Recursion

What is recursion?

→ When a function calls itself until a specified condition is met, it is known as recursion.

# infinite recursion - runs until stack overflow, when there is no base condition
# The unexecuted functions are stored in the stack memory, and when an infinite recursion is called
# the stack space is extinguished which is known as stack overflow! ex-
 
def fn():
	print(1)
	fn()
	
fn()

Basic Recursion Problems (1D)

# Print your name n times using recursion 
 
def print_name(i,n):
	if i>n:
		return
	print("aniket")
	print_name(i+1,n)
	
n = int(input("enter the value of n"))
print_name(1,n)
 
# Time Complexity = O(n) and Space Complexity = O(n)

aniket
aniket
aniket
aniket
aniket

# Print numbers from n → 1
 
def print_num(i):
	if i<1:
		return
	print(i)
	print_num(i-1)
 
 
n = int(input("enter the value of n"))
print_num(n)

5
4
3
2
1

# Print numbers from 1 → n (backtracking concept)
 
def print_num(i):
	if i<1:
		return
	print_num(i-1)
	print(i)  # notice the difference from above code
	
n = int(input("enter the value of n"))
print_num(n)
 
# When we do an operation after a fn call in recursion, it executes for the last call first known as backtracking!

1
2
3
4
5

# Print numbers from n → 1 using backtracking
 
def print_num(i,n):
	if i>n:
		return
	print_num(i+1,n)
	print(i)
	
n = int(input("enter the value of n"))
print_num(1,n)

5
4
3
2
1

Parameterized and Functional Recursion

# Summation of numbers from 1 → n (parameterized recursion)
 
def print_sum(n,sum):
	if n==0:
		print(sum)
		return
	print_sum(n-1,sum+n)
		
n = int(input("enter the value of n"))
print_sum(n,0)
 
# in parameterized recursion we carry the ans as a paramter

15

# Summation of numbers from 1 → n (functional recursion)
 
def print_sum(n):
	if n==0:
		return 0
	return n + print_sum(n-1)
	
n = int(input("enter the value of n"))
print(print_sum(n))
 
# in functional recursion we return the ans to the previous call! 

15

# Reverse an array using recursion - parameterized
 
def rev(arr, i):
    size = len(arr)
    if i >= size // 2:
        return
    arr[i], arr[size - i - 1] = arr[size - i - 1], arr[i]
    rev(arr, i + 1)
 
arr= [3, 2, 4, 1, 5]
rev(arr, 0)
print("reversed array:", arr)

reversed array: [5, 1, 4, 2, 3]

# Check if a given string is palindome or not? - functional
 
def check(str, i):
    size = len(str)
    if i>= size//2:
        return True
    elif str[i]==str[size-i-1]:
        return check(str,i+1)
    else:
        return False
 
str = input("enter the string")
print(check(str,0))

False

Recursion Mindset

the following problems are crucial to develop a recursion mindset!

# sort an array using recursion, tricky one!
 
def sort(arr, i):
    if i==len(arr)-1:
        return
 
    # sort the array for i+1 -> len(arr)
    sort(arr, i+1)
 
    # insert this element in the correct position in the sorted array and remove its old index
    curr= arr[i]
    j= i+1
    while j<len(arr) and arr[j]<curr:
        arr[j-1]= arr[j]
        j+=1
    arr[j-1]= curr
 
arr= [3, 2, 4, 1, 11, 21]
sort(arr, 0)
print(arr)

[1, 2, 3, 4, 11, 21]

# sort a stack using recursion, tricky one!
 
def insert(st, num):
    if len(st)==0:
        st.append(num)
        return
    
    top= st.pop()
    if top>num:
        insert(st, num)
        st.append(top)
    else:
        st.append(top)
        st.append(num)
 
def sort(st):
    if len(st)==1:
        return
    
    top= st.pop()
    # sort the stack for the remaining elements except top
    sort(st)
 
    # insert top in the correct position in the sorted stack
    insert(st, top)
 
st= [2, 3, 1, 11, 41]
sort(st)
print(st)

[1, 2, 3, 11, 41]

# reverse a stack using recursion
 
def insertTop(st, num):
    if not st:
        st.append(num)
        return
    
    top= st.pop()
    insertTop(st, num)
    st.append(top)
 
def reverse(st):
    if len(st)==1:
        return
 
    top= st.pop()
    # reverse the stack for the remaining elements except top
    reverse(st)
 
    insertTop(st, top)
 
st= [1, 2, 3, 4, 5]
reverse(st)
print(st)

[5, 4, 3, 2, 1]

# fast exponentiation (find pow(x,n)) - difficult one!
 
