The N Queens Problem is the problem of placing N chess queens on an N×N chessboard so that no two
queens threaten each other. Thus, a solution requires that no two queens share
the same row, column, or diagonal. The eight queens puzzle is an example of the N queens problem of placing N non-attacking queens on
an N×N chessboard, for which
solutions exist for all natural numbers N with the exception of N=2 and N=3.
In the code, backtracking method is
used to solve the problem. A queen is
placed in a column that is known not to cause conflict. If a column is not
found the program returns to the last good state and then tries a different
column by increments or decrements the column index.
//A C++ code to Solve N-Queen Chess
problem
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <conio.h>
const unsigned int N = 8;
using namespace std;
// Print N Queen chess problem solution
void PrintNQSolution(bool
board[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout
<< board[i][j] << " ";
cout
<< endl;
}
}
/* check if a queen can be placed on the
board[row][col]*/
bool CheckSafe(bool
board[N][N], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
{
if (board[row][i])
return false;
}
for (i = row, j = col; i >= 0 && j
>= 0; i--, j--)
{
if (board[i][j])
return false;
}
for (i = row, j = col; j >= 0 && i <
N; i++, j--)
{
if (board[i][j])
return false;
}
return true;
}
/*solve N Queen problem */
bool SolveNQ(bool
board[N][N], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++)
{
if (CheckSafe(board, i, col))
{
board[i][col] = true;
if (SolveNQ(board, col + 1) == true)
return true;
board[i][col] = false;
}
}
return false;
}
/* solves the N Queen problem using
Backtracking and print the solution.*/
bool SolveAndPrintNQ()
{
bool board[N][N] = { 0 };
if (SolveNQ(board, 0) == false)
{
cout
<< "Solution
does not exist"
<< endl;
return false;
}
PrintNQSolution(board);
return true;
}
int main()
{
cout
<< "**** " << N << " Queens Problem
Solution *****\n\n";
SolveAndPrintNQ();
_getch();
return 0;
}
Output:
