LeetCode 51

1. 放一个queen以后，其所在row，column，正对角线，反对角线都需要被标记成占用
2. 对nxn的格子，其对角线数为2*n - 1
3. 正对角线index = row + col
4. 反对角线index = row - col + (n - 1)
5. 需5个成员变量：分别用于标记被占用的格子，行，列 和对角线

    private boolean[] rows;
    private boolean[] cols;
    private boolean[] diag1;
    private boolean[] diag2;
    private boolean[][] board;

递归求解

1. 参数： row index， n； return void
2. base case:
   if rowIndex == n, convert current board into result
3. for col in range (0, n)
   1） 首先判断是否可以放置 （即行，列，对角线都没有被占用），如可以放置就标记其行，列，对角线，和board；
   2） 继续递归处理下一行： row + 1 （因为本行不能再放了）
   3） 清除标记

这样可以找到全部解

class Solution {
    private boolean[] rows;
    private boolean[] cols;
    private boolean[] diag1;
    private boolean[] diag2;
    private boolean[][] board;

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n < 0) {
            return result;
        }
        
        rows = new boolean [n];
        cols = new boolean [n];
        diag1 = new boolean [2*n - 1];
        diag2 = new boolean [2*n - 1];
        board = new boolean [n][n];
        
        solveNQueensHelper (0, n, result); // row first

        return result;
    }
    
    // 因为要求解所有解，所以不能像sudoku那道题一样，一旦有就返回。否则只会拿到一个解
    // 整个过程是，从row 0 开始，对 0 ~ n col进行尝试放置。如果以某个col （col 2）为起点，找到了一个解。那么继续col 3 试图找解。
    // 因为每一次都是row 0开始的，所以可以覆盖完所有解
    private void solveNQueensHelper (int row, int n, List<List<String>> result) {

        if (row == n) {
            List<String> tempList = new ArrayList<> ();
            for (int i = 0; i < n; i ++) {
                StringBuilder temp = new StringBuilder ();
                for (int j = 0; j < n; j++) {
                    if (board[i][j]) {
                        temp.append ("Q");
                    } else {
                        temp.append (".");
                    }
                }
                
                tempList.add (temp.toString ());
                
            }
            result.add (tempList);
            return;
        }

        for (int col = 0; col < n; col ++) {
            if (rows[row] || cols[col] || diag1[row + col] || diag2 [(row - col + (n - 1))]) {
                continue;
            }
            // System.out.println (row + "   " + col);
            rows [row] = true;
            cols [col] = true;
            diag1[row + col] = true;
            diag2 [(row - col + (n - 1))] = true;
            board [row][col] = true;
            
            solveNQueensHelper (row + 1, n, result); // 当前row已经方式，进行下一行
            
            rows [row] = false;
            cols [col] = false;
            diag1[row + col] = false;
            diag2 [(row - col + (n - 1))] = false;
            board [row][col] = false;
        }
    }
}

LeetCode 52: 区别在于不需要求具体解，所以不需要board这个变量

class Solution {
    private boolean[] rows;
    private boolean[] cols;
    private boolean[] diag1;
    private boolean[] diag2;
    // private boolean[][] board;
    
    public int totalNQueens(int n) {
        rows = new boolean[n];
        cols = new boolean[n];
        diag1 = new boolean[2*n - 1];
        diag2 = new boolean[2*n - 1];
        // board = new boolean[n][n];
        
        int[] result = { 0 };
        
        totalNQueensHelper (0, n, result); // start from row 0
        
        return result[0];
    }
    
    private void totalNQueensHelper (int row, int n, int[] result) {
        if (row == n) {
            result[0] ++;
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (rows[row] || cols[col] || diag1 [row + col] || diag2 [row - col + (n - 1)]) {
                continue;
            }
            
            rows [row] =  true;
            cols [col] =  true;
            diag1 [row + col] = true;
            diag2 [row - col + (n - 1)] = true;
            //board [row][col] = true;
            
            totalNQueensHelper (row + 1, n, result);
            
            rows [row] =  false;
            cols [col] =  false;
            diag1 [row + col] = false;
            diag2 [row - col + (n - 1)] = false;
            //board [row][col] = false;
            
        }
    }
}