egsoftweb@gmail.com
 facebook.com/egsoftweb

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: