The problem description is as follows: The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

So no two queens can be on the same column, row or diagonals.

Example input/output Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] "." represents an empty cell on an n*n board, and "Q" represents a queen.

So far the solution that I came up with is through simple bfs as I noticed that every two queens are a knight move from each other. And since every column needs a queen, I iterate through the first row and check for possible solution starting at row 0 and the ith column. The problem is that I will only have one solution for each column, but there may be two. I think the problem involves backtracking. But I don't know how or if it is possible to include backtracking in the bfs.

def solveNQueens(self, n: int) -> List[List[str]]:
        moves = ((1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1))
        
        queue = deque()
        
        res = []
        ans = []
        for i in range(n):
            queue.append((0, i, [(0, i)]))
            diagonalR = set([0-i])
            diagonalL = set([0+i])
            visitedCol = set([i])
            visitedRow = set([0])
            while queue:
                cr, cc, queens = queue.popleft()
                for di, dj in moves:
                    if len(queens) == n and queens not in ans:
                        ans.append(queens)
                        res.append(['.' * x[1] + 'Q' + '.' * (n-1-x[1]) for x in queens])
                        continue
                    if 0 <= cr + di < n and 0 <= cc + dj < n and cr + di not in visitedRow and cc + dj not in visitedCol and (cr + di) + (cc + dj) not in diagonalL and (cr + di) - (cc + dj) not in diagonalR:
                        queens.append((cr + di, cc + dj))
                        queue.append((cr + di, cc + dj, queens))
                        visitedCol.add(cc + dj)
                        visitedRow.add(cr + di)
                        diagonalR.add((cr + di) - (cc + dj))
                        diagonalL.add((cr + di) + (cc + dj))
                        
        return res
        

For example, for n = 5, there are 10 ways for arranging 5-queens but I only got 5.

My output: [["Q....","..Q..","....Q",".Q...","...Q."],[".Q...","...Q.","Q....","..Q..","....Q"],
["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.",".Q...","....Q","..Q..","Q...."],
["....Q","..Q..","Q....","...Q.",".Q..."]]

Expected output: [["Q....","..Q..","....Q",".Q...","...Q."],
["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],
[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],
["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],
["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],
["....Q","..Q..","Q....","...Q.",".Q..."]]