Hi,
I'm trying to work out an algorithm to solve the game "peg solitaire" for this structure:
x x x x x
x x x x x
x x x x x
x x x x x
x x x x x
x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x
x x x x x x x O x x x x x x x
x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x
x x x x x
x x x x x
x x x x x
x x x x x
x x x x x
The goal of this game is to remove all pegs by jumping over another peg to an open field (e.g. the O in the middle) end ending up with the last peg in the center position.
Now, I'm trying to use backtracking for this: look for all possible moves (4 when starting) and then try one, look for all possible moves and then try one...
The problem is that I get a java.lang.outOfMemoryException: heap space and I don't know why.
The board is coded as followed:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
This is the algorithm:
private void fillBoard(){
spelBord = new int[17][17];
for(int i=0;i<289;i++)
if( (i%17>5 && i%17<11 && i>17 && i<272) || (((i%17>0 && i%17<6) || (i%17<16 && i%17>10)) && i>102 && i<187 ) )
spelBord[i%17][i/17]=1;
spelBord[8][8]=2;
kopie = new int[15][15];
for(int i=1;i<16;i++)
System.arraycopy(spelBord, 1, kopie[i-1], 0, 15);
d.setSpelBord(kopie);
}
public void calculateMoves(){
zettenLijst.add(addPossibleMoves(8,8));
tryMove(zettenLijst.get(0).get((int)(Math.random()*3)));
}
private boolean tryMove(Zet z){
if(solved)
return true;
zetten.add(z);
spelBord[z.getRijVan()][z.getKolVan()]=2;
spelBord[z.getRijOver()][z.getKolOver()]=2;
spelBord[z.getRijNaar()][z.getKolNaar()]=1;
if(zetten.size()==124 && spelBord[8][8]==2){
resultatenLijst = new ArrayList<Zet>(zetten);
solved=true;
return true;
}
addList();
walkThroughList(zettenLijst.get(zettenLijst.size()-1));
return false;
}
private boolean walkThroughList(ArrayList<Zet> lijst){
if(solved)
return true;
for(Zet z:lijst){
if(tryMove(z))
return true;
else undoMove(z);
}
return false;
}
private void undoMove(Zet z){
spelBord[z.getRijVan()][z.getKolVan()]=1;
spelBord[z.getRijOver()][z.getKolOver()]=1;
spelBord[z.getRijNaar()][z.getKolNaar()]=2;
zetten.remove(z);
}
public void addList(){
for(int rij=1;rij<16;rij++)
for(int kol=1;kol<16;kol++)
if(spelBord[rij][kol]==2)
zettenLijst.add(addPossibleMoves(rij,kol));
}
private ArrayList<Zet> addPossibleMoves(int rij, int kol){
ArrayList<Zet> lijst = new ArrayList<Zet>();
if(spelBord[rij-1][kol]==1){
if(spelBord[rij-2][kol]==1){
lijst.add(new Zet(rij-2,kol,rij-1,kol,rij,kol));}}
if(spelBord[rij][kol+1]==1){
if(spelBord[rij][kol+2]==1){
lijst.add(new Zet(rij,kol+2,rij,kol+1,rij,kol));}}
if(spelBord[rij+1][kol]==1){
if(spelBord[rij+2][kol]==1){
lijst.add(new Zet(rij+2,kol,rij+1,kol,rij,kol));}}
if(spelBord[rij][kol-1]==1){
if(spelBord[rij][kol-2]==1){
lijst.add(new Zet(rij,kol-2,rij,kol-1,rij,kol));}}
return lijst;
}
So first fillBoard() is called and then calculateMoves()
When I change this line:
if(zetten.size()==124 && spelBord[8][8]==2){
into this:
if(zetten.size()>52){
I don't get an outOfMemory exception. Changing this value to 53 does.
Any ideas why I get this exception? (Expanding the heap size didn't work).
Best regards,
RoDeNtJe