[Tutor] 15 puzzle

[Daniel Yoo]

On Sat, 28 Apr 2001, Julieta wrote:

> Hi! My name is Maritza and I am trying to learn how to program with
> the python language.  I'm interested in a computer version of the 15
> puzzle.  I've seen how it works and used it as well, but I am curious
> about how the program was set up.  Just to make sure that we all know

If you're trying to write a game to play the 15 puzzle, it sounds like a
fun problem.  How far have you gotten in Python?  We can help give you
pointers on writing the game.


However, if you're trying to write a program to get the computer to try
_solving_ the problem, that's a whole different story.  Solving the 15
puzzle is a HARD problem --- it's something that even beginning computer
scientists have trouble writing.  *grin*


> which puzzle I'm refering to, it is the one that you can get at toy
> stores and is essentially a 4 x 4 matrix with the numbers 1-15 on
> tiles placed in the matrix.  There is one blank space where tiles
> adjacent to the blank space may be moved into the blank space.  The
> object of the game is to arrange the numbers 1-15 in order.  They are


###

[You might want to ignore the message below; now that I think about it,
this is probably not what you're looking for.]

If you'd like an example on how to get the computer to solve 15 puzzles,
take a look at:

    http://hkn.eecs.berkeley.edu/~dyoo/python/

Check under the heading "A* Search", which has a solution to the 8-puzzle.  
Modifying it to do the 15 puzzle shouldn't be too bad...  (However, if
you're just starting out in Python, I'm not quite sure if my code will be
readable for you.)