# Developer Corner

## N Queens Chess Problem Solution using C++

#### 31/10/2017

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 incrementing or decrementing 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:

Previous Topics List