- “This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
51. The N queens
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.
1. Topic analysis
According to the question, N pieces are placed on an N by N rectangular board, one for each row, one for each column, and one for each slash;
2. How to solve the problem
We can think of it this way, taking 4*4 as an example:
1, in each line in turn placed pieces, but only one piece can be placed at a time, such as the first line: respectively placed a piece in the 0,1,2,3 columns, the second line from 0,1,2,3 columns placed a piece, and so on;
2. After placing each piece, the total number of pieces is reduced by one;
3, when placing the chess pieces, judge whether to meet the requirements of the topic. If it meets the requirements of placing the next line, it does not meet the requirements of traversing the next position.
4. Place each row recursively
5. How to judge whether the placed piece is on the column and slash line of the previous piece? Section 3 Explanation
Third, code writing ideas and details
How to determine whether the placed piece is on the column and slash of the previous piece?
Because of the way of placing each row, there is no need to consider the row repetition. When placing each row, the position of the column placed is recorded, and the array is adDR_ROW_COL_ [n]. Col ==addr_row_col_[I]; col==addr_row_col_[I]; Can. So how do you know what a slash is
If you don’t understand, you can draw it.
And then the comments in the code are the little details that I encountered the error.
class Solution {
public:
void solve_n(vector<vector<string>>&_s,vector<string> & _ss,string & _sss,int _row,int _col,int Leftover,int addr_row_col_[]){//Leftover chess pieces
if(Leftover==0) {// Return the remaining pieces with zero
_s.push_back(_ss);
//cout<<"* *"<
return;
}
//cout<<Leftover<<endl;
bool b=false;
while(_col<(_row+Leftover)){
// Check whether it exists in addr_row_col_ and whether it is on the diagonal of the previous addr_ROW_col_ [_ROW-1] line
// Not only the diagonals on the top line are all diagonals
// Note that the value of addr_row_col_ is recovered after recursion, this is important ！！！！！！！
// Backtracking must restore some values to the default values. There is also a _col++ string that exceeds the boundary, and then _sss[Q]
If (_col==_row+Leftover) break;
_col++;
for(int j=0; j<=_row; j++){// Only judge the result of the first N rows
if(_col==addr_row_col_[j]-(_row-j)||_col==addr_row_col_[j]+_row-j){
b=true;
break;
}
if(_col==addr_row_col_[j]){
b=true;
break; }}if(b) {
b=false;
continue;
}
if(_col==_row+Leftover) break;// Place _col outside the checkerboard
addr_row_col_[_row]=_col;// Record the col position of each row
_sss[_col]='Q';// Modify the string
//cout<<_col<<" "<<_sss<
_ss.push_back(_sss);// Add a string to the end
_sss[_col]='. ';// Change back to the checkerboard
solve_n(_s,_ss,_sss,_row+1.- 1,Leftover- 1,addr_row_col_);// Assume that the initial chess position is in the -1 column
addr_row_col_[_row]=2 -;// Restore addr_ROW_col_ at this location
_ss.pop_back(a);// Pops up the row added at this time
}
return;
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> s;
vector<string> ss;
string sss;
int row=0; / / line
//int col=-1; / / column
int addr_row_col[n];
for(int i=0; i<n; ++i){ sss.push_back('. ');// Initializes the SSS string
addr_row_col[i]=2 -;// Initialize the placement position
}
solve_n(s,ss,sss,row,- 1,n,addr_row_col);// recursion -- backtrack, assuming the initial piece position is in -- 1 column
returns; }};Copy the code