The \(n\)-queens puzzle is the problem of placing \(n\) queens on an \(n \times n\) chessboard such that no two queens attack each other, which means no two queens share the same row, column, or diagonal. Given an integer \(n\), return all distinct solutions to the \(n\)-queens puzzle. Each solution contains a distinct board configuration of the \(n\)-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
This problem can be solved recursively: for every free grid in a row, resursively check possible solutions in the row below, until (1) there is no free grid in the next row(failure) or (2) there is no row below(current row is the last row, sucess).
For any grid in the table, if the value of the grid is true, then this grid is free. Otherwise, it is not free. In order to guaranttee there is no two queens in the same row, column or diagonal, after picking up a grid, set the value of grids in the same row, column or diagonal to be false. After checking the remaining rows, the states of grids set in this step should be restored.
Following is my C++ implementation. Functions checkRow() and setGrid() are very tricky.
class Solution {
public:
vector<vector > solveNQueens(int n) {
vector<vector > grid;
vector row_bool;
for(int j=0;j<n;++j)
row_bool.push_back(true);
for(int i=0;i<n;++i)
grid.push_back(row_bool);
vector<vector<pair<int,int> > > points;
vector<pair<int,int> > path;
checkRow(grid,path,points,n,0);
vector<vector > ret;
for(int i=0;i<points.size();++i) {
vector trace;
string row_trace;
for(int i=0;i<n;++i)
row_trace+=".";
for(int i=0;i<n;++i)
trace.push_back(row_trace);
for(auto& pt: points[i])
trace[pt.first][pt.second]='Q';
ret.push_back(trace);
}
return ret;
}
// Recrusively try a solution row-by-row
void checkRow(vector<vector >& grid, vector<pair<int,int> >& path, vector<vector<pair<int,int> > >& trace, int n, int row) {
if(row==n && path.size()==n) {
trace.push_back(path); // store the solution
return;
}
vector avail_cols;
findAvailGrids(grid,avail_cols,row);
if(avail_cols.empty())
return;
for(auto& col:avail_cols) {
path.push_back(pair<int,int>(row,col));
vector<pair<int,int> > points;
setGrid(grid,points,row,col,false);
checkRow(grid,path,trace,n,row+1);
setGrid(grid,points,true); // recover the state of table
path.pop_back();
}
}
// Find available grids in a row
void findAvailGrids(vector<vector >& grid,vector& vec,int row) {
for(int j=0;j<grid[0].size();++j) {
if(grid[row][j])
vec.push_back(j);
}
}
// Set grids to val based on the coordinate of a given grid
void setGrid(vector<vector >& grid,vector<pair<int,int> >& points, int row, int col, bool val) {
const int n=grid.size();
// set grids in the same row and column
for(int i=0;i<n;++i) {
if(grid[i][col]!=val)
points.push_back(pair<int,int>(i,col));
if(grid[row][i]!=val)
points.push_back(pair<int,int>(row,i));
grid[i][col]=val;
grid[row][i]=val;
}
// set diagnal grids
int x=row;
int y=col;
while(x>=0 && y>=0) {
if(grid[x][y]!=val)
points.push_back(pair<int,int>(x,y));
grid[x][y]=val;
x--;y--;
}
x=row+1; y=col+1;
while(x<n && y<n) {
if(grid[x][y]!=val)
points.push_back(pair<int,int>(x,y));
grid[x][y]=val;
x++;y++;
}
x=row-1; y=col+1;
while(x>=0 && y<n) {
if(grid[x][y]!=val)
points.push_back(pair<int,int>(x,y));
grid[x][y]=val;
x--;y++;
}
x=row+1; y=col-1;
while(x<n && y>=0) {
if(grid[x][y]!=val)
points.push_back(pair<int,int>(x,y));
grid[x][y]=val;
x++;y--;
}
}
// Set grids to val based on a collection of grids
void setGrid(vector<vector >& grid, vector<pair<int,int> >& points, bool val) {
for(auto& pt:points)
grid[pt.first][pt.second]=val;
}
// Print all solutions, test only
void printSolution(vector<vector >& trace) {
cout<<"["<<endl;
for(int i=0;i<trace.size();++i) {
cout<<" [\""<<trace[i][0]<<"\","<<endl;
for(int j=1;j<trace[i].size();++j) {
if(j!=trace[i].size()-1)
cout<<" \""<<trace[i][j]<<"\","<<endl;
else
cout<<" \""<<trace[i][j]<<"\"]"<<endl;
}
cout<<endl;
}
}
// Print the values of all grids in the table, test only
void printGrid(vector<vector >& grid,int row,int col,string str) {
cout<<"("<<row<<","<<col<<")"<<str<<":"<<endl;
for(int i=0;i<grid.size();++i) {
for(int j=0;j<grid[0].size();++j) {
if(grid[i][j])
cout<<"T ";
else
cout<<"F ";
}
cout<<endl;
}
cout<<endl;
}
};
</pre>