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.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

&nbsp;
Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above


Example 2:

Input: n = 1
Output: [["Q"]]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 9


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        coord = self.findNextRows(0, n)
        ans = []
        for c in coord:
            temp = []
            for j in c:
                temp.append("."*j+"Q"+"."*(n-j-1))
            ans.append(temp)
        return ans
                        
    def findNextRows(self, i, n, h_occ=set(), d_occ=set(), ad_occ=set()):
		'''
		h_occ: occupied horizontal coordinate
		d_occ: occupied diagonal
		ad_occ: occupied anti-diagonal
		'''
        ans = []
        if i==n:
            return [[]]
        for j in range(n):
             if (j not in h_occ) and (j-i not in d_occ) and ((j-n+1)+i not in ad_occ):
                    h_occ.add(j)
                    d_occ.add(j-i)
                    ad_occ.add((j-n+1)+i)
                    temp = self.findNextRows(i+1, n, h_occ, d_occ, ad_occ)
                    h_occ.remove(j)
                    d_occ.remove(j-i)
                    ad_occ.remove((j-n+1)+i)
                    ans += [[j]+l for l in temp]
        return ans
                
                
Simple backtracking logic, try out each row and col and check position is valid or not.

since we are going row one by one, there is no way queen is placed in that row.

so, we need to check col, diagonals for valid position.

// col is straightforward flag for each column

// dia1
// 0 1 2 3
// 1 2 3 4
// 2 3 4 5
// 3 4 5 6

// dia2
// 0 -1 -2 -3
// 1  0 -1 -2
// 2  1  0 -1
// 3  2  1  0

negative numbers are not allowed as index, so we add n - 1 to diagonal2.

class Solution {
    List<List<String>> ans = new LinkedList<>();
    int n;
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        int[][] board = new int[n][n];
        
        boolean[] col = new boolean[n];
        boolean[] dia1 = new boolean[2 * n];
        boolean[] dia2 = new boolean[2 * n];
        
        solve(0, col, dia1, dia2, board);
        return ans;
    }
    
    public void solve(int row, boolean[] col, boolean[] dia1, boolean[] dia2, int[][] board){
        if(row == n){
            copyBoardToAns(board);
            return;
        }
        // brute force all col in that row
        for(int i = 0; i < n; i++){
            if(isValid(col, dia1, dia2, i, row)){
                col[i] = true; dia1[row + i] = true; dia2[row - i + n - 1] = true;
                board[row][i] = 1;
                solve(row + 1, col, dia1, dia2, board);
                col[i] = false; dia1[row + i] = false; dia2[row - i + n - 1] = false;
                board[row][i] = 0;
            }
        }
    }
    
    public boolean isValid(boolean[] col, boolean[] dia1, boolean[] dia2, int curCol, int curRow){
        return !col[curCol] && !dia1[curCol + curRow] && !dia2[curRow - curCol + n - 1];
    }
    
    public void copyBoardToAns(int[][] board){
        List<String> res = new LinkedList<>();
        for(int i = 0; i < n; i++){
            String row = "";
            for(int j = 0; j < n; j++){
                if(board[i][j] == 1){
                    row += "Q";
                }else{
                    row += ".";
                }
            }
            res.add(row);
        }
        ans.add(res);
    }
}
class Solution {
    bool isSafe(vector<string> board, int row, int col, int n){
        int r=row;
        int c=col;
        
        // Checking for upper left diagonal
        while(row>=0 && col>=0){
            if(board[row][col]=='Q') return false;
            row--;
            col--;
        }
        
        row=r;
        col=c;
        // Checking for left
        while(col>=0){
            if(board[row][col]=='Q') return false;
            col--;
        }
        
        row=r;
        col=c;
        // Checking for lower left diagonal
        while(row<n && col>=0){
            if(board[row][col]=='Q') return false;
            row++;
            col--;
        }
        
        return true;
    }
    
    void solve(vector<vector<string>> &ans, vector<string> &board, int n, int col){
        if(col==n){
            ans.push_back(board);
            return;
        }
        
        for(int row=0;row<n;row++){
            if(isSafe(board,row,col,n)){
                board[row][col]='Q';
                solve(ans,board,n,col+1);
                board[row][col]='.';
            }
        }
    }
    
    
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<string> board;
        string s(n,'.');
        for(int i=0;i<n;i++) board.push_back(s);
        
        solve(ans,board,n,0);
        
        return ans;
    }
};
// time O(n!) | space O(n^n)
var solveNQueens = function(n) {
    let res = [];
    
    function backtrack(board, r) {
        if (r === n) {
            // - 1 to account for adding a Q that takes up a space
            res.push(board.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
            return;
        }
        
        for (let c = 0; c < n; c++) {
            // bc is the current element
            // br is the index of the element bc
            //
            // bc === c | checks row and col
            // bc === c - r + br | checks lower diagonal
            // bc === c + r - br | checks upper diagonal
            if (!board.some((bc, br) => bc === c || bc === c - r + br || bc === c + r - br)) {
                backtrack(board.concat(c), r + 1);
            }
        }
    }
    
    backtrack([], 0);
    
    return res;
};
N-Queens