Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Cracker Barrel puzzle solver using Recursion

1. ## 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

```
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();

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);

}
}
}```

2. ## Re: Cracker Barrel puzzle solver using Recursion

arraylist errors
Please copy and paste here the full text of the error messages.

3. ## Re: Cracker Barrel puzzle solver using Recursion

Oh yea, sorry about that. I just woke up and will start working on it soon.

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

4. ## 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.

5. ## 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.

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)
```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();

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+")";
} else {
word = "n";
}
}
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);

}
}
}```

6. ## 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.