Sliding puzzles

Table of Contents

I recently have become interested in sliding puzzles. You can read all about them on Wikipedia. In undergraduate AI, I was ask to implement a solver for the rush-hour game, a version of a sliding puzzle. I forgot all about it until recently when I was preparing an AI lesson to teach for Code Connects, a coding education non-profit. I stumbled upon the 8-puzzle.

Difficulty of AI

At first, it seemed pretty simple, and I thought an AI would do easy on it for bigger boards, but I was sorely mistaken. When you think about it, the N-puzzle, or sometimes called the $N^2-1$ puzzle, has $(N^2 -1)!/2$ possible states. That grows incredibly rapidly with N meaning even N=5 is very hard to solve.

There’s been a plethora of research on the puzzles, and I hope to explore it, implement it, and maybe even contribute to it.

My implementation

As a start, I’ve begun implementing my own version of the sliding puzzle. So far, I just have implemented the core sliding puzzle and N-puzzle representations with a basic (and slow) breadth-first search and A* search with the Manhattan heuristic. I’m also using this as an opportunity to learn more about Read the Docs. So, you can see my beginning docs. They’re not automatically generating everything yet, but I also haven’t written docstrings, so I wouldn’t expect much.

Expect more regular updates on the developments.

comments powered by Disqus