USE JAVA! Please be as detailed and as specific as possible. Thank you!

Consider a sliding block puzzle with the following initial configuration: There are three black tiles (B), three white tiles (W), and an empty cell (E). The puzzle has the following moves a. A tile may move into an adjacent empty cell with unit cost. b. A tile may hop over at most two other tiles into an empty cell with a cost equal to the number of tiles hopped over Cost Initial BBBWWEW BBBWWEW Next BBBWEWw BBBEWWw BBEWWBW BBBWWEW The goal of the puzzle is to have all of the white tiles to the left of all of the black tiles (regardless of the position of the blank cell). You are to: 1. 2. 3. Specify a heuristic function, h, for this problem and show the search tree produced by the algorithm A* using this heuristic function (show the explicit portion of the search tree). Determine and show that your function never overestimates the true cost of reaching a goal or otherwise. Implement a program in C, C++ or Java to solve the sliding block puzzle using your heuristic function. The input to the program should be given interactively in your console as follows (the example below illustrates the initial state given above): Enter initial state: EWBWBWB nat EWBWBWB : G(n) = 0 : h(n) = 3 WWBEBWB : G(n)-2 :h(n) 2 WWBWBEB G(n)-3 :h(n)1 WWEWBBB : G(n) = 5 : h(n) = 0 Total cost 5 Number of states expanded = 1 1 Consider a sliding block puzzle with the following initial configuration: There are three black tiles (B), three white tiles (W), and an empty cell (E). The puzzle has the following moves a. A tile may move into an adjacent empty cell with unit cost. b. A tile may hop over at most two other tiles into an empty cell with a cost equal to the number of tiles hopped over Cost Initial BBBWWEW BBBWWEW Next BBBWEWw BBBEWWw BBEWWBW BBBWWEW The goal of the puzzle is to have all of the white tiles to the left of all of the black tiles (regardless of the position of the blank cell). You are to: 1. 2. 3. Specify a heuristic function, h, for this problem and show the search tree produced by the algorithm A* using this heuristic function (show the explicit portion of the search tree). Determine and show that your function never overestimates the true cost of reaching a goal or otherwise. Implement a program in C, C++ or Java to solve the sliding block puzzle using your heuristic function. The input to the program should be given interactively in your console as follows (the example below illustrates the initial state given above): Enter initial state: EWBWBWB nat EWBWBWB : G(n) = 0 : h(n) = 3 WWBEBWB : G(n)-2 :h(n) 2 WWBWBEB G(n)-3 :h(n)1 WWEWBBB : G(n) = 5 : h(n) = 0 Total cost 5 Number of states expanded = 1 1