...

/

N - Queens Problem - Implementation

N - Queens Problem - Implementation

Implement the solution for the N-Queens problem.

We'll cover the following...

Implementation

In the N - Queens Problem lesson, we discussed the logic to solve this problem. Let’s move to the coding part now.

Press + to interact
#include <iostream>
using namespace std;
bool isSafe(int board[][10],int i, int j, int n){
for(int row = 0; row<i; row++){
if(board[row][j] == 1){
return false;
}
}
//Left Diagonal
int x = i;
int y = j;
while(x>=0 && y>=0){
if(board[x][y]==1)
return false;
x--;
y--;
}
//Right Diagonal
x = i;
y = j;
while(x>=0 && y<n){
if(board[x][y]==1)
return false;
x--;
y++;
}
return true;
}
bool solveNQueen(int board[][10],int i, int n){
if(i==n){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(board[i][j] == 1){
cout<<" Q ";
}
else{
cout<<" - ";
}
}
cout<<endl;
}
cout<<endl<<endl;
return true; //false to print all configurations
}
for(int j=0; j<n; j++){
if(isSafe(board,i,j,n)){
board[i][j] = 1;
bool nextQueen = solveNQueen(board,i+1,n);
if(nextQueen){
return true;
}
board[i][j] = 0;
}
}
return false;
}
int main() {
int n = 4;
int board[10][10] = {0};
solveNQueen(board,0,n);
}

Explanation:

  • On line 4, we define a function isSafe() to check whether the queen can be placed at position (i, j).
  • From lines 5 to 9, we check whether there is any queen
...