Computer Science 242

Homework 2

You are asked to write a program which solves a sliding block puzzle. You may complete this project alone or as a team of size two. You will need to consider each of the following:
  • State: how will you represent the puzzle board.
  • Actions: the puzzle "blank" can be moved in a maximum of four directions (up, down, left, right); however, not all actions are always available (e.g., at the edges of the board.)
  • Transition model: How will a move update your board?
  • Initial state: the initial state will be given to you as console standard (plain text) input.
  • Terminal states: the goal is to get all the non-blank tiles into numerical order, starting from top left. Although a real sliding block puzzle allows two final states, where the blank can be either top left or bottom right, for this project you should consider only one final state: where the blank is in the top left.
Your objective is to find the shortest solution with the fewest number of steps. Therefore, once you have developed a workable model of the puzzle, you must implement at least two search algorithms:
  • Breadth First Search (BFS)
  • AStar Search
Discussion Your README should explain your heuristic for AStar, and discuss the relative performance of BFS and AStar. A good way to measure performance is to count the number of expanded nodes.

To represent a solution, output a series of moves with respect to the motion of the blank tile (e.g., a series of UP, LEFT, RIGHT, DOWN tokens in plain text). The input format consists of an integer for the size of the puzzle, followed by the title IDs, where 0 is the blank tile: 

3
1 2 5
3 4 8
6 7 0
Your program should be named "puzzle" and take a command line argument "--astar" to specify astar, or "--bfs" to specify bfs. Here are some examples of what the input/output should look like: 
 ./puzzle --astar < /u/cs242/hw2/test_in
LEFT
UP
 ./puzzle --bfs < /u/cs242/hw2/test_in
LEFT
UP
 ./puzzle --bfs < /u/cs242/hw2/test14_in
LEFT
UP
UP
LEFT
DOWN
RIGHT
DOWN
LEFT
UP
RIGHT
RIGHT
UP
LEFT
LEFT
 ./puzzle --astar < /u/cs242/hw2/test14_in
LEFT
UP
UP
LEFT
DOWN
RIGHT
DOWN
LEFT
UP
RIGHT
RIGHT
UP
LEFT
LEFT