52. N-Queens II

Question

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.

Solution

和昨天的题目51. N-Queens一样。
只是不需要转换并记录字符串了，递归结束时直接将res+1即可。

Code

class Solution {
    int target;
    int res;
    int[][] operations;
    public int totalNQueens(int n) {
        target = n;
        res = 0;
        operations = new int[][]{{-1,0},{-1,1},{-1,-1}};
        backtracking(new int[n][n], 0, 0);
        return res;
    }
    
    private void backtracking(int[][] board, int i, int n){
        if(n == target){
            res++;
            return;
        }
        for(int j = 0; j < target; j++){
            if(isValid(board, i, j)){
                board[i][j] = 1;
                backtracking(board, i+1, n+1);
                board[i][j] = 0;
            }
        }
    }
    
    private boolean isValid(int[][] board, int i, int j){
        for(int[] operation : operations){
            int p = i + operation[0], q = j + operation[1];
            while(p >= 0 && p < target && q >= 0 && q < target){
                if(board[p][q] == 1) return false;
                p += operation[0];
                q += operation[1];                
            }
        }
        return true;
    }
}