# Eight Queens in C++

The Eight Queens problem can be solved using recursion.

This section gives a recursive solution to the Eight Queens problem presented earlier. The task is to place a queen in each row on a chessboard in such a way that no two queens can attack each other. You may use a two-dimensional array to represent a chessboard. However, since each row can have only one queen, it is sufficient to use a one-dimensional array to denote the position of the queen in the row. So, let us declare array queens as follows:

int queens[8];

Assign j to queens[i] to denote that a queen is placed in row i and column j. Figure 17.8a shows the contents of array queens for the chessboard in Figure 17.8b.

Listing 17.8 is a program that finds a solution for the Eight Queens problem

Listing 17.8 EightQueen.cpp

1 #include <iostream>
2
using namespace std;

3
4
const int NUMBER_OF_QUEENS = 8; // Constant: eight queens
5 int queens[NUMBER_OF_QUEENS];
6
7
// Check whether a queen can be placed at row i and column j
8 bool isValid(int row, int column)
9 {
10
for (int i = 1; i <= row; i++)
11
if (queens

== column // Check column
12    || queens
== column – i
// Check upper left diagonal
13    || queens
== column + i)
// Check upper right diagonal
14    return false; // There is a conflict
15    return true; // No conflict
16 }
17
18
// Display the chessboard with eight queens
19 void printResult()
20 {
21    cout <<
“\n———————————\n”;
22
for (int row = 0; row < NUMBER_OF_QUEENS; row++)
23    {
24
for (int column = 0; column < NUMBER_OF_QUEENS; column++)
25       printf(column == queens
?
“| Q ” : “| “);
26       cout <<
“|\n———————————\n”;
27    }
28 }
29
30
// Search to place a queen at the specified row
31 bool search(int row)
32 {
33
if (row == NUMBER_OF_QUEENS) // Stopping condition
34    return true; // A solution found to place 8 queens in 8 rows
35
36
for (int column = 0; column < NUMBER_OF_QUEENS; column++)
37    {
38       queens
= column;
// Place a queen at (row, column)
39       if (isValid(row, column) && search(row + 1))
40
return true; // Found, thus return true to exit for loop
41    }
42
43
// No solution for a queen placed at any column of this row
44    return false;
45 }
46
47
int main()
48 {
49    search(
0); // Start search from row 0. Note row indices are 0 to 7
50    printResult(); // Display result
51
52
return 0;
53 }

The program invokes search(0) (line 49) to start a search for a solution at row 0, which recursively invokes search(1), search(2), . . . , and search(7) (line 39).

The recursive search(row) function returns true if all rows are filled (lines 39-40). The function checks whether a queen can be placed in column 0, 1, 2, . . . , and 7 in a for loop (line 36). Place a queen in the column (line 38). If the placement is valid, recursively search for the next row by invoking search(row + 1) (line 39). If search is successful, return true (line 40) to exit the for loop. In this case, there is no need to look for the next column in the row. If there is no solution for a queen to be placed on any column of this row, the function returns false (line 44).

Suppose you invoke search(row) for row is 3, as shown in Figure 17.9a. The func­tion tries to fill in a queen in column 0, 1, 2, and so on in this order. For each trial, the isValid(row, column) function (line 39) is called to check whether placing a queen at the specified position causes a conflict with the queens placed before this row. It ensures that no queen is placed in the same column (line 11), no queen is placed in the upper left diagonal (line 12), and no queen is placed in the upper right diagonal (line 13), as shown in Figure 17.9a. If isValid(row, column) returns false, check the next column, as shown Figure 17.9b. If isValid(row, column) returns true, recursively invoke search(row + 1), as shown in Figure 17.9d. If search(row + 1) returns false, check the next column on the preced­ing row, as shown Figure 17.9c.

Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.