Leetcode 51. N-Queens

Classic backtracking solution. The backtracking function takes current states,

int[] pos; 			// the position of queens
char[][] board;		// the current board
int curr_row; 		// the current row
int n;				// total number of rows

At the beginning of backtracking, we will check whether the input int[] pos is valid input. Note that we only need to check the last queen (since we check every other queens in previous rounds.)

class Solution {
    public List<List<String>> solveNQueens(int n) {
        var res = new ArrayList<List<String>>();
        var pos = new int[n];         //pos[i] is the col number of the queen in ith row
        Arrays.fill(pos, -1);
        var board = new char[n][n];
        for (int i = 0; i < board.length; i++) {
            Arrays.fill(board[i], '.');
        }
        backtracking(res, pos, board, 0, n);
        return res;
    }
    public void backtracking(List<List<String>> res, int[] pos, char[][] board, int curr_row, int n) {
        if (!isValid(pos, curr_row, n)) {
            return;
        }
        if (curr_row == n) {
            var sl = new ArrayList<String>();
            for (int i = 0; i < board.length; i++) {
                sl.add(new String(board[i]));
            }
            res.add(sl);
            return;
        }
        for (int i = 0; i < n; i++) {
            pos[curr_row] = i;
            board[curr_row][i] = 'Q';
            backtracking(res, pos, board, curr_row+1, n);
            pos[curr_row] = -1;
            board[curr_row][i] = '.';
        }
    }
    public final boolean isValid(int[] pos, int curr_row, int n) {
        if (curr_row < 1) {
            return true;
        }
        // check the last digit
        int last_row = curr_row-1;
        for (int i = 0; i < last_row; i++) {
            int x1 = pos[i], x2 = pos[last_row], y1 = i, y2 = last_row;
            if (x1==x2 || y1==y2 || (x1+y1)==(x2+y2) || (x1-x2)==(y1-y2)) {
                return false;
            }
        }
        return true;
    }
}