N Queen Problem in C++

This C++ Program demonstrates the implementation of N-Queen Problem.

Here is source code of the C++ Program to Solve N-Queen Problem by BackTracking. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Solve N-Queen Problem

```
 */
```
```
#include <iostream>
```
```
#include <cstdio>
```
```
#include <cstdlib>
```
```
#define N 8
```
```
using namespace std;
```
```
 
```
```
/* print solution */
```
```
void printSolution(int 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 board[row][col]*/

bool isSafe(int 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 solveNQUtil(int board[N][N], int col)

```
{
```
```
    if (col >= N)
```
```
        return true;
```
```
    for (int i = 0; i < N; i++)
```
```
    {
```
```
        if ( isSafe(board, i, col) )
```
```
        {
```
```
            board[i][col] = 1;
```

            if (solveNQUtil(board, col + 1) == true)

```
                return true;
```
```
            board[i][col] = 0;
```
```
        }
```
```
    }
```
```
    return false;
```
```
}
```
```
 
```

/* solves the N Queen problem using Backtracking.*/

```
bool solveNQ()
```
```
{
```
```
    int board[N][N] = {0};
```
```
    if (solveNQUtil(board, 0) == false)
```
```
    {
```

        cout<<"Solution does not exist"<<endl;

```
        return false;
```
```
    }
```
```
    printSolution(board);
```
```
    return true;
```
```
}
```
```
 
```
```
// Main
```
```
int main()
```
```
{
```
```
    solveNQ();
```
```
    return 0;
```
```
}
```

$ g++ nqueen.cpp
$ a.out
 
1  0  0  0  0  0  0  0
0  0  0  0  0  0  1  0
0  0  0  0  1  0  0  0
0  0  0  0  0  0  0  1
0  1  0  0  0  0  0  0
0  0  0  1  0  0  0  0
0  0  0  0  0  1  0  0
0  0  1  0  0  0  0  0
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Find the Median of Two Sorted Arrays using Divide and Conquer

» Next - C++ Program to Find Hamiltonian Cycle

Related Posts:

Recommended Articles: