Second year computer science
Please leave notes for better understanding
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 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 Comparing two boards for cquality. Two boards arc equal if they have the same size and their corresponding tiles are in the same positions. The equals0 method is inherited from java.lang Object, so it must obey all of Java's requirements. Neighboring boards. The neighbors) method returns an iterable containing the neighbors of the board. Depending on the location of the blank square, a board can have 2, 3, or 4 neighbors. 1 2 3 4 78 6 neighbor 2 board neighbor1 neighbor 3 Performance requirements. In the worst case, your implementation must support size() and tileAt) in constant time; the constructor, isGoal0, equals0, toString0, and neighbors0 in time proportional to n' (or better). 2. Create a game tree data type. In this part you will implement a GameTree class with the following API: public class GameTree f public GameTree (Board initial, int depth) public string DFS ) public String BFS // creates a game tree with the given depth // travexses the tree using DES craverses the tre using BrS Constructor. The constructor receives the initial board and creates a game tree where the branches represent the possible movements to perform at a given board. The tree should be created up to the specified depth Depth 1 means only the root node, depth 2 means root node plus one level neighbor boards representing the results of the applicable moves...and so on. For this game tree DFS and BFS return the same String: 013 425 786 4 2 5 7 8 6 Constructor. The constructor receives the initial board and creates a game tree where the branches represent the possible movements to perform at a given board. The tree should be created up to the specified depth. Depth-1 means only the root node, depth 2 means root node plus one level neighbor boards representing the results of the applicable moves... and so on. For this game tree DFS and BFS return the same String: 013 425 786 103 425 786 413 025 786 Depth First Search (DFS), This method will return the sequence of string representations of the boards generated by this traversal algorithm (an empty line should be added between boards). Breadth First Search (DFS). This method will return the sequence of string representations o generated by this traversal algorithm (an empty line should be added between boards)
