Search Algorithms Applied to the 8-Puzzle
Write a program that, given an initial configuration, and a search strategy, returns:
a series of states (path) from the initial to the goal configuration, and the number of generated nodes (states).
The following strategies should be implemented:
depth first search.
breath first search.
best first search with each of the following heuristics :
depth in the search space + number of tiles out of place.
depth in the search space + minimum number of moves to
reach the goal state. depth in the search space + the heuristic H defined below.
H is a combination of two mesures:
1. totdist: the "total distance" of the eight tiles in Pos (Pos is a board position) from their "home squares". We use
the Manhattan distance (see below for the definition of the Manhattan distance) to calculate the distance of each tile
from its home square. For example, in the starting position of the puzzle (a) in the figure below, totdist = 4.
2. seq: the "sequence score" that measures the degree to which the tiles are already ordered in the current position
with respect to the order required in the goal configuration. seq is computed as the sum of scores for each tile
according to the following rules:
a tile in the centre scores 1; a tile on a non-central square scores 0 if the tile is, in the clockwise direction, followed
by its proper successor. such a tile scores 2 if it is not followed by its proper successor.
For example, for the starting position (a) of the puzzle in the figure below, seq = 6. The heuristic estimate, H, is
H = totdist + 3*seq
The "Manhattan distance" between 2 squares S1 and S2 is the distance between S1 and S2 in the horizontal
direction plus the distance between S1 and S2 in the vertical direction. We want to minimize the length of solutions.
Therefore, we define the cost of all the arcs in the state space to equal 1.
Solution contain Netbean project