Can this be written in Java
Please leave comments
The 8-puzzle is a sliding puzzle that is played on a 3-by-3 grid with 8 square tiles labeled 1 through & plus a blank square. The goal is to rearrange the tiles so that they are in row-major order, using as few moves as possible. You are permitted to slide tiles either horizontally or vertically into the blank square. The following diagram shows a sequence of moves from an initial board (left) to the goal board (right) 5 lef 7 8 6 7 8 goal 1. To begin, create a data type that models an n-by-n board with sliding tiles. Implement data type Board with the following AP: publie elass Board ( public Board(ine111 tiles) e at trow, col) xing rosntation of this beard publie string toStringo publie int tileAt(int ro, int col) publie int size( publie boolean isGoal publie boolean equals (object y) public Iterablechoard> neighborsO boar d BoaEG Constructor. You may assume that the constructor receives an n-by-n array containing a permutation of the n' integers between 0 and n - 1, where O represents the blank square. You may also assume that 2 String representation. The toSinng) method returns a string composed of n lines. Each lne contains the n-by-n grid of tiles in row-major order, using 0 to designate the blank square. 786 Throw a java lang legalArgumentExcoption in tieAtO unless both row and col are between 0 and n- 1 The 8-puzzle is a sliding puzzle that is played on a 3-by-3 grid with 8 square tiles labeled 1 through 8, plus a blank square. The goal is to rearrange the tiles so that they are in row-major order, using as few moves as possible. You are permitted to slide tiles either horizontally or vertically into the blank square. The following diagram shows a sequence of moves from an initial board (left) to the goal board (right). 1 S lef 7 8 6 7 8 6 7 8 6 7 8 6 initial goal 1. Implement Best-First-Search algorithm In the previous assignment you implemented a Board class to represent a state of the 8-Puzzle game You also implemented a Depth-First-Search (DFS) and Breadth-First-Search (BFS) algorithm. In this assignment we want to generalize these search strategies with a Best-First-Search algorithm (not abbreviated for obvious reasons) In a Best-First-Search we start by generating a board for the initial state of the 8-puzzle. Every time a new node (board state) is generated it will be assigned a value indicating how "good" that state. For every generated node we will push it into a Priority Queue(PQ)using the "goodness" as the priority. After generating the initial state node and pushing it into the PQ the Best-First-Search algorithm wil keep iterating until the goal state is found or a given stopping condition (e g. a maximum running time is reached). In each iteration the Best-First-Search algorithm will remove the first board in the PQ and process that board. Processing a board means checking whether that board is the goal state, if that is the case the algorithm will terminate and return the sequence of boards (steps) from the initial state to the goal state. If the removed board is not the goal board then the neighbors of that board will be generated, for each neighbor its priority will be calculated and they will be inserted in the PQ. Then the next iteration will begin by removing again the first element in the queue. In order to easily return the path from a given state to the initial state consider modifying the Board class to accommodate a field containing the states-path traversed before generating that specific board configuration. Updating the path of a new state can be done directly when creating the Neighbors or with a specific UpdatePathToStartState). If the final state is reached the algorithm should return the corresponding board instance (which should include the path from the initial state), otherwise, If the algorithm fails to find a solution (stopping condition is reached before goal state) then should return nu mplement an abstract class BestFirst Search where the CalculatePriority) method is declared abstract The class should provide a Run method that executes the Best-First-Search algorithm. The run method should receive as an argument the number maximum millisecond to run the algorithm and it should be used as the stopping condition Implement two subclasses of BestFirst Search which must provide a concrete implementation of the CalculatePriority) method: 1. BreadthFirstSearch: Calculate the priority as the depth of the board in the game tree (the same as the number of actions performed to reach that state) 2. HeuristicSearch: Calculate the priority as the number of tiles misplaced (i.e. in a different position from the goal state). Here is a pseudocode of the BestFirst Search algorithm: BestFirstSearch(InitState, StoppingCondition) Create PQ p CalculatePriority(InitiState) PQInsert(cinitistate, p>) While(StoppingCondition is not True) nextState- PQ.RemoveFirst) if (nextState is goalState) return nextState foreach (neighbor in Pa) Neighbor.UpdatePathToStartState) p CalculatePriority(neighbor) PQInsert(neighbor, p>) 2. Test BreadthFirstSearch and HeuristicSearch algorithms. Write a code to run both algorithms with the following initial states and stopping conditions: Initial state: [1,2,3; 4,0,5; 7,8,6 Time limit: 2000 ms Il. Initial state: [0, 1,2; 4, 5,3; 7,8,6. Time limit: 2000 ms III Initial state: [0, 8, 6; 2,7,5; 1,3,4] Time limit: 2000 ms If the algorithm manages to find the goal state print the sequence the path from the initial state to the goal state. Otherwise print "The algorithm was unable to find the solution in the given time