CSC 3421535 Artificial Intelligence (Spring 2018) Homework Three (80 points) Due: Tuesday, February 27, 2018 by 11:59PM (via Blackboard) Using the initial program that you wrote for the 2nd assignment, which reads in the initial input configuration, you are to solve the 8-puzzle program using the A* algorithm we covered in class. This requires you to design a heuristic h(n) which can estimate the cost to the specified goal state. Therefore, you'll need to define the function f(n) where f(n) g(n) + h(n) and g(n) - cost so far to reach n (current position) . h(n) - estimate to reach the goal state from n From the starting state, read as input, you should print out the sequence of moves required to get to the goal state, also read as input. The output should be displayed as a pair, where "tile" is the number of tile to be moved and "dir" is the direction to move the tile. Please us one of [ UP, DOWN, LEFT, RIGHT]. For the start and goal state the below the output might be 3, UP 1, LEFT 6, DOWN 4, DOWN Start State Goal State The rubric for this assignment is as follows 1) 10 points program is formatted well and commented appropriately 2) 10 points- program has code to help prevent and/or detect errors 3) 50 points - A* is implemented correctly. That is, g(n) & h(n) are defined and a set of boards are maintained as the algorithm proceeds to a solution 4) 10 points -program displays sequence of moves that solve the puzzle Please make sure you can read the start state and the goal state as a sequence of space separated numbers on a single line as that is how it will be tested. For example the data will be entered as follows for the above start and goal states 7 2 45068 31 012 3 45678 Output would then be displayed as 3, UP 1, LEFT NOTE: THE PROGRAM YOU SUBMIT MUST BE YOUR OWN WORK. NO CREDIT WILL BE GIVEN FOR ANY SUBMISSION THAT IS NOT YOUR OWN WORK OR THAT CAN NOT BE EXPLAINED BY YOU IN DETAIL ANY SUBMISSIONS TAKEN FROM THE INTERNET WILL RESULT IN A SCORE OF 0 AND MAY RESULT IN FAILING THE COURSE IMMEDIATELY