def exp(x, n):
    powr= n if n>0 else -n
    val= x
    ans= 1
    while powr>0:
        if powr%2==0:
            val*= val
            powr/=2
        else:
            ans*= val
            powr-= 1
    return ans
 
print(exp(2, 10))

1024

# Generate Parentheses, beautiful approach!
 
def gen(n, comb, ans):
    if len(comb)==2*n:
        ans.append(comb)
        return
    
    # can we use "(" ?
    if comb.count("(")<n:
        gen(n, comb+"(", ans)
 
    # can we use ")" ?
    if comb.count("(") > comb.count(")"):
        gen(n, comb+")", ans)
 
ans= []
gen(3, "", ans)
print(ans)

['((()))', '(()())', '(())()', '()(())', '()()()']

Multiple Recursion Calls

# Print nth Fibonacci Number
 
def fib(i):
    if i<=1:
        return i
    else:
        return fib(i-1) + fib(i-2)
    
n = int(input("enter fibonacci index"))
print(fib(n))

5

# Print all fibonacci numbers till a given index n
 
n = int(input("enter the index"))
fib = []
for i in range(n+1):
    if i<=1:
        fib.append(i)
    else:
        fib.append(fib[i-1]+fib[i-2])
 
print(fib)

[0, 1, 1, 2, 3, 5]

Recursion on Subsequences

What is a Subsequence?

A subsequence is a sequence derived by deleting some or no elements from the original array without changing the order.

🔹 Elements may not be contiguous but must appear in the same relative order.

Example

Given array: [1, 2, 3]

✅ Valid Subsequences:

[1, 2]
[1, 3]
[2, 3]
[1, 2, 3] (the full array itself)
[ ] (empty subsequence)

⛔ Invalid: [3, 1] (order changed)

🔹 Number of Subsequences: 2^n (Each element has 2 choices: include or exclude)

What is a Subarray?

Subarray

A subarray is a contiguous part of an array.

🔹 Elements must be contiguous (no skipping allowed).

Example

📌 Given array: [1, 2, 3]

✅ Valid Subarrays:

[1]
[2]
[3]
[1, 2]
[2, 3]
[1, 2, 3]

⛔ Invalid: [1, 3] (not contiguous)

🔹 Number of Subarrays: n * (n + 1) / 2 (all possible start-end pairs)

# Print all subsequences
 
def print_sub(i, sub, arr):
    if i==len(arr):
        print(sub)
        return
    
    # pick the current element
    sub.append(arr[i])
    print_sub(i+1,sub,arr)
 
    # not pick the current element
    sub.pop()
    print_sub(i+1,sub,arr)
 
arr = [2, 1, 5]
print_sub(0, [], arr)
 
# Time Complexity = O(2^n) and Space Complexity = O(n)

[2, 1, 5]
[2, 1]
[2, 5]
[2]
[1, 5]
[1]
[5]
[]

# Print all subsequences whose sum is k
 
def print_sub(i, sub, arr, sum, k):
    # if sum is hit
    if sum==k:
        print(sub)
        return
    
    # if elements are over
    if i==len(arr):
        return
    
    # pick the current element
    if sum+arr[i]<=k:
        sub.append(arr[i])
        print_sub(i+1,sub,arr,sum+arr[i],k)
        sub.pop()
    
    # not pick the current element
    print_sub(i+1,sub,arr,sum,k)
 
arr = [1, 2, 5, 3]
print_sub(0, [], arr, 0, 5)

[2, 3]
[5]

# Print one subsequence whose sum is k
 
def print_sub(i, sub, arr, sum, k):
    # if sum is hit
    if sum==k:
        print(sub)
        return True
    
    # if elements are over
    if i==len(arr):
        return False
    
    # pick the current element
    if sum+arr[i]<=k:
        sub.append(arr[i])
        if print_sub(i+1,sub,arr,sum+arr[i],k):
            return True
        sub.pop()
    
    # not pick the current element
    return print_sub(i+1,sub,arr,sum,k)
 
arr = [1, 2, 5, 3]
print_sub(0, [], arr, 0, 5)

[2, 3]





True

Note:

A very important trick for recursion is:

• Whenever we have to print / return a single item we return True / False
• Whenever we have to return a count, return 0 or 1

# Print count of subsequence whose sum is k
 
def count(i, arr, sum, k):
    if sum == k:
        return 1
    if i == len(arr):
        return 0
 
    # Pick the current element
    pick = 0
    if sum + arr[i] <= k:
        pick = count(i + 1, arr, sum + arr[i], k)
 
    # Not pick the current element
    not_pick = count(i + 1, arr, sum, k)
 
    return pick + not_pick
 
