Question

(Eight Queens) A puzzler for chess buffs is the Eight Queens problem, which asks the following: Is it possible to place eight queens on an empty chessboard so that no queen is “attacking” any other (i.e., no two queens are in the same row, in the same column or along the same diagonal)? For instance, if a queen is placed in the upper-left corner of the board, no other queens could be placed in any of the marked squares shown in Fig. 15.23. Solve the problem recursively. [Hint: Your solution should begin with the first column and look for a location in that column where a queen can be placed—initially, place the queen in the first row. The solution should then recursively search the remaining columns. In the first few columns, there will be several locations where a queen may be placed. Take the first available location. If a column is reached with no possible location for a queen, the program should return to the previous column, and move the queen in that column to a new row. This continuous backing up and trying new alternatives is an example of recursive back-tracking.]

Short answer

Place queens column by column, recursively checking for conflicts and using backtracking if needed to find a safe configuration.

Step-by-step solution

Understand the Problem

The Eight Queens problem requires placing eight queens on a standard 8x8 chessboard where no two queens can attack each other. This means they cannot be in the same row, column, or diagonal.

Initialize the Chessboard

Create an 8x8 matrix to represent the chessboard. Each position is initially empty and can be considered as 0.

Define the Recursive Function

Write a function to attempt to place queens column by column. The function should accept the current column as a parameter and try to place a queen in that column following the rules.

Check for Attacks

Before placing a queen in a specific position in the column, check if placing a queen there would cause any conflicts with previously placed queens in terms of row, column, or diagonal.

Place the Queen

If a safe position is found in the current column, place the queen (set the position in the matrix to 1), and call the recursive function for the next column.

Backtracking

If no safe position is found in the current column, backtrack by removing the queen from the last placed column (set the matrix position back to 0), and try the next possible row in the previous column.

Termination

The recursion ends successfully when queens are placed in all columns without conflicts. If all columns are filled, print the configuration.

Key concepts

Recursive Algorithms

Recursive algorithms are methods that solve problems by breaking down the problem into smaller, similar sub-problems and solving each one in a repetitive manner. The Eight Queens problem is an excellent example where recursion plays a crucial role. In this problem, placing a queen in one column impacts the placement of queens in subsequent columns.

The recursive function in this context takes care of placing queens column by column. It attempts to find a suitable position for the queen following the rules: no two queens should threaten each other.

• The function is initiated at the first column and progresses by evaluating if each row in the column can host a queen without conflict.
• If a valid position is located, the problem is recursively delegated to the next column.
• If a column cannot host a queen without conflicts, the function backtracks, pointing to another recursive technique called 'Backtracking'.

This recursive nature simplifies tackling this complex problem by focusing sequentially on each recursive subset of the board, rather than tackling the entire board at once.

Backtracking

Backtracking is a fundamental concept used alongside recursion. It is employed in the Eight Queens problem to revisit previous decisions and make necessary changes when a dead-end is reached in the attempted solution.

In solving the Eight Queens problem, backtracking occurs when a column fails to accommodate a queen safely.

• Backtracking algorith reverts to the previous column where a queen was successfully placed.
• The already-placed queen is then moved to an alternative row if possible, paving the way for new possibilities in the succeeding columns.
• Backtracking ensures that each potential solution is explored and evaluated thoroughly.

Thus, backtracking acts as a corrective process within the recursive algorithm, guaranteeing that all possibilities are considered, eventually leading to a feasible solution.

Chessboard Representation

In problems like the Eight Queens, visualizing the chessboard is key to understanding the placement of queens. The chessboard for this problem is typically represented as an 8x8 matrix or grid.

Representation Details:

• The initial configuration of the chessboard is defined with all elements set to zero, signifying that no queens are placed.
• A queen's position is marked by updating the corresponding position in the matrix from a '0' to a '1'.
• The constraints of the problem—that queens should not share a row, column, or diagonal—can be methodically checked by inspecting these matrix indices.

This matrix representation allows for easy manipulation and verification of each placement's validity, facilitating the problem's efficient resolution.

Algorithm Design

Designing an algorithm for the Eight Queens problem involves structuring the code in a way that systematically explores possible solutions, utilizing recursive functions and backtracking techniques.

The design process includes:

• Initial Board Setup: Establishing the chessboard as an 8x8 matrix and setting all positions to '0'.
• Recursive Function Construction: Developing a function to place queens by exploring each column recursively.
• Conflict Monitoring: Adding logic to verify that any queen placement does not generate conflicts, thereby maintaining the rules of the game.
• Backtracking Mechanism: Incorporating a plan to retract and adjust prior queen placements when the current approach yields no valid outcome.

By designing an algorithm adaptable to this trial-and-error method, solutions to placing eight non-threatening queens on the chessboard can be efficiently discovered and implemented.