|
N-Queen problem involves placing N queens on an N×N chessboard such that no two queens threaten each other. This means no two queens share the same row, column, or diagonal.
In this article, we will learn to solve the N queen problem using the Branch and Bound technique which provides an efficient method compared to simple backtracking.
Example:
Input:
N = 8
Output:
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 The backtracking Algorithm for N-Queen is already discussed here.
The idea behind the Branch and Bound approach is to enhance the backtracking method by pruning the search space early. In backtracking, we explore each possibility and backtrack when we hit a dead end. However, in Branch and Bound, we can avoid exploring certain branches of the search tree altogether if we know they lead to invalid solutions.
Approach:- Initialize the Board:
- Create a 2D array to represent the board.
- Initialize arrays to track columns and diagonals.
- Check Safety:
- Create a function isSafe to check if a position is safe by ensuring the current row, and both diagonals are free of other queens.
- Recursive Backtracking:
- Implement the recursive function solve that places queens column by column.
- For each column, try placing a queen in each row and check if it’s safe.
- If placing the queen is safe, mark the position and recursively try to place the next queen in the next column.
- If placing the queen is not safe, backtrack and try the next row.
- Print Solution:
- If a solution is found, print the board.
C++ Program to Solve N-Queen ProblemThe below program implements the above approach to solve N-Queen Problem in C++.
C++
// C++ program to solve N Queen problem using Branch and
// Bound approach
#include <iostream>
#include <vector>
using namespace std;
int N;
// Function to print the solution
void printSolution(vector<vector<int> >& board)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// Print each cell of the board
cout << board[i][j] << " ";
}
// Print new line after each row
cout << endl;
}
}
// Optimized isSafe function to check if current row, left
// diagonal or right diagonal contains any queen
bool isSafe(int row, int col, vector<bool>& rows,
vector<bool>& leftDiagonals,
vector<bool>& rightDiagonals)
{
// Check if the current row, left diagonal, or right
// diagonal is already occupied by a queen
if (rows[row] || leftDiagonals[row + col]
|| rightDiagonals[col - row + N - 1]) {
// If occupied, it's not safe to place the queen
return false;
}
// If not occupied, it's safe to place the queen
return true;
}
// Recursive function to solve N-Queen Problem
bool solve(vector<vector<int> >& board, int col,
vector<bool>& rows, vector<bool>& leftDiagonals,
vector<bool>& rightDiagonals)
{
// Base Case: If all Queens are placed
if (col >= N) {
// All queens are placed successfully
return true;
}
// Consider this column and try placing queen in all
// rows one by one
for (int i = 0; i < N; i++) {
if (isSafe(i, col, rows, leftDiagonals,
rightDiagonals)) {
// Mark the row and diagonals as occupied
rows[i] = true;
leftDiagonals[i + col] = true;
rightDiagonals[col - i + N - 1] = true;
// Place the queen
board[i][col] = 1;
// Recur to place rest of the queens
if (solve(board, col + 1, rows, leftDiagonals,
rightDiagonals)) {
// If placing the queen in the next column
// leads to a solution, return true
return true;
}
// Backtracking: Unmark the row and diagonals,
// and remove the queen
rows[i] = false;
leftDiagonals[i + col] = false;
rightDiagonals[col - i + N - 1] = false;
// Remove the queen
board[i][col] = 0;
}
}
// If no place is safe in the current column, return
// false
return false;
}
int main()
{
// Taking input from the user
cout << "Enter the number of rows for the square "
"board: ";
// Read the size of the board
cin >> N;
// Board of size N*N
// Initialize the board with all cells as 0 (no queens
// placed)
vector<vector<int> > board(N, vector<int>(N, 0));
// Arrays to tell which rows and diagonals are occupied
// Initialize the row markers
vector<bool> rows(N, false);
// Initialize the left diagonal markers
vector<bool> leftDiagonals(2 * N - 1, false);
// Initialize the right diagonal markers
vector<bool> rightDiagonals(2 * N - 1, false);
// Start solving from the first column
bool ans = solve(board, 0, rows, leftDiagonals,
rightDiagonals);
if (ans) {
// If a solution is found, print the solution board
printSolution(board);
}
else {
// If no solution exists, print a message
cout << "Solution does not exist\n";
}
return 0;
}
Output
Enter the number of rows for the square board: 8
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 Time Complexity: The time complexity of the solver algorithm is O(N!), where N is the number of rows and columns in the square board. This is because for each column, the algorithm tries to place a queen in each row and then recursively tries to place the queens in the remaining columns. The number of possible combinations of queen placements in the board is N! since there can be only one queen in each row and each column.
Space Complexity: The space complexity of the solver algorithm is O(N^2), where N is the number of rows and columns in the square board. This is because we are using a 2D vector to represent the board, which takes up N^2 space. Additionally, we are using three boolean arrays to keep track of the occupied rows and diagonals, which take up 2N-1 space each. Therefore, the total space complexity is O(N^2 + 6N – 3), which is equivalent to O(N^2).
|
C++ Program to Implement B+ Tree
C++ Program to Implement Binomial Heap
Reflection in C++
Point in Polygon in C++