Q23:The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
Example:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as
shown above
Solution:
class Solution {
public:
vector<vector<string>> ret;
bool is_valid(vector<string> &board, int row, int col){
// check col
for(int i=row;i>=0;--i)
if(board[i][col] == 'Q') return false;
// check left diagonal
for(int i=row,j=col;i>=0&&j>=0;--i,--j)
if(board[i][j] == 'Q') return false;
//check right diagonal
for(int i=row,j=col;i>=0&&j<board.size();--i,++j)
if(board[i][j] == 'Q') return false;
return true;
}
void dfs(vector<string> &board, int row){
// exit condition
if(row == board.size()){
ret.push_back(board);
return;
}
// iterate every possible position
for(int i=0;i<board.size();++i){
if(is_valid(board,row,i)){
// make decision
board[row][i] = 'Q';
// next iteration
dfs(board,row+1);
// back-tracking
board[row][i] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
if(n <= 0) return {{}};
vector<string> board(n,string(n,'.'));
dfs(board,0);
return ret;
}
};
Explantion:
>This C++ code is an implementation of the N-Queens problem using backtracking.
The N-Queens problem is a classic chess problem where you need to place N
queens on an N×N chessboard in such a way that no two queens threaten each
other. The code uses a recursive approach to find all possible solutions.
Here's a breakdown of the code:
>is_valid Function:
This function checks if it's valid to place a queen at a given position
(row, col) on the chessboard. It checks for conflicts in the same column,
left diagonal, and right diagonal.
>dfs Function:
dfs stands for Depth-First Search, and it's a recursive function that
explores the possibilities of placing queens on the board.
It starts from the first row and iterates through each column, checking if
placing a queen at that position is valid.
If valid, it updates the board, moves to the next row (recursive call), and
continues the process.
If not valid, it backtracks by undoing the queen placement and continues the
iteration.
>solveNQueens Function:
Initializes an empty vector ret to store the solutions.
Checks if n is less than or equal to 0, and if so, returns an empty vector
(no solution).
Creates a chessboard represented by a vector of strings (board) initially
filled with dots (.).
Calls the dfs function to find all solutions starting from the first row.
Returns the vector containing all valid solutions.
In simple terms, the code explores all possible arrangements of queens on
the chessboard, making sure that no two queens threaten each other.
It uses backtracking to try different positions and efficiently find all
solutions. The final result is a vector of vectors, where each inner vector
represents a valid solution to the N-Queens problem.