The n-queens puzzle is the problem of placing n queens on an n by n chessboard such that no two queens attack each other.

public class Solution {
    public ArrayList<ArrayList<String>> solveNQueens(int n) {
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
        if (n <= 0) return result;

        ArrayList<Integer> cols = new ArrayList<Integer>();
        search(n, cols, result);
        return result;
    }
    public void search(int n, ArrayList<Integer> cols, ArrayList<ArrayList<String>> result) {//add one queen to cols each time
        if (cols.size() == n) {//queen is located at (i, cols.get(i))
            result.add(placeQueens(cols));
            return;//we have added all rows
        }
        for (int col = 0; col < n; col ++) {
            if (isValid(cols, col)) {
                cols.add(col);
                search(n, cols, result);
                cols.remove(cols.size() - 1);
            }
        }
    }
    public boolean isValid(ArrayList<Integer> cols, int col) {
        int row = cols.size();//the row position for new queen
        for (int i = 0; i < cols.size(); i++) {
            if (cols.get(i) == col) {
                return false;//same column
            } else if (i - cols.get(i) == row - col) {
                return false;// left-top to right-bottom
            } else if (i + cols.get(i) == row + col) {
                return false;// right-top to left-bottom
            }
        }
        return true;
    }
    public ArrayList<String> placeQueens(ArrayList<Integer> cols) {
        ArrayList<String> chessboard = new ArrayList<String>();
        for (int i = 0; i < cols.size(); i++) {
            String row = "";
            for (int j = 0; j < cols.size(); j++) {
                if (j == cols.get(i)) {//find a queen at jth column
                    row += "Q";
                } else {
                    row += ".";
                }
            }
            chessboard.add(row);
        }
        return chessboard;
    }
}

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if not n:
            return

        ret = []
        self.helper(n, [], ret)
        return ret

    def helper(self, n, curr, ret):
        if len(curr) == n:
            ret.append(self.place_queen(curr))
            return
        for i in range(n):
            if self.is_valid(curr, i):
                curr.append(i)
                self.helper(n, curr, ret)
                curr.pop()

    def is_valid(self, cols, col):
        row = len(cols)
        for i, used in enumerate(cols):
            if used == col or abs(row - i) == abs(col - used):
                return False
        return True

    def place_queen(self, curr):
        board = []
        for num in curr:
            line = ["."] * len(curr)
            for j in range(len(line)):
                if j == num:
                    line[j] = "Q"
                    break
            board.append("".join(line))
        return board