52. N-Queens II #

Problem #

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.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

Summary #

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Solution Ideas #

This problem is an enhanced version of Problem 51. On the basis of Problem 51, simply accumulate and record the number of solutions.
This problem can also be solved by a brute-force lookup table method, with a time complexity of O(1).

Code #


package leetcode

// Solution 1, brute-force lookup table method
func totalNQueens(n int) int {
	res := []int{0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724}
	return res[n]
}

// Solution 2, DFS backtracking method
func totalNQueens1(n int) int {
	col, dia1, dia2, row, res := make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1), []int{}, 0
	putQueen52(n, 0, &col, &dia1, &dia2, &row, &res)
	return res
}

// Try to place the queen in row index in an n-queens problem
func putQueen52(n, index int, col, dia1, dia2 *[]bool, row *[]int, res *int) {
	if index == n {
		*res++
		return
	}
	for i := 0; i < n; i++ {
		// Try to place the queen in row index in column i
		if !(*col)[i] && !(*dia1)[index+i] && !(*dia2)[index-i+n-1] {
			*row = append(*row, i)
			(*col)[i] = true
			(*dia1)[index+i] = true
			(*dia2)[index-i+n-1] = true
			putQueen52(n, index+1, col, dia1, dia2, row, res)
			(*col)[i] = false
			(*dia1)[index+i] = false
			(*dia2)[index-i+n-1] = false
			*row = (*row)[:len(*row)-1]
		}
	}
	return
}

// Solution 3, binary bit manipulation method
// class Solution {
// 	public:
// 		int totalNQueens(int n) {
// 			int ans=0;
// 			int row=0,leftDiagonal=0,rightDiagonal=0;
// 			int bit=(1<<n)-1;//to clear high bits of the 32-bit int
// 			Queens(bit,row,leftDiagonal,rightDiagonal,ans);
// 			return ans;
// 		}
// 		void Queens(int bit,int row,int leftDiagonal,int rightDiagonal,int &ans){
// 			int cur=(~(row|leftDiagonal|rightDiagonal))&bit;//possible place for this queen
// 			if (!cur) return;//no pos for this queen
// 			while(cur){
// 				int curPos=(cur&(~cur + 1))&bit;//choose possible place in the right
// 				//update row,ld and rd
// 				row+=curPos;
// 				if (row==bit) ans++;//last row
// 				else Queens(bit,row,((leftDiagonal|curPos)<<1)&bit,((rightDiagonal|curPos)>>1)&bit,ans);
// 				cur-=curPos;//for next possible place
// 				row-=curPos;//reset row
// 			}
// 		}
// };