Blocks World Puzzle

Links:

The report presents the work done to investigate search tree algorithms used to solve puzzles and games. Then the algorithms are applied to solve the Blocks-World puzzle [1].

The method used is building a search tree and exploring it to find the solution. The algorithms used are mixture of blind search and heuristic search. For the blind search, the algorithms used are depth-first, breadth-first and iterative deepening. Different ways of calculating the heuristic values are discussed but only one was used in the implementation.

The key results are, despite the game may look trivial at the first glance; blind search techniques were not able to find the solution in a reasonable time. On the other hand, involving heuristic estimates in the search tree resulted in notable outcomes. A solution for the puzzle was found. Nevertheless, the blind search algorithms were able to find the solution when reducing the puzzle conditions (reduce world size or the number of blocks to be moved).

This project was built as a coursework for the ‘Artificial Intelligence’, 1st semester in MSc Artificial Intelligence at the University of Southampton.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s