N Queen Problem in C++
Posted by Superadmin on August 09 2022 07:09:26

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.

  1. /*
  2.  * C++ Program to Solve N-Queen Problem
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #define N 8
  8. using namespace std;
  9.  
  10. /* print solution */
  11. void printSolution(int board[N][N])
  12. {
  13.     for (int i = 0; i < N; i++)
  14.     {
  15.         for (int j = 0; j < N; j++)
  16.             cout<<board[i][j]<<"  ";
  17.         cout<<endl;
  18.     }
  19. }
  20.  
  21. /* check if a queen can be placed on board[row][col]*/
  22. bool isSafe(int board[N][N], int row, int col)
  23. {
  24.     int i, j;
  25.     for (i = 0; i < col; i++)
  26.     {
  27.         if (board[row][i])
  28.             return false;
  29.     }
  30.     for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
  31.     {
  32.         if (board[i][j])
  33.             return false;
  34.     }
  35.  
  36.     for (i = row, j = col; j >= 0 && i < N; i++, j--)
  37.     {
  38.         if (board[i][j])
  39.             return false;
  40.     }
  41.  
  42.     return true;
  43. }
  44.  
  45. /*solve N Queen problem */
  46. bool solveNQUtil(int board[N][N], int col)
  47. {
  48.     if (col >= N)
  49.         return true;
  50.     for (int i = 0; i < N; i++)
  51.     {
  52.         if ( isSafe(board, i, col) )
  53.         {
  54.             board[i][col] = 1;
  55.             if (solveNQUtil(board, col + 1) == true)
  56.                 return true;
  57.             board[i][col] = 0;
  58.         }
  59.     }
  60.     return false;
  61. }
  62.  
  63. /* solves the N Queen problem using Backtracking.*/
  64. bool solveNQ()
  65. {
  66.     int board[N][N] = {0};
  67.     if (solveNQUtil(board, 0) == false)
  68.     {
  69.         cout<<"Solution does not exist"<<endl;
  70.         return false;
  71.     }
  72.     printSolution(board);
  73.     return true;
  74. }
  75.  
  76. // Main
  77. int main()
  78. {
  79.     solveNQ();
  80.     return 0;
  81. }

 

$ 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