Leetcode 52. N-Queens II

Explanation

In order to solve the n-queens puzzle, we need to place n queens on an nxn chessboard in such a way that no queens threaten each other. This means that no two queens should be on the same row, column, or diagonal.

For instance, in a 4x4 chess board, two valid placements are:

1
2
3[[".Q..",  // solution 1
4"...Q",
5"Q...",
6"..Q."],
7
8["..Q.",  // solution 2
9"Q...",
10"...Q",
11".Q.."]]

Our task is to compute the number of valid placements given a particular board size n.

Approach

The approach used in the solution involves a technique called backtracking. The algorithm works by placing a queen in each row, and then recursively trying to place the queens in the subsequent rows. If a valid placement is found, then we increment our answer.

Consider placing the queens on a 4x4 board. The algorithm starts at the first cell (0,0) and places a queen there. Then it moves onto the next row and again places a queen at (1,0). It then checks if this placement is valid, if not it moves the queen to the next column (1,1) and so on. If all the columns in a row have been exhausted, it backtracks and moves the queen in the previous row to the next column.

The algorithm keeps track of already occupied columns and two diagonals; we just mark them before trying to fit the next queen and unmark them once we are done with the current placement.

Python Solution

1
2python
3class Solution:
4    def totalNQueens(self, n: int) -> int:
5        self.count = 0
6        self.dfs([-1]*n, 0)
7        return self.count
8    
9    # depth is the row index, nums is a array where the index represents 
10    # the row and the value represents the column
11    def dfs(self, nums: List[int], index: int):
12        if index == len(nums):
13            self.count += 1
14            return
15        
16        for i in range(len(nums)):
17            nums[index] = i
18            if self.valid(nums, index):  # if it is a valid place, then go to next row
19                self.dfs(nums, index + 1)
20        
21    # check whether nth queens can be placed in that column
22    def valid(self, nums: List[int], n: int) -> bool:
23        for i in range(n):
24            if abs(nums[i]-nums[n]) == n - i or nums[i] == nums[n]:
25                return False
26        return True

Java Solution

1
2java
3class Solution {
4    int rows[];
5    int hills[];
6    int dales[];
7    int n;
8    int queens[];
9    int output = 0;
10    
11    public boolean isNotUnderAttack(int row, int col) {
12        int res = rows[col] + hills[row - col + 2 * this.n] + dales[row + col];
13        return (res == 0) ? true : false;
14    }
15    
16    public void placeQueen(int row, int col) {
17        queens[row] = col;
18        rows[col] = 1;
19        hills[row - col + 2 * this.n] = 1;
20        dales[row + col] = 1;
21    }
22    
23    public void removeQueen(int row, int col) {
24        queens[row] = 0;
25        rows[col] = 0;
26        hills[row - col + 2 * this.n] = 0;
27        dales[row + col] = 0;
28    }
29    
30    public int backtrack(int row) {
31        for (int col = 0; col < n; col++) {
32            if (isNotUnderAttack(row, col)) {
33                placeQueen(row, col);
34                if (row + 1 == n) output++;
35                else backtrack(row + 1);
36                removeQueen(row, col);
37            }
38        }
39        return output;
40    }
41    
42    public int totalNQueens(int n) {
43        this.n = n;
44        rows = new int[n];
45        hills = new int[4 * n];
46        dales = new int[2 * n];
47        queens = new int[n];
48        return backtrack(0);
49    }
50}

JavaScript Solution

1
2javascript
3var totalNQueens = function(n) {
4    let count = 0;
5    const board = new Array(n).fill().map(() => new Array(n).fill(false));
6
7    function isSafe(row, col) {
8        for(let i=0;i<n;i++){
9            if(board[i][col]) return false
10            if(board[row][i]) return false
11            if(row-i>=0 && col-i>=0 && board[row-i][col-i]) return false
12            if(row+i<n && col+i<n && board[row+i][col+i]) return false
13            if(row-i>=0 && col+i<n && board[row-i][col+i]) return false
14            if(row+i<n && col-i>=0 && board[row+i][col-i]) return false
15        }
16    return true
17    }
18  
19    function placeQueens(row) {
20        if (row === n) {
21          count++;
22          return;
23        }
24    
25        for (let col = 0; col < n; col++) {
26          if (isSafe(row, col)) {
27            // Place a queen at (row, col)
28            board[row][col] = true;
29            // Continue placing queens in the next row
30            placeQueens(row + 1);
31            // Remove the queen from (row, col)
32            board[row][col] = false;
33          }
34        }
35    }
36  
37    placeQueens(0);
38  
39    return count;
40};

C++ Solution

1
2c++
3class Solution {
4public:
5    int totalNQueens(int n) {
6        int ans = 0;
7        dfs(n, 0, vector<bool>(n), vector<bool>(2 * n - 1), vector<bool>(2 * n - 1),
8            ans);
9        return ans;
10    }
11
12private:
13  void dfs(int n, int i, vector<bool>&& cols, vector<bool>&& diag1,
14           vector<bool>&& diag2, int& ans) {
15    if (i == n) {
16      ++ans;
17      return;
18    }
19
20    for (int j = 0; j < n; ++j) {
21      if (cols[j] || diag1[i + j] || diag2[j - i + n - 1])
22        continue;
23      cols[j] = diag1[i + j] = diag2[j - i + n - 1] = true;
24      dfs(n, i + 1, move(cols), move(diag1), move(diag2), ans);
25      cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
26    }
27  }
28};

C# Solution

1
2csharp
3public class Solution {
4    int COUNT = 0;
5    public int TotalNQueens(int n) {
6        bool[] cols = new bool[n]; 
7        bool[] d1 = new bool[2*n];   
8        bool[] d2 = new bool[2*n];   
9        helper(0, cols, d1, d2, n);
10        return COUNT;
11    }
12    public void helper(int row, bool[] cols, bool[] d1, bool[] d2, int n) {
13        if (row == n) COUNT++;
14        for (int col=0; col<n; col++) {
15            int id1 = col - row + n;
16            int id2 = col + row;
17            if (cols[col] || d1[id1] || d2[id2]) continue;
18            
19            cols[col] = true; d1[id1] = true; d2[id2] = true;
20            helper(row+1, cols, d1, d2, n);
21            cols[col] = false; d1[id1] = false; d2[id2] = false;
22        }
23    }
24}

Analysis

The time complexity for each solution can be approximated to O(N!). At each row, we execute N possibilities and there are approximately N rows, therefore the method needs to perform N x N-1 x N-2 x...x 1 = N! calls.

The space complexity for all these solutions depends on the number of solutions and ranges O(N) to O(N^2). This is because it is tracking the locations of the placed queens in nxn board (or just n when just keeping track of the column index of each queen), thus space complexity is dependent on the size of the board.

Optimizations

While the solutions given above are quite optimal for their respective languages, there are a few potential optimizations that are possible:

1. Bitmasking: Store all the queen's positions in a single integer by using bitwise operations. This will reduce the space usage significantly.
2. Symmetry: We can exploit the symmetrical nature of the problem and perform the search on half part of the board and get the result for the other half by symmetry, this would reduce the computation time by half.
3. Better Pruning: The initial versions of the code explore all possible placements of queens, even when it is known that a solution is impossible. For instance, if two queens threaten each other, there is no point in going forward. Therefore, extra conditions could be added to stop unnecessary exploration.

Despite these potential optimizations, the mentioned solutions in Python, Java, JavaScript, C++, and C# are often sufficient for most needs, solving the problem efficiently and effectively.