Topic:
The n-queen problem is the study of how to place n queens on an n-by-n chess board, and make the queens unable to attack each other.
Given an integer n, return the number of different solutions for n queens.
Example:
Input: 4
Output: 2
Explanation: 4 There are two different solutions to the queen problem.
[
[".Q..", // Solution 1
"... Q".
"Q...".
".. Q."].
[".. Q."// Solution 2
"Q...".
"... Q".
".Q.."]
]
Copy the codeTip:
- Queen, a chess piece, means the king’s wife. The queen does only one thing, and that is to eat. When she came across a piece she could eat, she quickly rushed to take it. Of course, she can take one or n-1 step sideways, vertically, or diagonally, and can advance or retreat. (Quoting from Baidu Baike – Empress)
The topic
Similar questions have done N queen before, the logic of the two questions is the same, but the return value requires different, this question only requires the number of results returned
Recursive backtracking
- Place the N from the first row, and then the N after that as required (on the same row, vertical, or slash)
- If you can put n n, then the solution is +1
- If you can’t put n, you can backtrack forward one by one to update where n was placed
/ * *
* @param {number} n
* @return {number}
* /
var totalNQueens = function(n) {
let _result = 0.
tmp = []
dfs(tmp)
function dfs(tmp) {
if (tmp.length === n) {
_result++
return
}
for (let i = 0; i < n; i++) {
if (isValid(tmp, i)) {
// If "can't attack each other" is satisfied, take the point first and continue to place the next Q
tmp.push(i)
dfs(tmp)
// Trace back the Q that has been placed
tmp.pop()
}
}
}
// Determine if the new location satisfies "do not attack each other"
function isValid(tmp, Ny) {
[Nx,Ny] [Nx,Ny]
let Nx = tmp.length
for (let x = 0; x < Nx; x++) {
let y = tmp[x]
// Different columns, because all rows must be in different rows, not on the diagonal.
if (y === Ny || Nx - y === x - Ny || Nx + y === x + Ny) {
return false
}
}
return true
}
return _result
}
Copy the codeBlog: Front end bookboy
Public account: front little bookboy
Every day of the daily problem, write the problem will be synchronized to the public number one day a big Lee column welcome to pay attention to the message