Question

Write a backtracking algorithm for the \(n\) -Queens Problem that uses a version of procedure expand instead of a version of procedure checknode.

Short answer

The backtracking algorithm for the n-Queens problem with the expand procedure starts from an empty chessboard and recursively places queens on the board, generating children nodes. It backtracks when it fails to place a queen, returning to the previous node and trying a different placement. The algorithm continues this process until a solution is found or all placements are exhausted.

Step-by-step solution

Creating the initial node

Create an empty chessboard as the initial node for the backtracking algorithm and define the expand procedure. Since the queens are unique (no two are alike), we'll index them and try placing them on the board. Start by placing the first queen (index 0) in every possible space on the board (which would be \(n\) possibilities). Generate \(n\) children nodes, each representing a different placement of the first queen.

Recursive call

Let's assume we have a node that represents the placement of k queens on the board. Then the expand procedure will generate the children node by placing the queen \(k + 1\) in all possible spaces on the board where it is not threatened by any other queen already placed on the board. It's important to note that we only need to check the queens that have already been placed. This is the 'expand' procedure which will recursively go down the tree from the root node (empty chessboard), placing queens on the board and generating children nodes for each placement.

Handle base cases

There are two base cases to handle here. First, if we have placed all \(n\) queens on the board, then we have found a solution, so return the current board. Second, if we couldn't place a queen in any row during the 'expand' procedure, that means we have hit a dead-end. In that case, we backtrack and remove the queen placed in the previous procedure, marking it as not feasible.

Iterative backtracking algorithm

This expands on the third step and outlines how backtracking works. Start from the root node (empty chessboard). Then, while there are untried ways of placing the queens, choose one and update the board accordingly. Apply the expand procedure to generate the children nodes. If we find a solution during this process, return the corresponding board. If not, backtrack to the previous node and try a different placement until a solution is found or all placements have been tested.