The n ， queen problem studies how to place n ， queens in n × N's chessboard, and the Queens can't attack each other.
The figure above is a solution to the 8 queen problem.
Given an integer n, returns the number of different solutions of Queen n.
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.."] ]
Tips:
- Queen, yes Chess The chess piece in means king My wife. The queen only does one thing, that is“ Eat son ”. When she met a piece she could eat, she rushed up and ate it. Of course, she can walk one or seven steps horizontally, vertically and obliquely, and can go forward or backward. (quoted from) Baidu Encyclopedia - Queen )
Intuitive ideas
This problem is a classic problem. It is very important to feel the elegance of the solution.
The first idea is to use brute force method, which means to generate all possible situations in which N queens are placed on the chessboard, and check whether it is guaranteed that no Queens can attack each other. This means that we must consider the time complexity (NNO ^ HC)}.
Here are two useful programming concepts.
The first is called constraint programming
Its basic meaning is to add restrictions after placing each queen. When a queen is placed on the chessboard, the current row, column and the corresponding two diagonals are excluded immediately. This process passes constraints, which helps to reduce the number of situations that need to be considered.
The second is called backtracking
Let's imagine that when several queens are placed on the chessboard without attacking each other. But the scheme chosen is not optimal, because the next queen cannot be placed. What should we do now? to flash back. It means to take a step back to change the position where the queen was last placed and then put it down. If you still can't, go back.
Method 1: backtracking
Before building the algorithm, let's consider two useful details.
There can be only one queen in a row and only one queen in a column.
This means that there is no need to consider all the squares on the chessboard. Just cycle by column.
For all primary diagonals, there is row number + column number = constant, and for all secondary diagonals, there is row number column number = constant
This allows us to mark diagonals that are already under attack and check whether a square (row number, column number) is in the attack position.
Now you can write the backtrace function backtrack(row = 0)
-
Start with the first row = 0
-
Loop columns and try to place queens in each column
-
If the row, column is not within the attack range
- Place the queen on the (row, column) grid.
- Exclude the positions of corresponding rows, columns and two diagonals.
- If all rows are considered, row == N
- It means we found a solution
- Else
- Continue to consider the next queen to place backtrack(row + 1)
- Backtracking: remove the queen in the (row, column) box
-
The following is a direct implementation of the above algorithm.
- Java
- Python
class Solution {
public boolean is_not_under_attack(int row, int col, int n,
int [] rows,
int [] hills,
int [] dales) {
int res = rows[col] + hills[row - col + 2 * n] + dales[row + col];
return (res == 0) ? true : false;
}
public int backtrack(int row, int count, int n,
int [] rows,
int [] hills,
int [] dales) {
for (int col = 0; col < n; col++) {
if (is_not_under_attack(row, col, n, rows, hills, dales)) {
// place_queen
rows[col] = 1;
hills[row - col + 2 * n] = 1; // "hill" diagonals
dales[row + col] = 1; //"dale" diagonals
<span class="hljs-comment">// if n queens are already placed</span>
<span class="hljs-keyword">if</span> (row + <span class="hljs-number">1</span> == n) count++;
<span class="hljs-comment">// if not proceed to place the rest</span>
<span class="hljs-keyword">else</span> count = backtrack(row + <span class="hljs-number">1</span>, count, n,
rows, hills, dales);
<span class="hljs-comment">// remove queen</span>
rows[col] = <span class="hljs-number">0</span>;
hills[row - col + <span class="hljs-number">2</span> * n] = <span class="hljs-number">0</span>;
dales[row + col] = <span class="hljs-number">0</span>;
}
}
<span class="hljs-keyword">return</span> count;
}
public int totalNQueens(int n) {
int rows[] = new int[n];
// "hill" diagonals
int hills[] = new int[4 * n - 1];
// "dale" diagonals
int dales[] = new int[2 * n - 1];
<span class="hljs-keyword">return</span> backtrack(<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, n, rows, hills, dales);
}
}
class Solution:
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
def is_not_under_attack(row, col):
return not (rows[col] or hills[row - col] or dales[row + col])<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">place_queen</span><span class="hljs-params">(row, col)</span>:</span> rows[col] = <span class="hljs-number">1</span> hills[row - col] = <span class="hljs-number">1</span> <span class="hljs-comment"># "hill" diagonals</span> dales[row + col] = <span class="hljs-number">1</span> <span class="hljs-comment"># "dale" diagonals</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">remove_queen</span><span class="hljs-params">(row, col)</span>:</span> rows[col] = <span class="hljs-number">0</span> hills[row - col] = <span class="hljs-number">0</span> <span class="hljs-comment"># "hill" diagonals</span> dales[row + col] = <span class="hljs-number">0</span> <span class="hljs-comment"># "dale" diagonals</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">backtrack</span><span class="hljs-params">(row = <span class="hljs-number">0</span>, count = <span class="hljs-number">0</span>)</span>:</span> <span class="hljs-keyword">for</span> col <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">if</span> is_not_under_attack(row, col): place_queen(row, col) <span class="hljs-keyword">if</span> row + <span class="hljs-number">1</span> == n: count += <span class="hljs-number">1</span> <span class="hljs-keyword">else</span>: count = backtrack(row + <span class="hljs-number">1</span>, count) remove_queen(row, col) <span class="hljs-keyword">return</span> count rows = [<span class="hljs-number">0</span>] * n hills = [<span class="hljs-number">0</span>] * (<span class="hljs-number">2</span> * n - <span class="hljs-number">1</span>) <span class="hljs-comment"># "hill" diagonals</span> dales = [<span class="hljs-number">0</span>] * (<span class="hljs-number">2</span> * n - <span class="hljs-number">1</span>) <span class="hljs-comment"># "dale" diagonals</span> <span class="hljs-keyword">return</span> backtrack()
Complexity analysis
- Time complexity: O(N!)\mathcal{O}(N!)O(N!). There are N possible methods to place the first queen. The method to place two queens should not exceed N (N - 2), the method to place three queens should not exceed N(N - 2)(N - 4), and so on. Overall, the time complexity is O(N!)\mathcal{O}(N!)O(N!) .
- Space complexity: O(N)\mathcal{O}(N)O(N) Diagonal and row information needs to be saved.
Method 2: using bitmap backtracking
If you are in an interview - use method 1.
The following algorithm has the same time complexity O(N!)\mathcal{O}(N!)O(N!). But due to the use of Bit operation , it can run faster.
Thanks to the proposer of this algorithm takaken.
In order to understand the algorithm, the following code is explained step by step.
- Java
- Python
class Solution {
public int backtrack(int row, int hills, int next_row, int dales, int count, int n) {
/**
row: Line number of the currently placed queen
hills: Main diagonal occupancy [1 = occupied, 0 = unoccupied]
next_row: When the next row is occupied [1 = occupied, 0 = unoccupied]
dales: Sub diagonal occupancy [1 = occupied, 0 = unoccupied]
count: Number of all feasible solutions
*/
<span class="hljs-comment">// All columns of the chessboard can be placed</span>
<span class="hljs-comment">// That is, the bitwise representation is n '1's</span>
<span class="hljs-comment">// bin(cols) = 0b1111 (n = 4), bin(cols) = 0b111 (n = 3)</span>
<span class="hljs-comment">// [1 = placeable]</span>
<span class="hljs-keyword">int</span> columns = (<span class="hljs-number">1</span> << n) - <span class="hljs-number">1</span>;
<span class="hljs-keyword">if</span> (row == n) <span class="hljs-comment">// If n queens have been placed</span>
count++; <span class="hljs-comment">// Cumulative feasible solution</span>
<span class="hljs-keyword">else</span> {
<span class="hljs-comment">// Available columns for the current row</span>
<span class="hljs-comment">// ! Indicates the meaning of 0 and 1. For the variable hills, next_row and dales have the opposite meaning</span>
<span class="hljs-comment">// [1 = unoccupied, 0 = occupied]</span>
<span class="hljs-keyword">int</span> free_columns = columns & ~(hills | next_row | dales);
<span class="hljs-comment">// Find the column where the next queen can be placed</span>
<span class="hljs-keyword">while</span> (free_columns != <span class="hljs-number">0</span>) {
<span class="hljs-comment">// free_ The first bit of columns is' 1 '</span>
<span class="hljs-comment">// In this column we place the current queen</span>
<span class="hljs-keyword">int</span> curr_column = - free_columns & free_columns;
<span class="hljs-comment">// Place queen</span>
<span class="hljs-comment">// And exclude the corresponding columns</span>
free_columns ^= curr_column;
count = backtrack(row + <span class="hljs-number">1</span>,
(hills | curr_column) << <span class="hljs-number">1</span>,
next_row | curr_column,
(dales | curr_column) >> <span class="hljs-number">1</span>,
count, n);
}
}
<span class="hljs-keyword">return</span> count;
}
public int totalNQueens(int n) {
return backtrack(0, 0, 0, 0, 0, n);
}
}
class Solution:
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
def backtrack(row = 0, hills = 0, next_row = 0, dales = 0, count = 0):
"""
:type row: Line number of the currently placed queen
:type hills: Main diagonal occupancy [1 = Occupied, 0 = Unoccupied]
:type next_row: When the next line is occupied [1 = Occupied, 0 = Unoccupied]
:type dales: Sub diagonal occupancy [1 = Occupied, 0 = Unoccupied]
:rtype: Number of all feasible solutions
"""
if row == n: # If n queens have been placed
count += 1 # Cumulative feasible solution
else:
# Available columns for the current row
# ! Indicates the meaning of 0 and 1. For the variable hills, next_row and dales have the opposite meaning
# [1 = unoccupied, 0 = occupied]
free_columns = columns & ~(hills | next_row | dales)<span class="hljs-comment"># Find the column where the next queen can be placed</span> <span class="hljs-keyword">while</span> free_columns: <span class="hljs-comment"># free_ The first bit of columns is' 1 '</span> <span class="hljs-comment"># In this column we place the current queen</span> curr_column = - free_columns & free_columns <span class="hljs-comment"># Place queen</span> <span class="hljs-comment"># And exclude the corresponding columns</span> free_columns ^= curr_column count = backtrack(row + <span class="hljs-number">1</span>, (hills | curr_column) << <span class="hljs-number">1</span>, next_row | curr_column, (dales | curr_column) >> <span class="hljs-number">1</span>, count) <span class="hljs-keyword">return</span> count <span class="hljs-comment"># All columns of the chessboard can be placed</span> <span class="hljs-comment"># That is, the bitwise representation is n '1's</span> <span class="hljs-comment"># bin(cols) = 0b1111 (n = 4), bin(cols) = 0b111 (n = 3)</span> <span class="hljs-comment"># [1 = placeable]</span> columns = (<span class="hljs-number">1</span> << n) - <span class="hljs-number">1</span> <span class="hljs-keyword">return</span> backtrack()
Complexity analysis
- Time complexity: O(N!)\mathcal{O}(N!)O(N!).
- Space complexity: O(N)\mathcal{O}(N)O(N)