52. N-Queens II

The n-queens puzzle is the problem of placing n queens on an n× 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.



Output: 2

 There are two distinct solutions to the 4-queens puzzle as shown below.
 [".Q..",  // Solution 1

 ["..Q.",  // Solution 2


  1. Backtracking:
    1. Having 3 boolean vectors, col, diag, anti-diag to mark where there is a queen on the same column, same diagnal, or same anti-diagnal. for col, the level set is col; for diagnal: the level set is col - row + n; for antidiagnal: the level set is row + col.
    2. for each row, expanding the cols and check where there is a queen in col, diag, and anti-diag, then recursively call the backtracking until the row reaches the end or did get in depth due to the disqualification of the results.


class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        boolean [] cols = new boolean[n], diag = new boolean[2*n], antiDiag = new boolean[2*n];
        return count;

    private void backtrack(int row, int n, boolean[] cols, boolean[]diag, boolean[]antiDiag){
        if(row == n) count++;

        for(int col = 0; col < n; col++){
            int d = row - col + n; 
            int aD = row + col;
            if(cols[col] || diag[d] || antiDiag[aD]) continue;

            cols[col] = true; diag[d] = true; antiDiag[aD] = true;
            backtrack(row + 1, n, cols, diag, antiDiag);
            cols[col] = false; diag[d] = false; antiDiag[aD] = false;


results matching ""

    No results matching ""