Last Updated : 05 Aug, 2024
Summarize
Comments
Improve
The N-Queen problem is a classic puzzle where the goal is to place N queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal.
In this article, we will learn how to solve this problem using the C++ programming language.
Example:
Consider a 4×4 chessboard. The goal is to place 4 queens on the board such that no two queens can attack each other.
Input:
Solution:
To solve the N-Queen problem, we primarily use the Backtracking technique. Let’s discuss the approach and provide a C++ solution.
N Queen Problem usingBacktracking in C++
To solve N-Queen Problem we first place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and returnfalse.
Approach
- Start with an N x N board initialized to all zeros, where N is the number of queens and the size of the board.
- Define a function isSafe(board, row, col) to check if a queen can be placed at board[row][col] to ensure no other queens are in the same column, upper left diagonal, or upper right diagonal.
- Define a function solveNQueens(board, row) to attempt placing queens on the board row by row.
- If all queens are placed successfully (base case: row == N), return true.
- For each column in the current row:
- Check if placing a queen at board[row][col] is safe using isSafe().
- If safe, place the queen (board[row][col] = 1).
- Recur to place the next queen (solveNQueens(board, row + 1)).
- If placing the queen leads to a solution, return true.
- If not, remove the queen (board[row][col] = 0) and try the next column.
- If the queen cannot be placed in any column in the current row, return false.
- Print the solution if found, otherwise indicate no solution exists.
Below is the recursive tree of the above approach:
C++ Program to Solve N-Queen Problem using Backtracking
The following C++ program demonstrates how to solve the N-Queen problem using backtracking.
// C++ program to solve N Queen Problem using backtracking#include <iostream>#define N 4using namespace std;// A utility function to print solutionvoid printSolution(int board[N][N]){ for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) if (board[i][j]) cout << "Q "; else cout << ". "; cout << "\n"; }}// A utility function to check if a queen can// be placed on board[row][col]. Note that this// function is called when "col" queens are// already placed in columns from 0 to col -1.// So we need to check only left side for// attacking queensbool isSafe(int board[N][N], int row, int col){ int i, j; // Check this row on left side for (i = 0; i < col; i++) if (board[row][i]) return false; // Check upper diagonal on left side for (i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i][j]) return false; // Check lower diagonal on left side for (i = row, j = col; j >= 0 && i < N; i++, j--) if (board[i][j]) return false; return true;}// A recursive utility function to solve N// Queen problembool solveNQUtil(int board[N][N], int col){ // base case: If all queens are placed // then return true if (col >= N) return true; // Consider this column and try placing // this queen in all rows one by one for (int i = 0; i < N; i++) { // Check if the queen can be placed on // board[i][col] if (isSafe(board, i, col)) { // Place this queen in board[i][col] board[i][col] = 1; // recur to place rest of the queens if (solveNQUtil(board, col + 1)) return true; // If placing queen in board[i][col] // doesn't lead to a solution, then // remove queen from board[i][col] board[i][col] = 0; // BACKTRACK } } // If the queen cannot be placed in any row in // this column col then return false return false;}// This function solves the N Queen problem using// Backtracking. It mainly uses solveNQUtil() to// solve the problem. It returns false if queens// cannot be placed, otherwise, return true and// prints placement of queens in the form of 1s.// Please note that there may be more than one// solutions, this function prints one of the// feasible solutions.bool solveNQ(){ int board[N][N] = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}; if (solveNQUtil(board, 0) == false) { cout << "Solution does not exist"; return false; } printSolution(board); return true;}// Driver program to test above functionint main(){ solveNQ(); return 0;}
Output
. . Q . Q . . . . . . Q . Q . .
Time Complexity:O(N!), where N is the number of queens. This is because in the worst case, the algorithm tries all possible placements.
Auxiliary Space:O(N2) for the board.
Further Optimization in isSafe() Function
The isSafe() function can be optimized by using additional arrays to keep track of the columns and diagonals under attack by any queen. This reduces the number of checks needed for each placement.
Optimized Approach:
- Use three additional arrays: col[], diag1[], and diag2[] to keep track of the columns and diagonals.
- Update these arrays when placing or removing a queen.
Below is the implementation of above optimized approach.
// C++ program to solve N Queen Problem using backtracking#include <iostream>using namespace std;#define N 4// ld is an array where its indices indicate row-col+N-1// (N-1) is for shifting the difference to store negative// indicesint ld[30] = {0};// rd is an array where its indices indicate row+col// and used to check whether a queen can be placed on// right diagonal or notint rd[30] = {0};// Column array where its indices indicates column and// used to check whether a queen can be placed in that// row or not*/int cl[30] = {0};// A utility function to print solutionvoid printSolution(int board[N][N]){ for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cout << " " << (board[i][j] == 1 ? "Q" : ".") << " "; cout << endl; }}// A recursive utility function to solve N// Queen problembool solveNQUtil(int board[N][N], int col){ // Base case: If all queens are placed // then return true if (col >= N) return true; // Consider this column and try placing // this queen in all rows one by one for (int i = 0; i < N; i++) { // Check if the queen can be placed on // board[i][col] // To check if a queen can be placed on // board[row][col].We just need to check // ld[row-col+n-1] and rd[row+coln] where // ld and rd are for left and right // diagonal respectively if ((ld[i - col + N - 1] != 1 && rd[i + col] != 1) && cl[i] != 1) { // Place this queen in board[i][col] board[i][col] = 1; ld[i - col + N - 1] = rd[i + col] = cl[i] = 1; // Recur to place rest of the queens if (solveNQUtil(board, col + 1)) return true; // If placing queen in board[i][col] // doesn't lead to a solution, then // remove queen from board[i][col] board[i][col] = 0; // BACKTRACK ld[i - col + N - 1] = rd[i + col] = cl[i] = 0; } } // If the queen cannot be placed in any row in // this column col then return false return false;}// This function solves the N Queen problem using// Backtracking. It mainly uses solveNQUtil() to// solve the problem. It returns false if queens// cannot be placed, otherwise, return true and// prints placement of queens in the form of 1s.// Please note that there may be more than one// solutions, this function prints one of the// feasible solutions.bool solveNQ(){ int board[N][N] = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}; if (solveNQUtil(board, 0) == false) { cout << "Solution does not exist"; return false; } printSolution(board); return true;}// Driver program to test above functionint main(){ solveNQ(); return 0;}
Output
. . Q . Q . . . . . . Q . Q . .
Time Complexity:O(N!)
Auxiliary Space:O(N)
mishraaabcf9
Improve
Previous Article
Sum of array using pointer arithmetic
Next Article
Knight’s Tour Problem in C++
