Thread: 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();
 
        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);
 
        }
    }
}