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 Diagonalint x = i;int y = j;while(x>=0 && y>=0){if(board[x][y]==1)return false;x--;y--;}//Right Diagonalx = 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