In this problem, we are solving the N-Queens problem where the goal is to place N queens on an N×N chessboard so that no two queens can attack each other. The steps to solve this problem are as follows:
This function checks if placing a queen at a given position (row, col) is safe. It verifies three directions for conflicts with other queens: Upper diagonal on the left side. Left side. Lower diagonal on the left side. If any of these directions have a queen, it returns false. Otherwise, it returns true. Define Recursive Function solve:
This function attempts to place queens column by column. If the current column (col) is equal to the board size (n), it indicates all queens are placed successfully, and the current board configuration is added to the answer list (ans). For each row in the current column, it checks if placing a queen is safe using the isSafe1 function. If safe, it places a queen at board[row][col], recursively calls solve for the next column, and then removes the queen to backtrack.
This function initializes the board and calls the solve function. It creates an empty board with all positions set to '.', indicating no queens are placed. It calls the solve function starting from the first column. Finally, it returns the list of all valid board configurations. Detailed Steps:
Move upwards diagonally (row--, col--) and check for any queen. Check Left Side: Move left horizontally (col--) and check for any queen. Check Lower Diagonal: Move downwards diagonally (row++, col--) and check for any queen. Return true if no conflicts are found in the above directions. Recursive Function solve:
If col equals n, all queens are placed correctly. Add the current board configuration to ans and return. Recursive Case: For each row in the current column, check if placing a queen is safe using isSafe1. If safe, place the queen, call solve recursively for the next column, and backtrack by removing the queen. Main Function solveNQueens:
Call solve starting from the first column (0). Return the list of all valid configurations.
Loading component...
Loading component...
Main Function is not defined.
public static void solve(int col, vector<string> &board, vector<vector<string>>&ans, int n){
if(col == n){
ans.push_back(board);
return;
}
for(int row = 0; row< n; row++){
boolean safe = issafe1(row ,col, board ,n);
if(safe){
board[row][col] = 'Q';
solve(col+1,board,ans,n);
board[row][col]= '.';
}
}
}//function end
public static boolean issafe1(int row , int col, vector<string> board, int n){
int duprow = row;
int dupcol = col;
while(row >= 0 ){
while(col >= 0 ){
if(board[row][col] == 'Q'){
return false;
}
col--;
row--;
}
}
col = dupcol;
row = duprow;
while (col>=0){
if(board[row][col] == 'Q'){
return false;
}
col--;
}
row = duprow;
col =dupcol;
while(row < n ){
while(col > 0 ){
if(board[row][col] == 'Q'){
return false;
}
row++;
col--;
}
}
return true;
}//function end