Breadth-First Search is guaranteed to find the solution with the least number of moves from the initial state, although it may evaluate a rather large number of potential move sequences as it operates. Depth-First Search tries to make as much progress as possible each time it searches, and may locate a solution rather quickly, but it also may waste a lot of time on searching parts of the search tree that seem to offer no hope for success.

It is thus worthwhile to compare Depth-First Search, Breadth-First Search, and A*Search directly with one another. Using the 8-puzzle as our sample game, we created an initial state by randomly moving *n* tiles (ranging from 2, 4, 8, and 16); note that the same tile will not be moved twice in a row, since that would "undo" the move. Once *n* reached 32, the searches ran out of memory. For each board state, we execute Breadth-First Search, Depth-First Search(*n*), Depth-First Search(2**n*), and A*Search. For each move size *n*:

We total the number of board states in the

*open*and*closed*lists—this reveals the efficiency of the algorithm in locating the solution. The columns marked with # contain the average of these totals over all runs.We total the number of moves in the solution once found — this reveals the efficiency of the found solution paths. The columns marked with

*s*contain the average of these totals over all runs. The number in parentheses records the number of trials that failed to locate a solution within the given ply depth.

Start Free Trial

No credit card required