Consider the Peg Solitaire game demonstrated in class and found online. A constrained grid is presented with locations where pegs may be present or absent. A move consists of a peg A jumping over a peg B which is directly above, below, to the left, or to the right of peg A. Peg A lands in the adjacent spot in the same direction. Peg A must land on a spot where there is no peg and within the specified constraints. Peg B is removed and play continues until no moves are possible. The player wins if a single peg remains in the center of the 7 x 7 grid. We represent a peg with the symbol and an empty spot with the symbol . The four kinds of moves that can be made are depicted below. The before and after pictures are separated with : Bottom peg jumps up, top peg jumps down, left peg jumps right, right peg jumps left. Here are three example starting conditions that you will be expected to solve. Plus Standard Rhombus You will need to be able to solve all three configurations shown above, some additional symmetrical configurations, one or more very simple single-move boards, as well as deal with unsolvable boards. Please implement the following method in the PegSolitare class: public static String solve(boolean[][] pegs) You dont have to implement the helper method tryMove, but it will mirror the presentation from class of Knights Tour: private static String tryMove(boolean[][] pegs, int startX, int startY, int jumpX, int jumpY, int endX, int endY) When a peg is moved, it starts at a location, jumps over a location, and ends at a location. solve works with a board which you may assume to be a 7x7 boolean array. Note that the array includes 16 locations where pegs are not allowed to land, 4 in each corner. Each element in the array will be true if a peg is in the corresponding position and false if it is not. A solution leaves a single peg in the center location (3, 3). solve should return a solution as a String if the board is solvable, and null if it is not solvable. The solution format is specified on the next page. Page 2 of 2 You should attempt to solve the game in the same manner as we solved Knights Tour in class. Unlike Knights Tour, there are many possible pieces that may move, rather than just 8 possible moves. You must examine each valid position in the board for a peg to move. Note that in the first row, (0, 0), (1, 0), (5, 0), and (6, 0) are all invalid locations that can be skipped you can consider those indexes if it simplifies your program, but never move a peg into those locations! The test program will only allow your solve method to run for up to 5 minutes for a given board. Your solve method will be terminated and you will not receive credit for that example if it takes longer. Notice that, unlike Knight's Tour, moves can revisit spaces in Peg Solitaire so we cant leave the moves that we made in the original array to indicate the solution. Instead, we have to assemble the solution in a different way. It is tricky to assemble the solution, so read the next paragraphs carefully to help you think about how to do this. Upon finding a successful solution you should return a String that indicates the sequence of moves from beginning to end. Each move should be separated by a space (or newline) and should look like this: oldX oldY newX newY where oldX and oldY are the x and y location of the peg before the jump occurred and newX and newY are the x and y location of where the peg lands. If there is no solution, solve should return null. The easiest way to build the solution string is to consider the return value from a given recursive call. If solve or tryMove returns null, the board is not solved from that position, similar to the false return value from Knights Tour. (Note that you can compare with null by using == null.) Otherwise, the board is solved and we should include the move we just made into the solution we received from our recursive call. (Make sure you dont throw away the return value from any call to solve or tryMove; save it into a variable like we did with Knights Tour! Make sure to include each move only once; if solve and tryMove call each other and each examines a move once, only one should include the move in the solution!) Each recursive call return includes its move, which means we can build the solution string backwards from the end with concatenation, one move at a time. (Remember the Maze exercise which showed that the recursive call stack includes the solution!) As with Knights Tour, the code will have to recognize when it enters a solved state and use that to indicate to the caller that there is a solution. Notice that when we first recognize that the board is solved, there may not be any moves visible within that method call; in that case, return a non-null String (since we are solved) with nothing in it (since no moves are visible). Important note: When entered manually or printed out, 2D arrays in Java are normally considered to be in row-major [y][x] order (e.g. a[0] accesses the first row of the 2D array a), but we found it more convenient to use [x][y] indexing for Knights Tour; each dimension in our data structure can be used for whatever purpose we like. In the case of Peg Solitare, we are given input arrays which the solution is specified for. Because the movement rules are isotropic (allowed the same way along both axes) and boards will be symmetrical, you may access the board using [x][y] or [y][x] indexing, but you must be consistent in your choice throughout your solution. (There also may be one or more tests of boards requiring just one move; for those tests, the solver will be set up to allow either ordering.) EXTRA CREDIT (3 Points): Remove all uses of for and while from the solution. Please note that this will make your solution much more complicated! You may want to solve using loops first.