Backtracking Approach
This approach rejects all further moves if the solution is declined at any step, goes back to the previous step and explores other options.
Algorithm
Let's go through the steps below to understand how this algorithm of solving the 8 queens problem using backtracking works:
- Step 1: Traverse all the rows in one column at a time and try to place the queen in that position.
- Step 2: After coming to a new square in the left column, traverse to its left horizontal direction to see if any queen is already placed in that row or not. If a queen is found, then move to other rows to search for a possible position for the queen.
- Step 3: Like step 2, check the upper and lower left diagonals. We do not check the right side because it's impossible to find a queen on that side of the board yet.
- Step 4: If the process succeeds, i.e. a queen is not found, mark the position as '1' and move ahead.
- Step 5: Recursively use the above-listed steps to reach the last column. Print the solution matrix if a queen is successfully placed in the last column.
- Step 6: Backtrack to find other solutions after printing one possible solution.
Implementation in C++
Let's go through the C++ implementation of the above-discussed approach to solve the 8 queens problem using backtracking.
//Coding Ninjas
//C++ solution to 8 queens problem using backtracking
#include <bits/stdc++.h>
using namespace std;
int countt=0;
// A function to print a solution
void print(int board[][8]){
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
cout<<board[i][j]<<" ";
}
cout<<endl;
}
cout<<"-----------------\n";
}
//Function to check whether a position is valid or not
bool isValid(int board[][8],int row,int col){
//loop to check horizontal positions
for(int i=col;i>=0;i--){
if(board[row][i])
return false;
}
int i=row,j=col;
//loop to check the upper left diagonal
while(i>=0&&j>=0){
if(board[i][j])
return false;
i--;
j--;
}
i=row;
j=col;
//loop to check the lower left diagonal
while(i<8&&j>=0){
if(board[i][j])
return false;
i++;
j--;
}
return true;
}
//function to check all the possible solutions
void ninjaQueens(int board[][8],int currentColumn){
if(currentColumn>=8)
return;
//loop to cover all the columns
for(int i=0;i<8;i++){
if(isValid(board,i,currentColumn)){
board[i][currentColumn]=1;
if(currentColumn==7){
print(board);
countt++;
}
//recursively calling the function
ninjaQueens(board,currentColumn+1);
//backtracking
board[i][currentColumn]=0;
}
}
}
int main() {
//initial board situation
int board[8][8]={{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0}};
ninjaQueens(board,0);
/* In total, 92 solutions exist for 8x8 board. This statement will verify our code*/
cout<<countt<<endl;
return 0;
}
Output: (A total of 92 solutions will exist, we are showing the last two along with the count)
Implementation in Java
Let us look at the Java code for the algorithm implementation.
//Solution to 8 queens problem using backtracking
class NinjaQueens {
int countt=0;
// A function to print a solution
void print(int board[][]){
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
System.out.print(board[i][j]+" ");
}
System.out.print("\n");
}
System.out.print("-----------------\n");
}
//Function to check whether a position is valid or not
boolean isValid(int board[][],int row,int col){
//loop to check horizontal positions
for(int i=col;i>=0;i--){
if(board[row][i]==1)
return false;
}
int i=row,j=col;
//loop to check the upper left diagonal
while(i>=0&&j>=0){
if(board[i][j]==1)
return false;
i--;
j--;
}
i=row;
j=col;
//loop to check the lower left diagonal
while(i<8&&j>=0){
if(board[i][j]==1)
return false;
i++;
j--;
}
return true;
}
//Function to check all the possible solutions
void ninjaQueens(int board[][],int currentColumn){
if(currentColumn>=8)
return;
//loop to cover all the columns
for(int i=0;i<8;i++){
if(isValid(board,i,currentColumn)){
board[i][currentColumn]=1;
if(currentColumn==7){
print(board);
countt++;
}
//recursively calling the function
ninjaQueens(board,currentColumn+1);
//backtracking
board[i][currentColumn]=0;
}
}
}
void solve(){
//initial board situation
int board[][]={{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0}};
ninjaQueens(board,0);
/* In total, 92 solutions exist for 8x8 board. This statement will verify our code*/
System.out.print("countt\n");
return;
}
public static void main(String[] args) {
NinjaQueens solution=new NinjaQueens();
solution.solve();
}
}
Output: The first solution is shown below.
Complexity Analysis
Time Complexity: O(N!), For the first column we will have N choices, then for the next column, we will have N-1 choices, and so on. Therefore the total time taken will be N*(N-1)*(N-2)...., which makes the time complexity to be O(N!).
Space Complexity: O(N^2), we can see that the initial space needed is N^2, then N^2-1, then N^2-2 and so on. Thus making the space complexity N^2N, but we don’t need all the N^2 options each time. Therefore, the overall space complexity is O(N^2).
Implementation in Python
def is_valid(board, row, col, n):
# Check if no other queen is present in the same row or diagonal
for i in range(col):
if board[i] == row or \
board[i] - i == row - col or \
board[i] + i == row + col:
return False
return True
def solve_queen(board, col, n):
# Base case: if all queens are placed, return True
if col == n:
return True
# Try placing the queen in each row of the current column
for row in range(n):
if is_valid(board, row, col, n):
board[col] = row
# Recursively place the queens in the remaining columns
if solve_queen(board, col + 1, n):
return True
# Backtrack by undoing the current move and trying the next row
board[col] = -1
# If no valid position is found, return False
return False
def print_board(board, n):
for row in range(n):
for col in range(n):
if board[col] == row:
print('Q', end=' ')
else:
print('.', end=' ')
print()
def solve_n_queens(n):
board = [-1] * n
if solve_queen(board, 0, n):
print_board(board, n)
else:
print('No solution found')
The is_valid function checks if it is safe to place a queen in a given row and column by checking that no other queen is present in the same row or diagonal. The solve_queen function recursively tries to place the queens in each column and backtracks if no valid position is found. Finally, the print_board function prints the board layout for a valid solution, and the solve_n_queens function initializes the board and starts the recursive solving process.
Optimising Time Complexity
We can optimize the 'isValid' Function and avoid checking the diagonals. The logic behind this idea is that the difference between row and column indices is constant for each diagonal, and the sum is constant for anti-diagonal.
Algorithm
- Step 1: Create a boolean array to remember which diagonal is used by now.
- Step 2: In the 'isValid' Function, check if the boolean arrays are marked true instead of checking the diagonals.
- Step 3: Return true or false accordingly.
Implementation in C++
//Coding Ninjas
//C++ solution to 8 queens problem using backtracking
#include <bits/stdc++.h>
using namespace std;
int countt=0;
//Using three boolean arrays to optimise the isValid function
bool leftDiagonal[30]={0};
bool rightDiagonal[30]={0};
bool column[30]={0};
// A function to print a solution
void print(int board[][8]){
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
cout<<board[i][j]<<" ";
}
cout<<endl;
}
cout<<"-----------------\n";
}
//Function to check whether a position is valid or not
bool isValid(int board[][8],int row,int col){
if(leftDiagonal[row-col+7]!=1&&rightDiagonal[row+col]!=1&&column[row]!=1)
return true;
return false;
}
//function to check all the possible solutions
void ninjaQueens(int board[][8],int currentColumn){
if(currentColumn>=8)
return;
//loop to cover all the columns
for(int i=0;i<8;i++){
if(isValid(board,i,currentColumn)){
board[i][currentColumn]=1;
leftDiagonal[i-currentColumn+7]=rightDiagonal[i+currentColumn]=column[i]=1;
if(currentColumn==7){
print(board);
countt++;
}
//recursively calling the function
ninjaQueens(board,currentColumn+1);
//backtracking
board[i][currentColumn]=0;
leftDiagonal[i-currentColumn+7]=rightDiagonal[i+currentColumn]=column[i]=0;
}
}
}
int main() {
//initial board situation
int board[8][8]={{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0}};
ninjaQueens(board,0);
/* In total, 92 solutions exist for 8x8 board. This statement will verify our code*/
cout<<countt<<endl;
return 0;
}
Output:
Implementation in Java
//Solution to 8 queens problem using backtracking
class NinjaQueens {
int countt=0;
boolean[] leftDiagonal=new boolean[30];
boolean[] rightDiagonal=new boolean[30];
boolean[] column=new boolean[30];
// A function to print a solution
void print(int board[][]){
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
System.out.print(board[i][j]+" ");
}
System.out.print("\n");
}
System.out.print("-----------------\n");
}
//Function to check whether a position is valid or not
boolean isValid(int board[][],int row,int col){
if(leftDiagonal[row-col+7]==false&&rightDiagonal[row+col]==false&&column[row]==false)
return true;
return false;
}
//function to check all the possible solutions
void ninjaQueens(int board[][],int currentColumn){
if(currentColumn>=8)
return;
//loop to cover all the columns
for(int i=0;i<8;i++){
if(isValid(board,i,currentColumn)){
board[i][currentColumn]=1;
leftDiagonal[i-currentColumn+7]=rightDiagonal[i+currentColumn]=column[i]=true;
if(currentColumn==7){
print(board);
countt++;
}
//recursively calling the function
ninjaQueens(board,currentColumn+1);
//backtracking
board[i][currentColumn]=0;
leftDiagonal[i-currentColumn+7]=rightDiagonal[i+currentColumn]=column[i]=false;
}
}
}
void solve(){
//initial board situation
int board[][]={{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0}};
ninjaQueens(board,0);
/* In total, 92 solutions exist for 8x8 board. This statement will verify our code*/
System.out.print("countt\n");
return;
}
public static void main(String[] args) {
NinjaQueens solution=new NinjaQueens();
solution.solve();
}
}
Output:
Complexity Analysis
Time Complexity: O(N!), For the first column, we will have N choices, then for the next column, we will have N-1 choices, and so on. Therefore the total time taken will be N*(N-1)*(N-2)...., which makes the time complexity to be O(N!).
Space Complexity: O(N), since we are just maintaining three linear arrays as extra storage space.
Frequently Asked Questions
How do you solve 8 queens problem backtracking?
To solve the 8 Queens Problem using backtracking, we recursively try to place queens in each column, checking if the placement is valid and backtracking if not. The process continues until a valid solution is found or no solution exists.
Which algorithm is used to solve 8 queens problem?
One common algorithm used to solve the 8 Queens Problem is the backtracking algorithm, which tries to place queens on the chessboard column by column, checking if each placement is valid and backtracking if it is not.
What is the logic behind Queens problem?
The N-Queens problem is a classic puzzle. Its logic involves placing N chess queens on an N×N chessboard, so that no two queens threaten each other. It's a constraint satisfaction problem commonly solved using backtracking algorithms.
How many nodes are there in the 8 queen problem?
In the standard 8-Queens problem, there are 92 distinct solutions. Each solution represents a unique arrangement of 8 queens on an 8x8 chessboard, ensuring no two queens threaten each other in any direction.
Conclusion
We extensively discussed solving the 8 queens problem using backtracking. We learned how this solution works, its output values and its optimisation. We also went through sample codes involving the solution of 8 queens problem using backtracking. You can also try the N-Queens problem at Code 360.
We hope this blog has helped you enhance your knowledge about the topic 8 queens problem using backtracking. If you like to learn more, you can check out our articles:
Recommended Readings:
Refer to our Guided Path to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, and many more! If you wish to test your competency in coding, you may check out the mock test series and participate in the contests.
306+ registered