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
12 || queens
13 || queens
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 function 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 preceding row, as shown Figure 17.9c.
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.