Using BFS to solve the 15-puzzle

Part 1 | Part 2 | Parts 3 & 4

Challenge 5: the 15-puzzle

The 15-puzzle is a famous sliding puzzle. Your aim is to slide the numbered squares around, using a single empty square, to finally achieve an orderly board.

The puzzle is amenable to BFS, although the search space gets big quickly so bigger boards can require minutes (or more!) to solve.

I think an elegant way to represent a solution is to trace the imaginary path of the empty square, which can have repeat positions. However, in this puzzle’s case, the state represents the entire board’s configuration.

Give it a shot

Clone the repo and crack it. The last test case might take several seconds to compute (but shouldn’t take too long.)