This is the 18th day of my participation in the August Genwen Challenge.More challenges in August
preface
The queen is shown as follows:
The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other.
Given an integer n, return all the different solutions to the **n queen problem.
Each solution contains a different chess placement scheme for the N-queen problem, in which ‘Q’ and ‘.’ represent queens and slots, respectively.
Example 1:
Input: n = 4 output: [[". Q.. ", "... Q ", "Q...", ".. Q. "], [".. Q. ", "Q...", "... Q ", ". Q.. "]] : as shown in the above, 4 queen problems exist two different solutions.Copy the codeExample 2:
Input: n = 1 Output: [["Q"]Copy the codeTip:
1 <= n <= 9- Queens cannot attack each other, that is, no two queens can be in the same row, row, or diagonal.
A, thinking
N queen is a very classic backtracking algorithm problem, worth doing!
Tips: This problem and force buckle 37 – solving sudoku is very similar, the idea is almost the same, interested can also take a look at the problem.
There are three very important messages in the title:
The queenThey can’t be in the same lineThe queenThey can’t be in the same columnThe queenThey can’t be on the same diagonal
The general idea is divided into the following parts:
- Use three two-dimensional arrays to store the occupancy of selected points in rows and slashes
- Because there’s going to be one in every row
The queen, soOnly elements in the current row are iterated through in the current recursion(pruning)
Graphic algorithm
In the implementation process, the most stomped place is to store slash occupancy, so the following will mainly describe how to store row, column and slash occupancy.
As for recursion, the idea is not too hard, and the simplified pseudocode looks like this:
public void dfs(List<List<String>> ret, int count) {
if(count == len) {add the result to retreturn;
}
// Each row will have a queen, so it only needs to be traversed n times
for (int i=0; i<len; i++) {
// Determine whether the queen can be placed
if(! rowFlags[count][i] && ! colFlags[count][i] && slashFlags[count][i] ==0) {update the occupancy// recurse downward
dfs(ret, count+1); Restore the placeholder}}}Copy the codeBoolean [][] positions; // Select element Boolean [][] rowFlags; Boolean [][] colFlags; Int [][] slashFlags; // Slash usage
As shown in the figure below, when you select the first row and second column as the first element, that’s positions[0][1] = true
Row and column usage
Row and column occupancy can be used in two waysA two-dimensional Boolean arrayTo store
In this case, rowFlags[0][I] is true, and colFlags[I][1] is true
Slash occupation
I also started with a two-dimensional Boolean array to store slash occupancy, but I found that there was interference
As shown in the figure below, there will be overlap between [3, 4] and [4, 1], and the overlap will be set to false when backtracking upward
Yellow indicates selected elements and light indicates occupied slash cases
So slash occupancy can be stored as a two-dimensional int array, occupancy +1, backtracking -1
In this case, slashFlags[1][0], slashFlags[0][1], slashFlags[1][2], slashFlags[2][3], slashFlags[3][4] are all 1
Second, the implementation
The implementation code
The implementation code is consistent with the idea (but the code is a little long TNT ~).
boolean[][] positions;
boolean[][] rowFlags; / / line
boolean[][] colFlags; / / column
int[][] slashFlags; / / slash
int len;
/** * The row, column, and slash states need to be stored separately, otherwise they will affect each other *@param n
* @return* /
public List<List<String>> solveNQueens(int n) {
List<List<String>> ret = new ArrayList<>();
rowFlags = new boolean[n][n];
colFlags = new boolean[n][n];
slashFlags = new int[n][n];
positions = new boolean[n][n];
len = n;
dfs(ret, 0);
return ret;
}
/** * recursive */
public void dfs(List<List<String>> ret, int count) {
if (count == len) {
List<String> list = new ArrayList<>();
// Record the result
for (int i=0; i<len; i++) {
StringBuilder sb = new StringBuilder();
for (int j=0; j<len; j++) {
if (positions[i][j])
sb.append("Q");
else
sb.append(".");
}
list.add(sb.toString());
}
ret.add(list);
return;
}
// Each row will have a queen, so it only needs to be traversed n times
for (int i=0; i<len; i++) {
// Determine whether the current column can place a queen
if(! rowFlags[count][i] && ! colFlags[count][i] && slashFlags[count][i] ==0) {
/ / update
positions[count][i] = true;
updateFlags(count, i, true);
// recurse downward
dfs(ret, count+1);
positions[count][i] = false;
updateFlags(count, i, false); }}}public void updateFlags(int row, int col, boolean flag) {
/ / update
for (int i=0; i< len; i++) {
rowFlags[row][i] = flag;
}
/ / update the column
for (int i=0; i<len; i++) {
colFlags[i][col] = flag;
}
// Update the slash
int tRow = row; // Start point (slant down)
int tCol = col;
while (tRow>0 && tCol >0) {
tRow--;
tCol--;
}
// Update slant down
while (tRow<len && tCol<len) {
if (flag) {
++slashFlags[tRow][tCol];
} else if (slashFlags[tRow][tCol] > 0){
--slashFlags[tRow][tCol];
}
tRow++;
tCol++;
}
tRow = row; // Start point (oblique upward)
tCol = col;
while (tRow>0 && tCol<len-1) {
tRow--;
tCol++;
}
// Update slanted upward
while (tRow<len && tCol>-1) {
if (flag) {
++slashFlags[tRow][tCol];
} else if (slashFlags[tRow][tCol] > 0){ --slashFlags[tRow][tCol]; } tRow++; tCol--; }}Copy the codeThe test code
public static void main(String[] args) {
new Number51().solveNQueens(8);
}
Copy the codeThe results of
Third, summary
The next problem is Queen N II, the title is basically the same, I will optimize the idea of this paper.
Thank you to see the end, very honored to help you ~♥