As part of my Masters degree I implemented a breadth first search algorithm to solve the Klotski problem. The Klotski problem is a problem where you are given a 5x4 grid, with 4 types of piece. The aim of the puzzle is to remove the one large centre-piece from the board, while removing no others. An example of this puzzle can be found here.
My solution uses a recursive search to find all possible moves for any given board. It implements each move, then searches for any further moves for each new board. This continues until a solution is found.
To find the solution in this way, we need to make 116 individual moves, and analyse 23,118 distinct board layouts. It takes my PC approximately 2.5 minutes to run.