Contents

Brief

Place n queens on a chessboard without any of the queens threatening the other

Methods

Backtracking on permutations

Since we're backtracking on permutations of unique row indices, we only need to check diagonals. Below is example with n=4

'Up' diagonals p=i+a[j] where a[j]=[0,1,2,3] is the first trial permutation of row indices for columns [0,1,2,3] \

j\i 0 1 2 3
0 0 1 2 3
1 1 2 3 4
2 2 3 4 5
3 3 4 5 6

'Down' diagonals q=i+(n-1)-a[j] \

j/i 0 1 2 3
0 3 4 5 6
1 2 3 4 5
2 1 2 3 4
3 0 1 2 3

There are 2xn-1=7 up diagonals. The same elements along the up diagonals of p. There are 2xn-1=7 down diagonals. The same elements along the down diagonals of q

Implementation

```Python
def qqueens(n):
     a = list(range(n))
     u = [True]*(2*n - 1) 
     v = [True]*(2*n - 1)
     m = 0
     def sub(i):
         nonlocal m
         if i == n:
             m += 1
             print(a)
         else:
             for j in range(i, n):
                 p = i + a[j]
                 q = i + n - 1 - a[j]
                 if u[p] and v[q]:
                     u[p] = v[q] = False
                     a[i], a[j] = a[j], a[i]
                     sub(i + 1)
                     u[p] = v[q] = True
                     a[i], a[j] = a[j], a[i]

     sub(0)
     return m

solutions returned as generator using 'yield from' requires Python 3.3 \

```Python
def queens_bp(n):
     a = list(range(n)) #permutation being checked
     up = [True]*(2*n - 1) #"up" diagonals - going up left to right
     down = [True]*(2*n - 1) # "down" diagonals - going down left to right
     def sub(i):
         if i == n:
             yield tuple(a)
         else:
             for k in range(i, n):
                 j = a[k] 
                 p = i + j #up diagonals have equal sum of row and column index  
                 q = i - j + n - 1 #down diagonals have i-j+(n-1) equal
                 if up[p] and down[q]:
                     up[p] = down[q] = False
                     a[i], a[k] = a[k], a[i]
                     yield from sub(i + 1)
                     up[p] = down[q] = True
                     a[i], a[k] = a[k], a[i]
     yield from sub(0)

References ##