N-Queen using Generator

August 6, 2022

I’m trying to store indices of possible positions of queens so that no queen can attack each other then using that indices I’m putting my queen at that particular indices but I’m not getting expected result. Here is what I tried.

def queens(n, i, a, b, c):
    if i < n:
        for j in range(n):
            if j not in a and i + j not in b and i - j not in c:
                yield from queens(n, i + 1, a + [j] , b + [i+ j], c + [i-j])
    else:
        yield a

n = 4
ans =[]
board = [["."]*n for i in range(n)]
for solution in queens(n, 0, [], [] , []):
    for i in range(n):
        board[solution[i]][i] = 'Q'
        copy = ["".join(row) for row in board]
    ans.append(copy)
print(ans)

My Output:

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

Actual:

[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

>Solution :

You are very close.

I made some inline notes where I made changes.

def queens(n, i, a, b, c):
    if i < n:
        for j in range(n):
            if j not in a and i + j not in b and i - j not in c:
                yield from queens(n, i + 1, a + [j] , b + [i+ j], c + [i-j])
    else:
        yield a

n = 4
ans =[]
for solution in queens(n, 0, [], [] , []):
    # move the board inside the loop so it creates a new unique board 
    # on each iteration  otherwise all of the values from the last iteration
    # are still on the same board
    board = [["."]*n for i in range(n)]  # <- moving this is what solved the isssue
    for i in range(n):
        board[solution[i]][i] = 'Q'
    copy = ["".join(row) for row in board]  # moved this outside inner loop
                                            # since it only needs to execute
                                            # once per outer loop
    ans.append(copy)
print(ans)