COSC 410: Artificial Intelligence COSC 410: Artificial Intelligence Assignment #3: 19-Puzzle Due: 2/11/22 Points: 100 Consider a variant of the 8-puzzle where there are 19 tiles plus a blank, arranged...

need this program done


COSC 410: Artificial Intelligence COSC 410: Artificial Intelligence Assignment #3: 19-Puzzle Due: 2/11/22 Points: 100 Consider a variant of the 8-puzzle where there are 19 tiles plus a blank, arranged in the shape of a cross. An example would be: +---------+ | 2 | 1 | +---------+ | 6 | | +-----------------------------+ | 4 | 5 | 7 | 3 | 8 | 9 | +-----------------------------+ | 10 | 11 | 12 | 13 | 14 | 15 | +-----------------------------+ | 16 | 17 | +---------+ | 18 | 19 | +---------+ The rules of the puzzle are the same as that of the 8-puzzle. A tile may be moved to the blank space in each move (or you can think of it as moving the blank). The goal is to get all the tiles in the following order using the fewest number of moves: +---------+ | | 1 | +---------+ | 2 | 3 | +-----------------------------+ | 4 | 5 | 6 | 7 | 8 | 9 | +-----------------------------+ | 10 | 11 | 12 | 13 | 14 | 15 | +-----------------------------+ | 16 | 17 | +---------+ | 18 | 19 | +---------+ Write a program using the A* algorithm, or another AI algorithm, to solve this puzzle. The program should use a consistent heuristic measure for h. One possible function is the Manhattan distance: For any non-blank tile, find the difference in the x-direction from where the tile is to where it should be in the solution and add that to the difference in the y-direction from where the tile is to where it should be. Sum up these numbers for all the non-blank tiles to calculate h. The program should read in the starting state from standard input and print out the states that lead to the goal to standard output. The input and output will consist of just the numbers, not the lines as shown above. The number 0 will indicate the blank in the input and the output. Allowable Code You may use any code from the book or from class. You may use the APIs for a PriorityQueue (but don't - it's not efficient for this problem,) HashMap or HashTable, and ArrayList, or similar code for these data structures (and accredit the code.) You must write your own A* algorithm code or use the book's code. Sample Run java Puzzle Start State: 2 1 6 3 4 11 5 7 0 8 10 12 13 14 15 9 16 17 18 19 2 1 6 3 4 11 5 7 8 0 10 12 13 14 15 9 16 17 18 19 2 1 6 3 4 11 5 7 8 9 10 12 13 14 15 0 16 17 18 19 2 1 6 3 4 11 5 7 8 9 10 12 13 14 0 15 16 17 18 19 2 1 6 3 4 11 5 7 8 9 10 12 13 0 14 15 16 17 18 19 2 1 6 3 4 11 5 7 8 9 10 12 0 13 14 15 16 17 18 19 2 1 6 3 4 11 5 7 8 9 10 0 12 13 14 15 16 17 18 19 2 1 6 3 4 0 5 7 8 9 10 11 12 13 14 15 16 17 18 19 2 1 6 3 4 5 0 7 8 9 10 11 12 13 14 15 16 17 18 19 2 1 0 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Last modified: Jan. 28, 2022 Dr. Donald L. Simon, [email protected] http://www.mathcs.duq.edu/profs/simon.html COSC 410: Artificial Intelligence Assignment #3: 19-Puzzle Due: 2/11/22 Points: 100 Allowable Code Sample Run