Simply Logical lab exercises chapter 6

The assignment deals with heuristic search and the 8-puzzle.
The well-known 8-puzzle consists of 8 tiles and an empty space, organised in a square. A move consists in sliding a tile to the empty space, or equivalently, moving the empty space horizontally or vertically. Each move has equal cost. The objective is to reach the following position:
   1 2 3
   8   4
   7 6 5
The file contains a program for solving the 8-puzzle from an arbitrary starting position. The query puzzle(C,N) will return the cost of the found solution (the number of moves) and the number of nodes searched. During the search it prints the f-value of the current node taken from the front of the agenda. By typing ; after a solution has been found, you can backtrack over different starting positions specified by start_p.

  1. Adapt the predicate merge such that it only adds a node to the agenda if it does not already contain the same node with a lower f-value.

  2. The predicate eval_p evaluates a board position in terms of its overall Manhattan distance to the goal by using totdist. This heuristic is not always very effective. Improve it by adding the result of the predicate insequence, which punishes tiles that are not followed in clockwise direction by their successor.

  3. Make the search algorithm non-exhaustive by limiting the agenda to a fixed size. Demonstrate and discuss the effect this has on the ability of the program to find (optimal) solutions.

Back / Peter Flach