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:- 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
|
have taken their assigned medication. At the end of the visits, the robot reportsto the doctor which patients were not in the room, and which did not take theirmedication.Important NoteEvery implementation point described below is associated a number of marks. Inprevious years, we noticed that students frequently try to farm partial marks by writingsome amount of code for every section, even though none of it can even be executed.This is not the way to develop any complex system, and we intend to disincentivise it.For the reason described above, if a node implementing a piece of functionality doesnot execute, at most half the marks for that ROS node can be awarded. Marks arerounded up. Therefore, if an item is worth 5 marks, the most that a non-executablecode can get is 3.By non-executable, we mean that the code immediately terminates with an error dueto syntactic issues in the file, or wrong import statements. Runtime exceptions or bugsthat do not happen in the early stages of the execution will not be considered as non-executable, and therefore will not incur the penalty.Initialization• Create a package called "resit_coursework". Remember to maintain thecorrect dependencies in package.xml and CMakeLists.txt during development
