| Computer Science 242Homework 2You 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:
  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: 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.
 
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. Breadth First Search (BFS)
 AStar Search
 
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
 
 |