arr = [1] * 20
print(count(0, arr, 0, 5))

15504

# Merge Sort
 
def merge(arr, start, mid, end):
    left= start
    right= mid+1
 
    temp = []
 
    while left<=mid and right<=end:
        if arr[left]<=arr[right]:
            temp.append(arr[left])
            left+=1
        else:
            temp.append(arr[right])
            right+=1
 
    while left<=mid:
        temp.append(arr[left])
        left+=1
    
    while right<=end:
        temp.append(arr[right])
        right+=1
 
    for i in range(start,end+1):
        arr[i]= temp[i-start]
 
def mergesort(arr, start, end):
    if start<end:
        mid=(start + end)//2
        mergesort(arr,start,mid)
        mergesort(arr,mid+1,end)
        merge(arr,start,mid,end)
 
 
arr = [2, 1, 3, 8, 4, 6]
mergesort(arr, 0, 5)
print(arr)
 
# Time Complexity = O(NlogN) , Space Complexity = O(N)

[1, 2, 3, 4, 6, 8]

# Quick Sort
 
def getpartition(arr, start, end):
    pivot = arr[start]
    i = start + 1
    j = end
 
    while True:
        while i <= j and arr[i] <= pivot:
            i += 1
        while i <= j and arr[j] > pivot:
            j -= 1
 
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            break
 
    arr[start], arr[j] = arr[j], arr[start]
    return j
 
 
def quicksort(arr, start, end):
    if start < end:
        # keep the partition in its sorted pos
        partition = getpartition(arr, start, end) 
        quicksort(arr, start, partition - 1)
        quicksort(arr, partition + 1, end)
 
arr = [2, 1, 3, 8, 4, 6]
quicksort(arr, 0, len(arr) - 1)
print(arr)
 
# Time Complexity = O(NlogN) , Space Complexity = O(1)

[1, 2, 3, 4, 6, 8]

# Combination Sum - I
 
def solve(i, arr, com, ans, target):
    if target==0:
        ans.append(com[:])
        return
    
    if i==len(arr):
        return
    
    # pick
    if target>=arr[i]:
        com.append(arr[i])
        solve(i, arr, com, ans, target-arr[i])
        com.pop()
 
    # not pick
    solve(i+1, arr, com, ans, target)
 
 
arr = [2, 3, 6, 7]
target = 7
ans = []
solve(0, arr, [], ans, 7)
print(ans)
 
# Time Complexity = O(2^n * k) , Space Complexity = O(k * n) , k = avg length of combinations

[[2, 2, 3], [7]]

# why combination-I approach cannot be used in combination-II?
 
def solve(i, arr, com, ans, target):
    if target==0:
        ans.append(com[:])
        return
    
    if i==len(arr):
        return
    
    # pick
    if target>=arr[i]:
        com.append(arr[i])
        solve(i+1, arr, com, ans, target-arr[i])
        com.pop()
 
    # not pick
    solve(i+1, arr, com, ans, target)
 
arr = [10, 1, 2, 7, 6, 1, 5]
ans = [] # keeping this as hash-set will solve our problem but T.C = O((2^n)*(logk))
solve(0, arr, [], ans, 8)
print(ans) # generates duplicate sets

[[1, 2, 5], [1, 7], [1, 6, 1], [2, 6], [2, 1, 5], [7, 1]]

# Combination Sum - II (V.V. Imp)
 
# Note: We are not using the pick and not pick approach here because that approach can lead to duplicates getting generated, so to 
# handle the duplicates, we are exploring all the possible starting points at each level (optimized)
 
def solve(i, arr, target, comb, ans):
    if target==0:
        ans.append(comb[:])
        return
 
    for j in range(i,len(arr)):
        if j>i and arr[j]==arr[j-1]:
            continue
 
        if arr[j]>target:
            return
 
        comb.append(arr[j])
        solve(j+1,arr,target-arr[j],comb,ans)
        comb.pop()
 
arr = [10, 1, 2, 7, 6, 1, 5]
target = 8
ans = []
arr.sort()
solve(0, arr, target, [], ans)
print(ans)
 
# Time Complexity = O(K * 2^N) 

[[3, 6]]

# Subsets - I / Power Set
 
def solve(i, arr, ans, s):
    if i==len(arr):
        ans.append(s)
        return
    
    # pick
    solve(i+1,arr,ans,s+arr[i])
    
    # not pick
    solve(i+1,arr,ans,s) 
 
arr = [2, 3, 6, 3]
ans = []
solve(0, arr, ans, 0)
print(ans)

