I have to write a program in common lisp which utilizes the A* search
algorithm to solve a 15 puzzle. The input will be of the form ((1 2 3
4) (5 6 7 8) (9 10 11 12) (13 14 15 B)) where "B" is the blank spot in
the puzzle. The function should return a sequence of moves ((D-1 D-2)
(C-1 D-1) etc. to the goal). The goal state should be the one above.
If anyone knows where I could find this function or if you have code
that could be useful, please post it. I am in desperate need for this.
jay lineberry <········@cs.colostate.edu> writes:
> I have to write a program in common lisp which utilizes the A* search
[...]
Peter Norvig has written a book called "Paradigms of AI Programming"
giving code for, among other things, A* Searching.
You can find this code at
ftp://mkp.com/pub/Norvig/search.lisp
Stig Hemmer,
Jack of a Few Trades.
jay lineberry <········@cs.colostate.edu> writes:
> I have to write a program in common lisp which utilizes the A* search
> algorithm to solve a 15 puzzle. The input will be of the form ((1 2 3
> 4) (5 6 7 8) (9 10 11 12) (13 14 15 B)) where "B" is the blank spot in
> the puzzle. The function should return a sequence of moves ((D-1 D-2)
> (C-1 D-1) etc. to the goal). The goal state should be the one above.
>
> If anyone knows where I could find this function or if you have code
> that could be useful, please post it. I am in desperate need for this.
Others have already pointed you to A* code. I have a different, higher
level comment for you. You do realize that solving the 15 puzzle using
standard A* is untenable, don't you? In the AIMA code, they went as far as
developing a special representation so that they can solve the 8-puzzle
efficiently. You might want to try something similar, otherwise I'm afraid
you may not have a chance in hell.
Sunil
jay lineberry wrote:
> I have to write a program in common lisp which utilizes the A* search
> algorithm to solve a 15 puzzle. The input will be of the form ((1 2 3
> 4) (5 6 7 8) (9 10 11 12) (13 14 15 B)) where "B" is the blank spot in
> the puzzle. The function should return a sequence of moves ((D-1 D-2)
> (C-1 D-1) etc. to the goal). The goal state should be the one above.
>
> If anyone knows where I could find this function or if you have code
> that could be useful, please post it. I am in desperate need for this.
Norvig also co-authored a book with Stuart Russell called AI: a Modern
Approach. This is an excellent introduction to AI. The fourth chapter
covers Informed Search Methods, such as A*, IDA*, SMA*, hill-climbing,
etc... If you goto http://www.cs.berkeley.edu/~russell/aima.html, you will
find all the inforamtion you will need, plus other links, the code for the
book written in Lisp, Prolog, and C++. Very handy. It even has the
functions for an 8-puzzle problem all layed out for you : )