Consider the following puzzle. There are seven adjacent, numbered cells with three blue coins and three red coins. The blue coins (indicated by B) want to occupy cells 1, 2 and 3 while the red coins (indicated by R) want to occupy cells 5, 6 and 7. The desired state is: 1 2 3 4 5 6 7 B B B R R R The coins can be in any of the cells, as long as each cell is occupied by at most one coin at a time. One possible state is illustrated below and is called State A: 1 2 3 B R B 4 5 R 6 7 R B A coin is allowed to move to the adjacent cell if that cell is empty. For example, in the figure above, the red coin in cell 4 may move to cell 5. A coin may also move to an empty cell by "jumping" over an adjacent occupied cell into the empty cell two cells away. For example, in the figure above, the blue coin in cell 3 may jump over the red coin in cell 4 into cell 5. You have to find a sequence of moves that will move all six coins into the positions depicted by the desired state. The figure below depicts State B. 1. 2. 1 2 3 4 5 6 7 R R R B B B Formulate the task as a search problem by defining the following: a state, the goal state and the moves (actions). Draw the first three levels of the state space with the initial state State A. Do not include repeating states. The root node is the first level. 3. Use the heuristic: the number of coins that are not in their correct cells as depicted by the desired state. For example, the heuristic value of start state A is 3 and of start state B is 6. 4. 5. Indicate the heuristic value for each state in your drawing for question 2. Show the values on the same drawing, i.e. you do not need to redraw the partial state space. Write a Java implementation of the Best First Search algorithm for this problem. a. Your program must read the contents of a start state from a text file. b. The output of your program must show the sequence of nodes that are expanded. A node in the graph can simply be displayed by printing the heuristic value and showing the contents of each cell from 1 to 7 in a single line. A zero entry represents an empty cell. For example, State A can be displayed as: h=3 BRBRORB and State B can be displayed as h=6 RRROBBB c. Your program must show the number of moves taken to reach the goal state. d. The output of parts a and b must be written to an output file as well as to the screen. Run the program first using state B as the start state and name the output file OutputB.txt. Then run the program using state A as start state and name the output file OutputB.txt. 5. b. The output of your program must show the sequence of nodes that are expanded. A node in the graph can simply be displayed by printing the heuristic value and showing the contents of each cell from 1 to 7 in a single line. A zero entry represents an empty cell. For example, State A can be displayed as: h=3 BRBRORB and State B can be displayed as h=6 RRROBBB c. Your program must show the number of moves taken to reach the goal state. d. The output of parts a and b must be written to an output file as well as to the screen. Run the program first using state B as the start state and name the output file OutputB.txt. Then run the program using state A as start state and name the output file Output B.txt. Follow the instructions below carefully: • You are required to program in Java and use object-oriented programming concepts. Save all your files in a compressed (.zip) folder with the following naming convention XXYYZZZ_CSC311_Practical_1_Term_1_2025.zip where XXYYZZZ corresponds to your student number. Include the following at the beginning of the Java file and in the Word document: Student surname Student name Student number WCSC311 2024 AI Practical Call your Java program Coins Puzzle.java Write a class called state with the following variables to represent a state. o An array with 8 entries to represent the 7 cells and the positions of the 6 coins. The array entry at index () should indicate the cell number of the empty cell. For example, cell () for state A will contain the integer 5. An int value to store the h value. Write the necessary methods of the class including: o Accessor and mutator methods to retrieve and modify attributes of the class; o Methods to perform moves (i.e. generate children states) A method to print the contents of a state. Use the (built-in) Java Collections PriorityQueue (PQ) data structure to store the frontier list of expanded states. The PQ is of type State (represented in the data structure described above) and is sorted in increasing order according to the heuristic value of each state. Two states that have the same heuristic value may appear in any order in the PQ. (Note that you have to overload the comparison method in your PQ to sort the items in PQ in ascending order. Elements are sorted according to their hValue and it is a min PQ). Test your Java program with both the two start states A and B shown above. Show every state (and its heuristic value) that is expanded by the algorithm (i.e. removed from the PQ) as well as the final solution (i.e. goal state) by printing it to an output (text) file (called Output.A.txt and OutputB.txt, respectively). Also print the states on the screen. So, we want to see every move on the screen and in an output file. Simply print the contents of array in one line followed by the heuristic value of the state. Submit the following files on iKamva: Your written answers to questions 1-3 in a Word or a .pdf file. ⚫ Your Java source code. The two output files. 6. Demonstrate your program to a marker. Instructions will follow. Note: You have to complete the assignment on your own and write your own code. Plagiarism in any form will result in a mark of zero.