[14, 11, 8, 5, 11, 8, 5, 2, 12, 9, 6, 3, 9, 6, 3, 0]

# Subset Sum - II
 
def solve(i, arr, comb, ans):
    ans.append(comb[:])
 
    for j in range(i,len(arr)):
        if j>i and arr[j]==arr[j-1]:
            continue
 
        comb.append(arr[j])
        solve(j+1, arr, comb, ans)
        comb.pop()
        
arr = [1,2,2]
ans = []
solve(0, arr, [], ans)
print(ans)

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

# Combination Sum - III
 
def solve(start, k, target, com, ans):
    if len(com)==k and target==0:
        ans.append(com[:])
        return
 
    for i in range(start, 10):
        if i<=target:
            com.append(i)
            solve(i+1, k, target-i, com, ans)
            com.pop()
 
ans= []
solve(1, 3, 7, [], ans)
print(ans)

[[1, 2, 4]]

# Print all permuations (naive approach)
 
def solve(i, arr, map, perm, ans):
    if i==len(arr):
        ans.append(perm[:])
        return
 
    for j in range(0,len(arr)):
        if map[j]==0:
            perm.append(arr[j])
            map[j]= 1
            solve(i+1,arr,map,perm,ans)
            map[j]= 0
            perm.pop()
 
ans = []
arr = [1,2,3]
map = [0] * len(arr)
solve(0, arr, map, [], ans)
print(ans)
 
# Time Complexity = O(n! * n) , Space Complexity = O(n)

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

# Print all permutations (optimized)
 
def solve(i, arr, ans):
    if i==len(arr):
        ans.append(arr[:])
        return
    
    for j in range(i,len(arr)):
        arr[i], arr[j] = arr[j], arr[i]
        solve(i+1,arr,ans)
        arr[i], arr[j] = arr[j], arr[i]
 
ans = []
arr = [1,2,3]
solve(0, arr, ans)
print(ans)
 
# Time Complexity = O(n! * n) , Space Complexity = O(1)

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

# N Queens
 
def isSafe(row, col, board):
    # check left horizontal
    c= col
    while c>=0:
        if board[row][c]=="Q":
            return False
        c-=1
 
    # check left diagonal upper
    c= col
    r= row
    while c>=0 and r>=0:
        if board[r][c]=="Q":
            return False
        r-=1
        c-=1
 
    # check left diagonal lower
    c= col
    r= row
    while c>=0 and r<len(board):
        if board[r][c]=="Q":
            return False
        r+=1
        c-=1
 
    return True
 
 
def solve(col, board, ans):
    if col==len(board):
        ans.append([row[:] for row in board])
        return
    
    for row in range(0,len(board)):
        if isSafe(row, col, board):
            board[row][col]= "Q"
            solve(col+1,board,ans)
            board[row][col]= "."
 
board = [["."] * 8 for _ in range(8)]
ans = []
solve(0, board, ans)
print(ans)
 

