Leetcode - 51. N 皇后

class Solution {

    // cols[i]表示第i列是否存在皇后
    private boolean[] cols;

    // forwardSlashs[i]表示第i根从右上到左下的斜线上是否存在皇后，最左上角那个位置是第0根这样的斜线
    private boolean[] forwardSlashs;

    // backSlashs[i]表示第i根从左上到右下的斜线上是否存在皇后，最左下角那个位置是第0根这样的斜线
    private boolean[] backSlashs;

    // puzzle表示棋盘
    private char[][] puzzle;

    // n表示棋盘的维度
    private int n;

    // 计算某个位置在哪根斜线上
    private int getSlashIndex(int x, int y, boolean isForward) {
        
        // 如果是计算右上到左下的斜线的下标：
        //     (0, 0)位于第0根斜线，(1, 0)和(0, 1)位于第1根斜线，因此斜线下标为x + y
        // 如果是计算左上到右下的斜线的下标：
        //     (n - 1, 0)位于第0根斜线，(n - 2, 0)和(n - 1, 1)位于第1根斜线，因此斜线下标为n - 1 - x + y
        return isForward ? (x + y) : (n - 1 - x + y);
    }

    // 使用回溯法
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ret = new ArrayList<>();
        
        // 初始化成员变量
        this.n = n;
        this.cols = new boolean[n];
        this.forwardSlashs = new boolean[n + n - 1];
        this.backSlashs = new boolean[n + n - 1];
        this.puzzle = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                this.puzzle[i][j] = '.';
            }
        }
        
        // 从第0行开始放置皇后
        putAQueenInThisRow(0, ret);
        return ret;
    }

    private void putAQueenInThisRow(int r, List<List<String>> ret) {
        
        // r == n说明棋盘已经放置完成，因此将此时的棋盘状态保存到ret中
        if (r == n){
            List<String> list = new ArrayList<>();
            for (char[] row : puzzle) {
                list.add(new String(row));
            }
            ret.add(list);
            return;
        }

        // 如果还没有放置完成，则开始在本行的第1到n列逐个尝试放置皇后
        for (int i = 0; i < n; i++){

            int forwardSlashIndex = getSlashIndex(r, i, true);
            int backSlashIndex = getSlashIndex(r, i, false);
            
            // 如果当前列或当前斜线上已经有皇后了，则跳过
            if (cols[i] || forwardSlashs[forwardSlashIndex] || backSlashs[backSlashIndex]) {
                continue;
            }
            
            // 否则在本行的第i列上放置皇后
            cols[i] = forwardSlashs[forwardSlashIndex] = backSlashs[backSlashIndex] = true;
            puzzle[r][i] = 'Q';

            // 然后再在第r + 1行放置皇后
            putAQueenInThisRow(r + 1, ret);

            // 回溯
            cols[i] = forwardSlashs[forwardSlashIndex] = backSlashs[backSlashIndex] = false;
            puzzle[r][i] = '.';
        }
    }
}