PHP-Fusion Powered Website - Articles: N Queen Problem in C++

Users Online

· Guests Online: 31

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads

No Threads created

Hottest Threads

No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Oh no! Where's the JavaScript?
Your Web browser does not have JavaScript enabled or does not support JavaScript. Please enable JavaScript on your Web browser to properly view this Web site,
or upgrade to a Web browser that does support JavaScript; Firefox, Safari, Opera, Chrome or a version of Internet Explorer newer then version 6.

Articles Hierarchy

Articles Home » C++ » N Queen Problem in C++

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

Users Online

Forum Threads

Latest Articles

Articles Hierarchy

N Queen Problem in C++

N Queen Problem in C++

Comments

Post Comment

Ratings