# Cracker Barrel puzzle solver using Recursion

• February 14th, 2012, 12:37 AM
shiftasterisk
Cracker Barrel puzzle solver using Recursion
Hey everyone,

Ok, so I have to write this program that solves the Cracker Barrel puzzle aka Triangular Peg Solitaire. For more background info about the puzzle you can check out (George Bell's Triangular Peg Solitaire Page), that's where I got a bunch of my information anyway. So what we had to do was use a recursive search to solve this puzzle down to 1 peg and output the sequence of moves in the format (from, over, into) with from being the slot where the peg came from, over being the peg jumped over, and into being the blank space where the peg will land after jumping over the other peg. So what I did so far was use keep a SAX count described on that website so that I wouldn't have to deal with backtracking due to dead ends and attempted recursion even though I've always been iffy with it. I used a stack to keep track of the moves and my methods for getSax and isSolved seem to be working correctly from my tests.

Ive been looking at this code for hours and I am currently stuck with these arraylist errors and my brain is too fried to think for today. I'm going to work on it again tomorrow, so any help is really appreciated. I just want a fresh pair of eyes to take a look at it just for the assurance that i'm not completely off the mark and maybe for some advice/help.

Thanks again

Code Java:

```  import java.util.Stack; import java.util.ArrayList;   public class HiQ {   public static void main(String[] args) {   //Use ini to set up the puzzle, simply denote the blank space as 0 and the pegs as 1's; int[] ini = {1,1,1,1,0,1,1,1,1,1,1,1,1,1,1}; // The sax, blank and solved check int sax = getSAX(ini); // int blank = getBlank(ini); boolean solved = isSolved(ini); ArrayList a = new ArrayList(2); Stack moves = new Stack();   a.add(ini); a.add("n"); getSolution(a, moves);   } public static int getSAX(int[] puz){ //calculates the SAX of the puzzle, which makes this puzzle easier to solve. Also determines if the puzzle is solvable // source: [url=http://home.comcast.net/~gibell/pegsolitaire/tindex.html]George Bell's Triangular Peg Solitaire Page[/url] // SAX = S+A - X int sax=0; int edge1 = puz[1] + puz[3] + puz[6]; int edge2 = puz[2] + puz[5] + puz[9]; int edge3 = puz[11] + puz[12] + puz[13]; // these if's calculate the inner edges of the puzzle AKA the S if (edge1 >= 2){ sax +=1; } if (edge2 >= 2){ sax +=1; } if (edge3 >= 2){ sax+=1; } //these if's calculate the inner +1's of the puzzle AKA the A   if (puz[4] == 1){ sax+= 1; } if (puz[7] == 1){ sax += 1; } if (puz[8] == 1){ sax += 1; } // these if's calculate the "-1"'s of the puzzle AKA the X if (puz[0] == 1) { sax -= 1; } if (puz[3] == 1){ sax -= 1; } if (puz[5]== 1){ sax -= 1; } if (puz[10]==1){ sax -= 1; } if (puz[12]==1){ sax -= 1; } if (puz[14] == 1){ sax -= 1; } // end of -1's return sax; }   public static boolean isSolved(int[] puz){ int sum = 0; for(int x = 0; x<= 14; x++){ sum+= puz[x]; } if(sum == 1){ return true; } else { return false; } }   /* I dont think this is needed public static int getBlank(int[] puz){ int blank = 0; for(int x=0; x<= 14; x++){ if(puz[x] == 0){ blank = x; } } return blank; } */ public static ArrayList getMove(ArrayList a){ int[] puz = (int[]) a.get(0); ArrayList move = a; String check = ""; int x = 0; do { switch(x){ case 0: move = Move(puz, 0, 1, 3); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 0, 2, 5); } break;   case 1: move = Move(puz, 1, 3, 6); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 1, 4, 8); }break;   case 2: move = Move(puz, 2, 4, 7); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 2, 5, 9); }break;   case 3: move = Move(puz, 3, 1, 0); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 3, 6, 10); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 3, 7, 12); } } break;   case 4: move = Move(puz, 4, 7, 11); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 4, 8, 13); }break;   case 5: move = Move(puz, 5, 7, 11); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 5, 8, 12); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 5, 9, 14); } } break;   case 6: move = Move(puz, 6, 3, 1); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 6, 7, 8); }break;   case 7: move = Move(puz, 7, 4, 2); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 7, 8, 9); }break;   case 8: move = Move(puz, 8, 4, 1); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 8, 7, 6); }break;   case 9: move = Move(puz, 9, 5, 3); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 9, 8,7); }break;   case 10: move = Move(puz, 10, 6, 3); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 10, 11, 12); }break;   case 11: move = Move(puz, 11, 7, 4); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 11, 12, 13); }break;   case 12: move = Move(puz, 5, 7, 11); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 5, 8, 12); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 5, 9, 14); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 5, 9, 14); } } } break;   case 13: move = Move(puz, 13, 8, 4); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 13, 12, 11); }break;   case 14: move = Move(puz, 14, 9, 5); check = (String) move.get(1); if (check.equals("n")){ move = Move(puz, 14, 13, 12); }break; default: System.out.println("Something's wrong");   } x++; } while (check.equals("n") || x < 15);   return move; }   public static ArrayList Move(int[] puz, int x, int y, int z){ int sax; int temp[] = puz; String word = ""; int x1 = x+1; int y1 = y+1; int z1 = z+1; ArrayList a = new ArrayList(2); // If the Blank space is at 0 if(puz[x] == 0 && puz[y] != 0 && puz[z] != 0){   temp[x] = 1; temp[y] = 0; temp[z] = 0; sax = getSAX(temp);   if (sax>= 0){ word = "("+z1+","+ y1 + "," + x1+")"; a.set(0, temp); a.set(1, word); } else { word = "n"; a.set(0, puz); a.set(1,word ); } } return a; }   public static void getSolution(ArrayList a, Stack move){ Stack moves = move; ArrayList var = a; int[] puz = (int[]) a.get(0); if (isSolved(puz) == true){ while (moves.isEmpty() == false){ System.out.println(moves.pop()); } } else { var = getMove(var); moves.push(var.get(1)); getSolution(var, moves);   } } }```
• February 14th, 2012, 06:32 AM
Norm
Re: Cracker Barrel puzzle solver using Recursion
Quote:

arraylist errors
Please copy and paste here the full text of the error messages.
• February 14th, 2012, 07:02 AM
shiftasterisk
Re: Cracker Barrel puzzle solver using Recursion
Oh yea, sorry about that. I just woke up and will start working on it soon.

Quote:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 0
at java.util.ArrayList.RangeCheck(ArrayList.java:547)
at java.util.ArrayList.get(ArrayList.java:322)
at HiQ.getMove(HiQ.java:112)
at HiQ.getSolution(HiQ.java:277)
at HiQ.main(HiQ.java:25)
Java Result: 1
• February 14th, 2012, 07:29 AM
Norm
Re: Cracker Barrel puzzle solver using Recursion
At line 112 in getMove() the code is trying to get an element in an empty list. (Size: 0)
Looks like a logic error.
Either put something into the list
or test if the list is empty before trying to get something from it.
• February 14th, 2012, 08:25 AM
shiftasterisk
Re: Cracker Barrel puzzle solver using Recursion
Alright so I've come up to this point and now I'm getting a stackoverflow error which I was assuming I'd have at some point or another. Thanks again for the help.

Quote:

at HiQ.Move(HiQ.java:247)
at HiQ.getMove(HiQ.java:111)
at HiQ.getSolution(HiQ.java:278)
at HiQ.getSolution(HiQ.java:281)
at HiQ.getSolution(HiQ.java:281)
at HiQ.getSolution(HiQ.java:281)
at HiQ.getSolution(HiQ.java:281)
at HiQ.getSolution(HiQ.java:281)
Code Java:

```import java.util.Stack; import java.util.ArrayList;   public class HiQ {   public static void main(String[] args) {   //Use ini to set up the puzzle, simply denote the blank space as 0 and the pegs as 1's; int[] ini = {1,1,1,1,0,1,1,1,1,1,1,1,1,1,1}; // The sax, blank and solved check int sax = getSAX(ini); //int blank = getBlank(ini); boolean solved = isSolved(ini); ArrayList a = new ArrayList(2); Stack moves = new Stack();   a.add(ini); a.add("n"); getSolution(a, moves);   } public static int getSAX(int[] puz){ //calculates the SAX of the puzzle, which makes this puzzle easier to solve. Also determines if the puzzle is solvable // source: [url=http://home.comcast.net/~gibell/pegsolitaire/tindex.html]George Bell's Triangular Peg Solitaire Page[/url] // SAX = S+A - X int sax=0; int edge1 = puz[1] + puz[3] + puz[6]; int edge2 = puz[2] + puz[5] + puz[9]; int edge3 = puz[11] + puz[12] + puz[13]; // these if's calculate the inner edges of the puzzle AKA the S if (edge1 >= 2){ sax +=1; } if (edge2 >= 2){ sax +=1; } if (edge3 >= 2){ sax+=1; } //these if's calculate the inner +1's of the puzzle AKA the A   if (puz[4] == 1){ sax+= 1; } if (puz[7] == 1){ sax += 1; } if (puz[8] == 1){ sax += 1; } // these if's calculate the "-1"'s of the puzzle AKA the X if (puz[0] == 1) { sax -= 1; } if (puz[3] == 1){ sax -= 1; } if (puz[5]== 1){ sax -= 1; } if (puz[10]==1){ sax -= 1; } if (puz[12]==1){ sax -= 1; } if (puz[14] == 1){ sax -= 1; } // end of -1's return sax; }   public static boolean isSolved(int[] puz){ int sum = 0; for(int x = 0; x<= 14; x++){ sum+= puz[x]; } if(sum == 1){ return true; } else { return false; } }   /* I dont think this is needed public static int getBlank(int[] puz){ int blank = 0; for(int x=0; x<= 14; x++){ if(puz[x] == 0){ blank = x; } } return blank; } */ public static ArrayList getMove(ArrayList a){ ArrayList move = a; int[] puz = (int[]) move.get(0); String check = (String) move.get(1); int x = 0; do { switch(x){ case 0: move = Move(puz, 0, 1, 3);     if (check.equals("n")){ move = Move(puz, 0, 2, 5); } break;   case 1: move = Move(puz, 1, 3, 6);   if (check.equals("n")){ move = Move(puz, 1, 4, 8); }break;   case 2: move = Move(puz, 2, 4, 7);   if (check.equals("n")){ move = Move(puz, 2, 5, 9); }break;   case 3: move = Move(puz, 3, 1, 0);   if (check.equals("n")){ move = Move(puz, 3, 6, 10);   if (check.equals("n")){ move = Move(puz, 3, 7, 12); } } break;   case 4: move = Move(puz, 4, 7, 11);   if (check.equals("n")){ move = Move(puz, 4, 8, 13); }break;   case 5: move = Move(puz, 5, 7, 11);   if (check.equals("n")){ move = Move(puz, 5, 8, 12);   if (check.equals("n")){ move = Move(puz, 5, 9, 14); } } break;   case 6: move = Move(puz, 6, 3, 1);   if (check.equals("n")){ move = Move(puz, 6, 7, 8); }break;   case 7: move = Move(puz, 7, 4, 2);   if (check.equals("n")){ move = Move(puz, 7, 8, 9); }break;   case 8: move = Move(puz, 8, 4, 1);   if (check.equals("n")){ move = Move(puz, 8, 7, 6); }break;   case 9: move = Move(puz, 9, 5, 3);   if (check.equals("n")){ move = Move(puz, 9, 8,7); }break;   case 10: move = Move(puz, 10, 6, 3);   if (check.equals("n")){ move = Move(puz, 10, 11, 12); }break;   case 11: move = Move(puz, 11, 7, 4);   if (check.equals("n")){ move = Move(puz, 11, 12, 13); }break;   case 12: move = Move(puz, 5, 7, 11);   if (check.equals("n")){ move = Move(puz, 5, 8, 12);   if (check.equals("n")){ move = Move(puz, 5, 9, 14);   if (check.equals("n")){ move = Move(puz, 5, 9, 14); } } } break;   case 13: move = Move(puz, 13, 8, 4);   if (check.equals("n")){ move = Move(puz, 13, 12, 11); }break;   case 14: move = Move(puz, 14, 9, 5);   if (check.equals("n")){ move = Move(puz, 14, 13, 12); }break; default: System.out.println("Something's wrong");   } x++; } while (check.equals("n") && x < 15);   return move; }   public static ArrayList Move(int[] puz, int x, int y, int z){ int sax; int temp[] = puz; String word = ""; int x1 = x+1; int y1 = y+1; int z1 = z+1; ArrayList a = new ArrayList(2); // If the Blank space is at 0 if(puz[x] == 0 && puz[y] != 0 && puz[z] != 0){   temp[x] = 1; temp[y] = 0; temp[z] = 0; sax = getSAX(temp);   if (sax>= 0){ word = "("+z1+","+ y1 + "," + x1+")"; a.add(0, temp); a.add(1, word); } else { word = "n"; a.add(0, puz); a.add(1,word ); } } return a; }   public static void getSolution(ArrayList a, Stack move){ Stack moves = move; //ArrayList var = a; int[] puz = (int[]) a.get(0); if (isSolved(puz) == true){ while (moves.isEmpty() == false){ System.out.println(moves.pop()); } } else { getMove(a); moves.push(a.get(1)); move.peek(); getSolution(a, moves);   } } }```
• February 14th, 2012, 08:29 AM
Norm
Re: Cracker Barrel puzzle solver using Recursion
Looks like the code is in an infinite loop.
You must add code to getSolution so that it stops calling itself.