BFS zero-to-hero, part 5: the 15-puzzle
Solving a famous puzzle with BFS
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.)