Mostly popular for its n=3 (game of eight) and n=4 (game of fifteen) versions, I've just implemented the game in C on Linux and ported it last night to Windows. I'm still working on a "GOD mode" whereby the program solves the puzzle itself for the user. Doing so will require a convenient algorithm as the search space is huge. After some googlin' the A* algorithm is the way to go. Further search revealed some research that improves on A* (Iterative Deepening A* - IRDA*) and could be useful for greater values of n (my implementation offer 3 <= n <= 9). I'll implement the "GOD mode" for n = 3 and n = 4, so A* should do just fine. In an effort to keep this down for later recap and help anyone out there "stumble on this" in the case they themselves are searching for something similar, i have included some of the pages i found helpful:

Wikipedia on the A* algorithm - description and pseudo code - good place to start

A* Algorithm tutorial by Justin Heyes-Jones

Further analysis with theorems of the sixteen puzzle by Kevin Gong (referred by Heyes-Jones)

Princeton programming assignment (8 Puzzle) Spring 09

University of Birmingham's professor Mark Ryan on solvability of the tiles game

stackoverflow peeps discussing the N-Puzzle's pseudo-random shuffling for an inital solvable state

Wikipedia on The Fisher-Yates shuffle - a good way to initialize to a random state

Heurtisticswiki offers links to the different possible heuristics to choose from and an O(n2) implementation

Paper on IRDA* by Alexander Reinefeld and T.A Marsland

A Real-Time Algorithm for the (n2 - 1)-Puzzle by Ian Parberry

Other than the GUI part of course, and the data structures you will need - there are three things to think about: creating a random initial state, ensuring the initial state's solvability, and if you wanna play "GOD Mode", then a proper A* algorithm implementation to find the goal state!

Enjoy!

## Comments

## Post a Comment