C++ Program to implement N-Queens Problem

In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 Queen’s problem asks how to place 8 queens on an ordinary chess board so that none of them can hit any other in one move. Consider an N by N “chess board” and ask if one can place N queens on such a board

Source: http://www.math.utah.edu/~alfeld/queens/queens.html

Here is the code for it:

1. #include<iostream>
2. #include<vector>
3. #include<fstream>
4. #include<string>
5. #include<algorithm>
6. using namespace std;
7. int ct=0;
8. class queen
9. {
10.     int n;
11. public:
12.     void read()
13.     {
14.         cout<<“Enter board size\n”;
15.         cin>>n;
16.     }
17.     bool place(int x[10],int k)
18.     {
19.         for(int i=1;i<k;i++)
20.         {
21.             if(x[i]==x[k]||i+x[i]==k+x[k]||i-x[i]==k-x[k])
22.                 return false;
23.         }
24.         return true;
25.     }
26.     void nqueen()
27.     {
28.         int x[10];
29.         int k=1;
30.         x[k]=0;
31.         while(k!=0)
32.         {
33.             x[k]++;
34.             while((!place(x,k))&&(x[k]<=n))x[k]++;
36.         if(x[k]<=n)
37.         {
38.             if(k==n)
39.             {
40.                 ct++;
41.                 cout<<“Solution “<<ct<<“:\n”;
42.                 print(x);
43.                 cout<<endl;
44.             }
45.             else
46.             {
47.                 k++;
48.                 x[k]=0;
49.             }
50.         }
51.         else
52.             k–;
53.         }
54.     }
55.     void print(int x[10])
56.     {
57.         char c[10][10];
58.         for(int i=1;i<=n;i++)
59.         {
60.             for(int j=1;j<=n;j++)
61.                 c[i][j]=’X’;
62.         }
63.         for(int i=1;i<=n;i++)
64.         {
65.             c[i][x[i]]=’Q’;
66.         }
68.         for(int i=1;i<=n;i++)
69.         {
70.             for(int j=1;j<=n;j++)
71.                 cout<<c[i][j];
72.                 cout<<endl;
73.         }
74.         cout<<endl;
75.     }
76. };
77. int main()
78. {
79.     queen A;
80.     A.read();
81.     A.nqueen();
82.     return 0;
83. }

 

Output:

Enter board size

4

Solution 1:

XQXX

XXXQ

QXXX

XXQX

 

Solution 2:

XXQX

QXXX

XXXQ

XQXX