Recursive Backtracking for Peg Solitaire

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 . Example moves (therelevant portion of the board before and after the move is separated with a symbol):

Bottom peg jumps up. Right peg jumps left.

Specifically, you will be given the following three starting conditions (along with one unsolvable board):

You will need to be able to solve all three configurations shown above. You are requested to implementthe following two methods of PegSolitaire according to the specification.

public static boolean solve(boolean[][] pegs, StringStack solution)

private static boolean tryMove(boolean[][] pegs, int startX, int startY, int jumpX,int jumpY, int endX, int endY, StringStack solution)

(You dont have to implement tryMove, but it will mirror the presentation from class of Knights Tour.)

solve should take the board, which you may assume to be a 7x7 boolean array, as well as a StringStack,which you may assume to be a new empty StringStack wrapper object. Note that the array includes 16 locations where pegs may not be moved, 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. solve should return true if the board is olvable, and false if it is not. A solution leaves a single peg in the center location (3, 3). One of thetests is a board which is not solvable but is tested because a solver which allows moves on theunreachable positions will detect a solution. You should attempt to solve the game in the same manneras we solved Knights Tour in class. You must examine each valid position in the board for a peg to move;you should search all positions with y coordinate 0 (the entire first row) from left to right for pegs,followed by the entire second row (y coordinate = 1) from left to right, etc. to the last row. (Note that inthe first row, (0, 0), (1, 0), (5, 0), and (6, 0) are all invalid locations that can be skipped you can considerthose indexes if it simplifies your program, but never move a peg into those locations!) For thepurposes of the directions specified, the upper left coordinate of the array is (0,0) and the lower rightcoordinate is (6, 6) (note that neither of these are valid locations). For any peg that can be moved, youmust recursively try moves in the following order: first try moving up (smaller y), then down (larger y),then left (smaller x), then right (larger x). (This is known as the Konami Order.) This way, you will arriveat the same solutions that the test program does. Moves will be made in the board and pushed ontothe stack as they are attempted. As with Knights Tour, attempted moves which do not result in asolution should be cleaned up / undone!

You will build the solution as you perform moves in the provided StringStack. Each move as described onthe StringStack should be a string which will look like the following:

(oldX, oldY) -> (newX, newY)

where oldX and oldY are the x and y location of the peg before the jump occurred and newX and newYare the x and y location of the peg after the jump occurred. The solution to the Plus starting condition isspecified in the test program but the other two solutions are encoded as MD5 hashes to discouragecheating! Remember to clean up the stack as dead ends are encountered!

The return value of solve will be true if a solution is found, false if not. If a solution is found, theStringStack passed as an argument should contain the first solution it finds, in the format specified inthe above paragraph; otherwise, it should be empty.

Important note: if you consider how arrays are written in .java files versus the indexing scheme, youmay be considering each 2D array as its transpose, e.g. the coordinate [1][0] will access the first elementin the second row as written in the Java program. PLEASE NOTE all solvable boards will be symmetrical,so you need not worry about this distinction (what you see in the .java file versus how they appear toyour program). HOWEVER, inside of your solve method, you must consider elements and moves inthe order specified: first moving the peg to a smaller y coordinate, then a larger y, then a smaller x,and finally a larger x coordinate!! This will be important when putting the moves in the stack!

EXTRA CREDIT (2 Points): Remove all uses of for and while from the solution.

EXTRA CREDIT (5 Points): Note that if the restrictions to move in the corners of the 7 by 7 board areremoved, your solver will take an extremely long time for the standard board. Determine a heuristic forthe search (which determines which order in which to consider subsequent moves based on the state ofthe board) which is capable of solving the standard board without the corner restrictions in a reasonableamount of time. Write solveHeuristic which uses this heuristic. Please document the heuristic used in acomment. Note that this extra credit is very challenging!

//Here is StringStack.java