[[['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.']], [['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.']], [['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.']], [['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.']], [['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.']], [['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.']], [['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.']], [['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.']], [['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.']], [['.', '.', 'Q', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', 'Q', '.', '.'], ['.', '.', '.', 'Q', '.', '.', '.', '.'], ['.', 'Q', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', 'Q'], ['.', '.', '.', '.', 'Q', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', 'Q', '.'], ['Q', '.', '.', '.', '.', '.', '.', '.']]]

# N Queens Optimized
 
def solve(col, board, ans, leftRow, leftDiagUpper, leftDiagLower):
    if col == len(board):
        ans.append(["".join(row) for row in board])
        return
    
    for row in range(len(board)):
        if row not in leftRow and (row + col) not in leftDiagLower and (row - col) not in leftDiagUpper:
            leftRow.add(row)
            leftDiagLower.add(row + col)
            leftDiagUpper.add(row - col)
            board[row][col] = "Q"
            
            solve(col + 1, board, ans, leftRow, leftDiagUpper, leftDiagLower)
            
            board[row][col] = "."
            leftRow.remove(row)
            leftDiagLower.remove(row + col)
            leftDiagUpper.remove(row - col)
 
board = [["."] * 8 for _ in range(8)]
ans = []
solve(0, board, ans, set(), set(), set())
print(ans)

[['Q.......', '......Q.', '....Q...', '.......Q', '.Q......', '...Q....', '.....Q..', '..Q.....'], ['Q.......', '......Q.', '...Q....', '.....Q..', '.......Q', '.Q......', '....Q...', '..Q.....'], ['Q.......', '.....Q..', '.......Q', '..Q.....', '......Q.', '...Q....', '.Q......', '....Q...'], ['Q.......', '....Q...', '.......Q', '.....Q..', '..Q.....', '......Q.', '.Q......', '...Q....'], ['.....Q..', 'Q.......', '....Q...', '.Q......', '.......Q', '..Q.....', '......Q.', '...Q....'], ['...Q....', 'Q.......', '....Q...', '.......Q', '.Q......', '......Q.', '..Q.....', '.....Q..'], ['....Q...', 'Q.......', '.......Q', '...Q....', '.Q......', '......Q.', '..Q.....', '.....Q..'], ['..Q.....', 'Q.......', '......Q.', '....Q...', '.......Q', '.Q......', '...Q....', '.....Q..'], ['....Q...', 'Q.......', '...Q....', '.....Q..', '.......Q', '.Q......', '......Q.', '..Q.....'], ['......Q.', 'Q.......', '..Q.....', '.......Q', '.....Q..', '...Q....', '.Q......', '....Q...'], ['....Q...', 'Q.......', '.......Q', '.....Q..', '..Q.....', '......Q.', '.Q......', '...Q....'], ['...Q....', 'Q.......', '....Q...', '.......Q', '.....Q..', '..Q.....', '......Q.', '.Q......'], ['.Q......', '.....Q..', 'Q.......', '......Q.', '...Q....', '.......Q', '..Q.....', '....Q...'], ['....Q...', '..Q.....', 'Q.......', '......Q.', '.Q......', '.......Q', '.....Q..', '...Q....'], ['.......Q', '..Q.....', 'Q.......', '.....Q..', '.Q......', '....Q...', '......Q.', '...Q....'], ['...Q....', '.....Q..', 'Q.......', '....Q...', '.Q......', '.......Q', '..Q.....', '......Q.'], ['....Q...', '......Q.', 'Q.......', '...Q....', '.Q......', '.......Q', '.....Q..', '..Q.....'], ['.....Q..', '..Q.....', 'Q.......', '.......Q', '...Q....', '.Q......', '......Q.', '....Q...'], ['....Q...', '..Q.....', 'Q.......', '.....Q..', '.......Q', '.Q......', '...Q....', '......Q.'], ['.....Q..', '..Q.....', 'Q.......', '.......Q', '....Q...', '.Q......', '...Q....', '......Q.'], ['...Q....', '.......Q', 'Q.......', '..Q.....', '.....Q..', '.Q......', '......Q.', '....Q...'], ['.......Q', '...Q....', 'Q.......', '..Q.....', '.....Q..', '.Q......', '......Q.', '....Q...'], ['...Q....', '.......Q', 'Q.......', '....Q...', '......Q.', '.Q......', '.....Q..', '..Q.....'], ['...Q....', '......Q.', 'Q.......', '.......Q', '....Q...', '.Q......', '.....Q..', '..Q.....'], ['.....Q..', '...Q....', 'Q.......', '....Q...', '.......Q', '.Q......', '......Q.', '..Q.....'], ['.....Q..', '..Q.....', 'Q.......', '......Q.', '....Q...', '.......Q', '.Q......', '...Q....'], ['......Q.', '..Q.....', 'Q.......', '.....Q..', '.......Q', '....Q...', '.Q......', '...Q....'], ['....Q...', '......Q.', 'Q.......', '..Q.....', '.......Q', '.....Q..', '...Q....', '.Q......'], ['.Q......', '....Q...', '......Q.', 'Q.......', '..Q.....', '.......Q', '.....Q..', '...Q....'], ['.Q......', '.......Q', '.....Q..', 'Q.......', '..Q.....', '....Q...', '......Q.', '...Q....'], ['.....Q..', '.Q......', '......Q.', 'Q.......', '..Q.....', '....Q...', '.......Q', '...Q....'], ['......Q.', '.Q......', '...Q....', 'Q.......', '.......Q', '....Q...', '..Q.....', '.....Q..'], ['.......Q', '.Q......', '...Q....', 'Q.......', '......Q.', '....Q...', '..Q.....', '.....Q..'], ['....Q...', '.Q......', '.......Q', 'Q.......', '...Q....', '......Q.', '..Q.....', '.....Q..'], ['.....Q..', '.Q......', '......Q.', 'Q.......', '...Q....', '.......Q', '....Q...', '..Q.....'], ['....Q...', '.Q......', '.....Q..', 'Q.......', '......Q.', '...Q....', '.......Q', '..Q.....'], ['..Q.....', '....Q...', '......Q.', 'Q.......', '...Q....', '.Q......', '.......Q', '.....Q..'], ['.....Q..', '...Q....', '......Q.', 'Q.......', '.......Q', '.Q......', '....Q...', '..Q.....'], ['....Q...', '.......Q', '...Q....', 'Q.......', '......Q.', '.Q......', '.....Q..', '..Q.....'], ['..Q.....', '.....Q..', '.......Q', 'Q.......', '....Q...', '......Q.', '.Q......', '...Q....'], ['......Q.', '....Q...', '..Q.....', 'Q.......', '.....Q..', '.......Q', '.Q......', '...Q....'], ['.....Q..', '...Q....', '......Q.', 'Q.......', '..Q.....', '....Q...', '.Q......', '.......Q'], ['....Q...', '.......Q', '...Q....', 'Q.......', '..Q.....', '.....Q..', '.Q......', '......Q.'], ['..Q.....', '.....Q..', '...Q....', 'Q.......', '.......Q', '....Q...', '......Q.', '.Q......'], ['..Q.....', '.....Q..', '.......Q', 'Q.......', '...Q....', '......Q.', '....Q...', '.Q......'], ['....Q...', '......Q.', '...Q....', 'Q.......', '..Q.....', '.......Q', '.....Q..', '.Q......'], ['.Q......', '.....Q..', '.......Q', '..Q.....', 'Q.......', '...Q....', '......Q.', '....Q...'], ['.Q......', '....Q...', '......Q.', '...Q....', 'Q.......', '.......Q', '.....Q..', '..Q.....'], ['.Q......', '......Q.', '....Q...', '.......Q', 'Q.......', '...Q....', '.....Q..', '..Q.....'], ['......Q.', '.Q......', '.....Q..', '..Q.....', 'Q.......', '...Q....', '.......Q', '....Q...'], ['.......Q', '.Q......', '....Q...', '..Q.....', 'Q.......', '......Q.', '...Q....', '.....Q..'], ['...Q....', '.Q......', '.......Q', '.....Q..', 'Q.......', '..Q.....', '....Q...', '......Q.'], ['...Q....', '.Q......', '......Q.', '....Q...', 'Q.......', '.......Q', '.....Q..', '..Q.....'], ['..Q.....', '.....Q..', '.Q......', '......Q.', 'Q.......', '...Q....', '.......Q', '....Q...'], ['..Q.....', '....Q...', '.Q......', '.......Q', 'Q.......', '......Q.', '...Q....', '.....Q..'], ['.....Q..', '.......Q', '.Q......', '...Q....', 'Q.......', '......Q.', '....Q...', '..Q.....'], ['..Q.....', '.......Q', '...Q....', '......Q.', 'Q.......', '.....Q..', '.Q......', '....Q...'], ['..Q.....', '....Q...', '.......Q', '...Q....', 'Q.......', '......Q.', '.Q......', '.....Q..'], ['.....Q..', '..Q.....', '......Q.', '...Q....', 'Q.......', '.......Q', '.Q......', '....Q...'], ['.....Q..', '..Q.....', '....Q...', '......Q.', 'Q.......', '...Q....', '.Q......', '.......Q'], ['.....Q..', '..Q.....', '....Q...', '.......Q', 'Q.......', '...Q....', '.Q......', '......Q.'], ['...Q....', '.......Q', '....Q...', '..Q.....', 'Q.......', '......Q.', '.Q......', '.....Q..'], ['...Q....', '......Q.', '....Q...', '..Q.....', 'Q.......', '.....Q..', '.......Q', '.Q......'], ['...Q....', '.....Q..', '.......Q', '..Q.....', 'Q.......', '......Q.', '....Q...', '.Q......'], ['.Q......', '...Q....', '.....Q..', '.......Q', '..Q.....', 'Q.......', '......Q.', '....Q...'], ['...Q....', '.Q......', '....Q...', '.......Q', '.....Q..', 'Q.......', '..Q.....', '......Q.'], ['...Q....', '.Q......', '.......Q', '....Q...', '......Q.', 'Q.......', '..Q.....', '.....Q..'], ['..Q.....', '......Q.', '.Q......', '.......Q', '....Q...', 'Q.......', '...Q....', '.....Q..'], ['..Q.....', '.....Q..', '.Q......', '....Q...', '.......Q', 'Q.......', '......Q.', '...Q....'], ['..Q.....', '.....Q..', '.Q......', '......Q.', '....Q...', 'Q.......', '.......Q', '...Q....'], ['....Q...', '......Q.', '.Q......', '.....Q..', '..Q.....', 'Q.......', '...Q....', '.......Q'], ['....Q...', '......Q.', '.Q......', '.....Q..', '..Q.....', 'Q.......', '.......Q', '...Q....'], ['......Q.', '...Q....', '.Q......', '....Q...', '.......Q', 'Q.......', '..Q.....', '.....Q..'], ['......Q.', '...Q....', '.Q......', '.......Q', '.....Q..', 'Q.......', '..Q.....', '....Q...'], ['....Q...', '......Q.', '.Q......', '...Q....', '.......Q', 'Q.......', '..Q.....', '.....Q..'], ['..Q.....', '.....Q..', '.......Q', '.Q......', '...Q....', 'Q.......', '......Q.', '....Q...'], ['......Q.', '..Q.....', '.......Q', '.Q......', '....Q...', 'Q.......', '.....Q..', '...Q....'], ['...Q....', '......Q.', '....Q...', '.Q......', '.....Q..', 'Q.......', '..Q.....', '.......Q'], ['...Q....', '.....Q..', '.......Q', '.Q......', '......Q.', 'Q.......', '..Q.....', '....Q...'], ['....Q...', '..Q.....', '.......Q', '...Q....', '......Q.', 'Q.......', '.....Q..', '.Q......'], ['.Q......', '......Q.', '..Q.....', '.....Q..', '.......Q', '....Q...', 'Q.......', '...Q....'], ['...Q....', '.Q......', '......Q.', '..Q.....', '.....Q..', '.......Q', 'Q.......', '....Q...'], ['....Q...', '.Q......', '...Q....', '.....Q..', '.......Q', '..Q.....', 'Q.......', '......Q.'], ['..Q.....', '......Q.', '.Q......', '.......Q', '.....Q..', '...Q....', 'Q.......', '....Q...'], ['.....Q..', '...Q....', '.Q......', '.......Q', '....Q...', '......Q.', 'Q.......', '..Q.....'], ['.....Q..', '..Q.....', '......Q.', '.Q......', '...Q....', '.......Q', 'Q.......', '....Q...'], ['.....Q..', '..Q.....', '......Q.', '.Q......', '.......Q', '....Q...', 'Q.......', '...Q....'], ['...Q....', '......Q.', '..Q.....', '.......Q', '.Q......', '....Q...', 'Q.......', '.....Q..'], ['...Q....', '.Q......', '......Q.', '..Q.....', '.....Q..', '.......Q', '....Q...', 'Q.......'], ['....Q...', '.Q......', '...Q....', '......Q.', '..Q.....', '.......Q', '.....Q..', 'Q.......'], ['..Q.....', '....Q...', '.Q......', '.......Q', '.....Q..', '...Q....', '......Q.', 'Q.......'], ['..Q.....', '.....Q..', '...Q....', '.Q......', '.......Q', '....Q...', '......Q.', 'Q.......']]


Bad pipe message: %s [b'(Windows NT; Windows NT 10.0; en-IN) WindowsPow']
Bad pipe message: %s [b'(Windows NT; Windows NT 10.0; en-IN) WindowsPow']
Bad pipe message: %s [b"iW&[\x83=\xea@\x85\xd75\xa8\xd5\xa822\xbfc\x00\x00*\xc0,\xc0+\xc00\xc0/\x00\x9f\x00\x9e\xc0$\xc0#\xc0(\xc0'\xc0\n\xc0\t\xc0\x14\xc0\x13\x00\x9d\x00\x9c\x00=\x00<\x005\x00/\x00\n\x01\x00\x00=\x00\n\x00\x08\x00\x06\x00\x1d\x00\x17\x00\x18\x00\x0b\x00\x02\x01\x00\x00\r\x00\x1a\x00\x18\x08\x04\x08\x05\x08\x06\x04\x01\x05\x01\x02"]
Bad pipe message: %s [b'']
Bad pipe message: %s [b'\x03\x02', b'\x02\x06']
Bad pipe message: %s [b'']
Bad pipe message: %s [b'#\x00']

# Sudoku Solver
 
def isValid(row, col, board, ch):
    for i in range(9):
        if board[row][i]==ch:
            return False
        if board[i][col]==ch:
            return False
        if board[(row//3)*3 + (i//3)][(col//3)*3 + (i%3)]==ch:
            return False
    return True
 
def solve(board):
    for row in range(len(board)):
        for col in range(len(board[0])):
            if board[row][col]==".":
                for num in range(1,10):
                    ch= str(num)
                    if isValid(row, col, board, ch):
                        board[row][col]= ch
                        if solve(board):
                            return True
                        board[row][col]= "."
                return False
    return True
 
board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]]
 
solve(board)
print(board)

[['5', '3', '4', '6', '7', '8', '9', '1', '2'], ['6', '7', '2', '1', '9', '5', '3', '4', '8'], ['1', '9', '8', '3', '4', '2', '5', '6', '7'], ['8', '5', '9', '7', '6', '1', '4', '2', '3'], ['4', '2', '6', '8', '5', '3', '7', '9', '1'], ['7', '1', '3', '9', '2', '4', '8', '5', '6'], ['9', '6', '1', '5', '3', '7', '2', '8', '4'], ['2', '8', '7', '4', '1', '9', '6', '3', '5'], ['3', '4', '5', '2', '8', '6', '1', '7', '9']]

# M-coloring problem
 
def isSafe(node, col, adj, color):
    for neighbour in adj[node]:
        if color[neighbour]==col:
            return False
    return True
    
    
def solve(node, adj, color, v, m):
    if node==v:
        return True
        
    for col in range(1,m+1):
        if isSafe(node, col, adj, color):
            color[node]= col
            if solve(node+1, adj, color, v, m)==True:
                return True
            color[node]= 0
    return False
            
def graphColoring(v, edges, m):
    # create adjacent matrix
    adj= [[] for _ in range(v)]
    for u,w in edges:
        adj[u].append(w)
        adj[w].append(u)
    
    # create a color hash
    color= [0] * v
    
    return solve(0, adj, color, v, m)

# Palindrome Patitioning
 
def solve(index, s, partition, ans):
    if index==len(s):
        ans.append(partition[:])
        return
    
    for i in range(index, len(s)):
        sub= s[index:i+1]
        if sub==sub[::-1]:
            partition.append(sub)
            solve(i+1, s, partition, ans)
            partition.pop()
 
 
s = "aab"
ans= []
solve(0, s, [], ans)
print(ans)
 
# Time Complexity: O((2^n) *k*(n/2)) for gen palindrome and inserting them into ans list
# Space Complexity: O(k * x) k= avg len of palindrome, x= no of palindromes

[['a', 'a', 'b'], ['aa', 'b']]

# Rat in a Maze
 
def solve(i, j, mat, vis, path, ans):
        if i<0 or j<0 or i==len(mat) or j==len(mat[0]) or mat[i][j]==0 or vis[i][j]==1:
            return
        
        if i==len(mat)-1 and j==len(mat[0])-1:
            ans.append(path)
            return
        
        vis[i][j]= 1
 
        directions = [(1, 0, "D"), (0, -1, "L"), (0, 1, "R"), (-1, 0, "U")]
        
        for dx, dy, move in directions:
            solve(i + dx, j + dy, mat, vis, path + move, ans)
            
        vis[i][j]= 0
            
def findPath(mat):
    ans= []
    vis = [[0] * len(mat[0]) for _ in range(len(mat))]
    solve(0, 0, mat, vis, "", ans)
    return ans
 
 
maze = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]
print(findPath(maze))

['DDRDRR', 'DRDDRR']

# K-th permutation
 
def solve(n, k):
    fact= 1
    nums= []
 
    for i in range(1,n):
        fact= fact*i
        nums.append(i)
 
    nums.append(n)
    k= k-1
    ans= ""
 
    while True:
        group= k//fact
        ans+= str(nums[group])
        nums.pop(group)
        if len(nums)==0:
            break
        k= k%fact
        fact= fact//len(nums)
 
    return ans
 
print(solve(3,3))
 
# T.C = O(n)

213

# expression and operators
 
def solve(index, num, expression, curr_val, prev_val, target, result):
        if index == len(num) and curr_val == target:
            result.append(expression)
            return
        
        if index == len(num):
            return
        
        for i in range(index, len(num)):
            # remove trailing zeros
            if index != i and num[index] == '0':
                break
                
            # Get the current number
            curr_num = int(num[index:i+1])
            
            # If it's the first digit, no operation to perform yet
            if index == 0:
                solve(i+1, num, expression + str(curr_num), curr_num, curr_num, target, result)
            else:
                # Addition
                solve(i+1, num, expression + "+" + str(curr_num), curr_val + curr_num, curr_num, target, result)
                
                # Subtraction
                solve(i+1, num, expression + "-" + str(curr_num), curr_val - curr_num, -curr_num, target, result)
                
                # Multiplication: need to adjust for operator precedence
                # We subtract the previous value, then add (previous value * current number)
                solve(i+1, num, expression + "*" + str(curr_num), 
                           curr_val - prev_val + (prev_val * curr_num), 
                           prev_val * curr_num, target, result)
                
num= "123"
target= 6
ans= []
solve(0, num, "", 0, 0, target, ans)
print(ans)

['1+2+3', '1*2*3']