CSCI 324 Project #2
Best-First Search and A*
Date Due: 30
September 2013
Problem Description:
Sliding block puzzles are a staple of many childhoods, and are also a recurring theme in AI. The puzzle typically consists of a 4x4 box which contains 15 small squares numbered 1 through 15 and one blank spot. Moves are made by sliding one of the neighboring pieces into the empty space (either from above, below, left, or right, depending on where the empty space is and the choice of the solver). The objective is to get the pieces arranged without lifting any of them out of the box so that reading left to right, top to bottom, the numbers are in order.
|
|
||||||||||||||||||||||||||||||||
|
Randomized squares |
The puzzle solved |
One of your jobs is to come up with a heuristic function that allows you to solve the puzzle in as few moves as possible. You should carefully document your heuristic in your code, and explain it in detail!
The Assignment:
You are to write a program to solve the 15 piece sliding block puzzle. Your program should read the initial configuration of the board from an input file consisting of four rows of numbers separated by spaces. The blank square should be represented by 0. Your program should then print out the series of moves needed to solve the puzzle, one move per row, using the words “LEFT”, “RIGHT”, “UP”, and “DOWN” to indicate how the block that moves into the empty square slides. For instance, in the puzzle above, your program might print “RIGHT” as the first move to indicate that the square with the 1 on it moves into the empty space. Your program should also print out the move number on each line, and the total number of moves required to solve the puzzle. A sample output might be:
1. RIGHT
2. DOWN
3. RIGHT
4. UP
Puzzle was solved in 4 moves
The input file could contain several puzzles, so your program should read 4 lines of numbers, solve that puzzle, read the next four lines, solve the second puzzle, etc.
This is an advanced CS course so your program is expected to be written following good style guidelines, and using all the best practices you have learned from your previous courses. For additional credit, ONCE you have the basic functionality implemented, you may also implement a GUI and graphical display IN ADDITION to the text interface described above. Have fun, and good luck!