public class StringStack {

private InternalStringStack stack;

public StringStack() { // Create an empty stack stack = null; }

public void push(String s) { stack = new InternalStringStack(s, stack); }

public int size() { if (stack == null) return 0; return stack.size(); }

public String top() { if (stack == null) return null; return stack.getData(); } public String pop() { if (stack == null) return null; String s = stack.getData(); stack = stack.getRest(); return s; } public boolean isEmpty() { return stack == null; }

}

//Here is InternalStringStack.java

public class InternalStringStack { private String data; private InternalStringStack rest; public InternalStringStack(String data, InternalStringStack rest) { this.data = data; this.rest = rest; } public String getData() { return data; } public InternalStringStack getRest() { return rest; } public int size() { if (rest == null) return 1; return 1 + rest.size(); } }

public class InternalStringStack { private String data; private InternalStringStack rest; public InternalStringStack(String data, InternalStringStack rest) { this.data = data; this.rest = rest; } public String getData() { return data; } public InternalStringStack getRest() { return rest; } public int size() { if (rest == null) return 1; return 1 + rest.size(); } }

//Here is PegSolitaireTest.java

import java.io.File;

import java.nio.file.Files; import java.nio.file.Paths; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.util.Arrays;

public class PegSolitaireTest {

public static String getSolution(boolean[][] board) { StringStack stack = new StringStack(); if (PegSolitaire.solve(board, stack)) { String cat = stack.pop(); String s; while ((s = stack.pop()) != null) { cat = s + ", " + cat; } return cat; } return null; }

public static void main(String[] args) throws NoSuchAlgorithmException { int points = 0; try { try { String source = new String(Files.readAllBytes(Paths.get("src" + File.separator + "PegSolitaire.java"))); boolean ec = true; if (source.matches("(?s).*\\sfor[\\s\\(].*")) { System.out.println( "Detected 'for' statement in your program! This is OK but remove all 'for's and 'while's for extra credit."); ec = false; } if (source.matches("(?s).*\\swhile[\\s\\(].*")) { System.out.println( "Detected 'while' statement in your program! This is OK but remove all 'for's and 'while's for extra credit."); ec = false; } if (ec) { System.out.println("Detected no 'for' or 'while'! 2 points of extra credit."); points += 2; } } catch (Exception e) { System.out.println( "Couldn't find PegSolitaire.java! Run this from the same Eclipse project as PegSolitaire with no package."); }

boolean[][] testSimple = { { false, false, false, false, false, false, false }, { false, false, false, false, false, false, false }, { false, false, false, false, false, false, false }, { false, true, true, false, false, false, false }, { false, false, false, false, false, false, false }, { false, false, false, false, false, false, false }, { false, false, false, false, false, false, false } }; String simpleSolution = getSolution(testSimple); if ("(1, 3) -> (3, 3)".equals(simpleSolution) || "(3, 1) -> (3, 3)".equals(simpleSolution)) { System.out.println("Your code correctly found the solution to a simple board! 10/10"); points += 10; } else { System.out.println( "Your code couldn't find a solution to a simple board requiring one move, so I'm exiting now with 0 points."); System.out.println("Solution seen: "+simpleSolution); return; } boolean[][] testUnsolvable = { { false, false, false, false, false, false, false }, { false, false, true, true, false, false, false }, { false, true, false, false, false, false, false }, { false, false, true, false, false, false, false }, { false, false, false, false, false, false, false }, { false, false, false, false, false, false, false }, { false, false, false, false, false, false, false } }; String unsolvableSolution = getSolution(testUnsolvable); if (unsolvableSolution != null) { System.out.println( "You found a solution to an unsolvable board! You are either allowing moves into the corners or have some other bugs. 0/10"); } else { System.out.println("You didn't find a solution to a simple unsolvable board! 10/10"); points += 10; } System.out.println("Attempting to solve 'plus' board:"); boolean[][] testPlus = { { false, false, false, false, false, false, false }, { false, false, false, true, false, false, false }, { false, false, false, true, false, false, false }, { false, true, true, true, true, true, false }, { false, false, false, true, false, false, false }, { false, false, false, true, false, false, false }, { false, false, false, false, false, false, false } }; String plusSolution = getSolution(testPlus); if (plusSolution != null) { String plusSolution1 = "(3, 2) -> (3, 0), (3, 4) -> (3, 2), (1, 3) -> (3, 3), (3, 3) -> (3, 1), (3, 0) -> (3, 2), (5, 3) -> (3, 3), (3, 2) -> (3, 4), (3, 5) -> (3, 3)"; String plusSolution2 = "(2, 3) -> (0, 3), (4, 3) -> (2, 3), (3, 1) -> (3, 3), (3, 3) -> (1, 3), (0, 3) -> (2, 3), (3, 5) -> (3, 3), (2, 3) -> (4, 3), (5, 3) -> (3, 3)"; if (plusSolution1.equals(plusSolution)) { System.out.println("Correct solution to the plus board! 30/30"); points += 30; } else if (plusSolution2.equals(plusSolution)) { System.out.println("It looks like you're scanning column by column instead of row by row! 25/30"); points += 25; } else { System.out.println("Unexpected solution! 0/30"); System.out.println(plusSolution); } } else { System.out.println("Your code didn't find a solution! 0/30"); } System.out.println("Attempting to solve 'standard' board:"); boolean[][] testStandard = { { false, false, true, true, true, false, false }, { false, false, true, true, true, false, false }, { true, true, true, true, true, true, true }, { true, true, true, false, true, true, true }, { true, true, true, true, true, true, true }, { false, false, true, true, true, false, false }, { false, false, true, true, true, false, false } }; String standardSolution = getSolution(testStandard); byte[] standardSolution1 = { -78, 17, -12, 124, -65, 94, -9, 38, -123, 104, -68, 64, 98, 0, -57, 24 }; byte[] standardSolution2 = { 87, -106, -18, 77, 33, 116, -74, -108, 85, 66, -15, -124, 101, 10, -2, 92 }; byte[] standardSolution3 = { 125, 111, -98, -4, -124, -61, -44, -65, -80, -124, -96, -1, 61, 79, -124, 21 }; byte[] standardSolution4 = { 74, -39, -96, 8, -84, -123, 39, 104, -28, 46, -24, 48, -37, 20, -37, 90 }; MessageDigest md5 = MessageDigest.getInstance("MD5"); byte[] standardBytes = md5.digest(standardSolution.getBytes()); if (Arrays.equals(standardBytes, standardSolution1)) { System.out.println("Correct solution to the standard board! 25/25"); points += 25; } else if (Arrays.equals(standardBytes, standardSolution2)) { System.out.println("It looks like you're scanning column by column instead of row by row! 20/25"); points += 20; } else if (Arrays.equals(standardBytes, standardSolution3)) { System.out.println("It looks like you're not using the up-down-left-right order! 20/25"); points += 20; } else if (Arrays.equals(standardBytes, standardSolution4)) { System.out.println( "It looks like you're scanning column by column instead of row by row and not using the up-down-left-right order!"); points += 15; } else { System.out.println("Unexpected solution! 0/25"); System.out.println(standardSolution); System.out.println(Arrays.toString(standardBytes)); } System.out.println("Attempting to solve 'rhombus' board:"); boolean[][] testRhombus = { { false, false, false, true, false, false, false }, { false, false, true, true, true, false, false }, { false, true, true, true, true, true, false }, { true, true, true, false, true, true, true }, { false, true, true, true, true, true, false }, { false, false, true, true, true, false, false }, { false, false, false, true, false, false, false } }; String rhombusSolution = getSolution(testRhombus); byte[] rhombusBytes = md5.digest(rhombusSolution.getBytes()); byte[] rhombusSolution1 = { 27, 122, -43, -15, 42, -15, -124, -17, 58, 91, -50, -126, 44, -124, -64, 97 }; if (Arrays.equals(rhombusBytes, rhombusSolution1)) { System.out.println("Correct solution to the rhombus board! 25/25"); points += 25; } else { System.out.println( "Unexpected solution! (Note, this one is very picky - if you got partial credit above, fix your solution!) 0/25"); System.out.println(rhombusSolution); System.out.println(Arrays.toString(rhombusBytes)); } } finally { System.out.println("Currently does not check for the 'difficult' extra credit!"); System.out.println("Please note the academic dishonesty policy can affect your score!"); System.out.println("Tentative total: " + points + "/100"); } }

}