52. N-Queens II (H)

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 the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 9

Solution:

Version 1:

不使用 boolean 数组来记录访问情况，直接暴力使用 for 循环来判断是否可以摆放在某个位置的写法。

java

class Solution {
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    public int totalNQueens(int n) {
        if (n <= 0) {
            return 0;
        }
        
        return search(new ArrayList<Integer>(), n);
    }
   
    private boolean isValid(List<Integer> cols, int colIndex) {
        int rowIndex = cols.size();
        for (int row = 0; row < cols.size(); row++) {
            int col = cols.get(row);
            if (col == colIndex || row + col == rowIndex + colIndex || 
                    row - col == rowIndex - colIndex) {
                return false;
            }
        }
        return true;
    }
    
    // search函数为搜索函数，n表示已经放置了n个皇后，cols 表示每个皇后所在的列
    private int search(List<Integer> cols, int n) {
        int rowIndex = cols.size();

        // 若已经放置了n个皇后表示出现了一种解法
        if (rowIndex == n) {
            return 1;
        }

        int sum = 0;
        // 枚举当前皇后放置的列，若不合法则跳过
        for (int colIndex = 0; colIndex < n; colIndex++) {
            if (!isValid(cols, colIndex)) {
                continue;
            }
            // 若合法则递归枚举下一行的皇后
            cols.add(colIndex);
            sum += search(cols, n);
            cols.remove(cols.size() - 1);
        }
        
        return sum;
    }
}

Version 2:

usedColumns[row]每次循环是直接改数值,不是累加,所以不需要回溯,加了usedColumns[row] = 0也不影响结果

public class Solution {
    public static int sum;
    public int totalNQueens(int n) {
        sum = 0;
        int[] usedColumns = new int[n];
        placeQueen(usedColumns, 0);
        return sum;
    }
    public void placeQueen(int[] usedColumns, int row) {
        int n = usedColumns.length;
        
        if (row == n) {
            sum ++;
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (isValid(usedColumns, row, i)) {
                usedColumns[row] = i;
                placeQueen(usedColumns, row + 1);
            }
        }
    }
    public boolean isValid(int[] usedColumns, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (usedColumns[i] == col) {
                return false;
            }
            // 这里是判断对角线， 包含两种情况
            //row + col == i + usedColumns[i] 移项后就是row - i == usedColumns[i] - col 
            以及row - col == i - usedColumns[i] 移项后就是 row - i == col - usedColomns[i]
            if ((row - i) == Math.abs(col-usedColumns[i])) {
                return false;
            }
        }
        return true;
    }
}