Backtracking with State

Section  introduced algorithms that backtrack. An algorithm is a recursive function that generates new problems for the recursive step rather than using the pieces of its input data. On occasion, an algorithm may have to make choices among several branches on the path to a solution. Some of them may lead nowhere. In such cases, an algorithm can backtrack. That is, it can restart the search for a solution with a different branch to check if it succeeds.

When the data representation for a problem uses structures or vectors, a backtracking algorithm can use structure mutation to test different approaches to a solution. The key is to design a pair of functions that change the state of the problem representation and that undo such a change in case the attempt fails. In this section, we discuss two examples of this kind: the Queens puzzle and the Peg Solitaire problem.

Recall the Queens puzzle from section . The goal of the puzzle is to place n queens on some board of arbitrary size m-by-m such that the queens do not threaten each other. A queen in chess threatens all places on the row, the column, and the two diagonals going through her own position. Figure  illustrates the notion with a single queen on an 8-by-8 board.

In section , we represented chessboards with lists. When we got to know vectors, we also developed a vector-based representation in exercise , as follows:

;; A chess-board CB is a (vectorof (vectorof boolean))
;; such that all vectors have the same size.

;; make-chess-board : N -> CB 
(define (make-chess-board m) 
  (build-vector m (lambda (i) (build-vector m (lambda (j) true))))) 

The queen-placement algorithm places a queen on one of the available fields on the given board and creates a new board that reflects the addition of the queen. This step is repeated until there are no more queens to be placed, in which case the puzzle is solved, or until there are no more places to choose from. In the second case, the algorithm backtracks. That is, the algorithm removes the last queen that was added and chooses some other available field. If there are no more fields, it backtracks further. The algorithm signals a complete failure when it becomes impossible to backtrack.

On one hand, creating a new board at each stage is acceptable because the chosen field may turn out to be the wrong one in which case the old board is the starting point for the next step. On the other hand, a human player is more likely to place the queen on the board and to remove it if the position turns out to be a bad choice. Thus the Queens problem is an example of where the ability of computer programs to create many alternative ``worlds'' clashes with the human world, which offers extremely limited possibilities of this kind and thus restricts human imagination. Still, it is worth exploring how the addition of vector mutation to our vocablulary enables us to mimic the actions of a human player more closely than before.

Exercise 43.3.1

Placing an additional queen on a chessboard means that some of the fields on the chessboard have to be set to false because they are now threatened and no longer available for future placements of queens. The placement of a queen is a function of the given chessboard and the indices of the new queen:

;; place-queen : CB N N -> void
;; effect: to set those fields in CB to false that are threatened by  
;; a queen on row i, column j 
(define (place-queen CB i j) ...)) 

Hints: (1) Recall threatened? from exercise . (2) Consider developing an abstract function for processing all items on a board. The function is analogous to vec-for-all from exercise . Solution

Exercise 43.3.2

Develop unplace-queen. The function removes a queen and its threats from a chessboard:

;; unplace-queen : CB N N -> void
;; effect: to set those fields in CB to false that were threatened by  
;; a queen on row i, column j 
(define (unplace-queen CB i j) ...)) 

Given any chessboard CB, the following equation holds:

  (begin 
    (place-queen CB i j) 
    (unplace-queen CB i j) 
    CB) 
= CB 

Exercise 43.3.3

Modify the solution of the Queens problem in section  to use the vector-based representation of chessboards and the functions place-queen and unplace-queen from exercises  and . Solution

Exercise 43.3.4

Use the draw.ss teachpack to develop a view for the Queens problem. Recall that a view is a function that illustrates certain aspects of a problem in a graphical manner. The natural solution here is to display the intermediate stages of the solution process according to the algorithm of exercise , including the backtracking steps. Solution

In section  we discussed the Peg Solitaire problem. The goal of the game is to eliminate the pegs one by one, until only one peg is left. A player can eliminate a peg if one of the neighboring holes is unoccupied and if there is a peg in the hole in the opposite direction. In that case, the second peg can jump over the first one and the first one is eliminated.

Just as with the Queens puzzle, we can represent the problem state with vectors and indicators for pegs and holes. In the real world, moving a peg corresponds to a physical action that changes the state of the board. When a player backtracks, the two pegs are placed back in their original positions.

Exercise 43.3.5

Design a vector representation for the triangular peg solitaire board. Develop a function for creating a board with a single hole. Solution

Exercise 43.3.6

Design a data representation for a move in the Peg Solitaire problem. Develop a function for making a move. Develop a function for undoing a move. The two functions should rely exclusively on effects. Do the functions satisfy an equation analogous to place-queen and unplace-queen in exercise ? Solution

Exercise 43.3.7

Develop a backtracking algorithm for solving a Peg Solitaire problem whose hole is placed randomly. Solution

Exercise 43.3.8

Use the draw.ss teachpack to develop a view for the Peg Solitaire problem. Recall that a view is a function that illustrates certain aspects of a problem in a graphical manner. The natural solution here is to display the intermediate stages of the solution process according to the algorithm of exercise , including the backtracking steps. Solution