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. b. A tile may move into an adjacent empty cell with unit cost. A tile may hop over at most two other tiles into an empty cell with a cost equal to the number of tiles h over Initial Next Cost BBBWWEW BBBWWEW BBBWWEW BBBWEWW BBBEWWW BBEWWBW 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 heuristic function Java to solve the sliding block puzzle using your 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 e Ou ormat in your console EWBWBWB : G(n)-0:h(n)-3 WTYBEBIYB : 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 = 11