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