In Java:
Please read the entire assignment before beginning it! 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 7x7 grid We represent a peg with the symbol and an empty spot with the symbol O.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[]I] pegs) You don't have to implement the helper method tryMove, but it will mirror the presentation from class of Knight's 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 1 of2 You should attempt to solve the game in the same manner as we solved Knight's Tour in class. Unlike Knight's 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! th in ke Notice that, unlike Knight's Tour, moves can revisit spaces in Peg Solitaire so we can't 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 Knight's 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 don't throw away the return value from any call to solve or tryMove; save it into a variable like we did with Knight's 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 Knight's Tour, the code will have to recognize when it enters a solved state and use that to indicate to the caller that there the visible within that in it (since no moves are visible thod call: in that case Ive in Important note: When entered manually or printed out, 2D arrays in Java are normally considered to be in row-major [yl[x] order (e.g. a[0 accesses the first row of the 2D array a), but we found it more convenient to use [x][yl indexing for Knight's 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][yl or [yx] 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 Please read the entire assignment before beginning it! 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 7x7 grid We represent a peg with the symbol and an empty spot with the symbol O.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[]I] pegs) You don't have to implement the helper method tryMove, but it will mirror the presentation from class of Knight's 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 1 of2 You should attempt to solve the game in the same manner as we solved Knight's Tour in class. Unlike Knight's 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! th in ke Notice that, unlike Knight's Tour, moves can revisit spaces in Peg Solitaire so we can't 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 Knight's 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 don't throw away the return value from any call to solve or tryMove; save it into a variable like we did with Knight's 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 Knight's Tour, the code will have to recognize when it enters a solved state and use that to indicate to the caller that there the visible within that in it (since no moves are visible thod call: in that case Ive in Important note: When entered manually or printed out, 2D arrays in Java are normally considered to be in row-major [yl[x] order (e.g. a[0 accesses the first row of the 2D array a), but we found it more convenient to use [x][yl indexing for Knight's 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][yl or [yx] 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
