8-puzzle
hi folks,
I've used a brute force implementation for 8-puzzle, it exhaustively search for all possibilities until it finds a match. I have two question:
1.what is the complexity of such method? is it 9!?
2.the code got a stackOverFlow Error at 2351 recursive calls. The following is the code. thanks for the help!!
import java.util.*;
public class PuzzleSolver{
Board initialState;
Board finalState;
static int EMPTY=-1;
public static void print(int[][]board){
for(int i=0;i<board.length;i++){
for(int j=0;j<board.length;j++){
System.out.print(board[j]+" ");
}
System.out.println("");
}
}
public static void main(String[]args){
int[][]a={{0,1,2},{3,4,5},{6,EMPTY,7}};
int[][]f={{0,1,2},{3,4,5},{6,7,EMPTY}};
//int[][]a={{3,0,2},{1,EMPTY,4}};
//int[][]f={{0,1,2},{3,4,5}};
Board ab=new Board(a);
Board fb=new Board(f);
PuzzleSolver p=new PuzzleSolver(ab,fb);
try{
Vector steps=p.solve();
for(int i=1;i<steps.size();i++){
int[]step=(int[])steps.get(i);
int[]prev=(int[])steps.get(i-1);
System.out.println("move from "+prev[0]+","+prev[1]+" to "+step[0]+","+step[1]);
}
}catch(Error ex){
ex.printStackTrace();
System.err.println(p.ct);
}
//print(p.initialState.array);
}
public boolean sameState(Board a, Board b){
for(int i=0;i<a.array.length;i++){
for(int j=0;j<a.array.length;j++){
if(a.array[j]!=b.array[j])return false;
}
}
return true;
}
public PuzzleSolver(Board initialState, Board finalState){
this.initialState=initialState;
this.finalState=finalState;
}
public int[] getPosition(int piece, Board board){
for(int i=0;i<board.array.length;i++){
for(int j=0;j<board.array.length;j++){
if(board.array[j]==piece)return new int[]{i,j};
}
}
return new int[]{-1,-1};
}
public Vector solve(){
int[] initPos=getPosition(EMPTY,initialState);
//int n=-count(initialState,EMPTY);
Vector v=new Vector();
return solveRecur(initPos,initialState,new Vector(),initPos,v);
}
int ct=0;
public Vector solveRecur(int[]pos, Board board, Vector steps,int[]prevPos,Vector cache){
int y=pos[0];
int x=pos[1];
System.out.println(y+" "+x);
System.out.println("--");
print(board.array);
System.out.println("--");
ct++;
System.out.println(ct);
if(sameState(board,finalState)){
System.err.println("sameState");
return steps;
}
if(cache.contains(board)){
//System.err.println("returning");
return new Vector();
}
//System.out.println("move "+board.array[y][x]+" from "+prevPos[0]+","+prevPos[1]+" to "+y+","+x);
cache.add(board);
steps.add(pos);
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
if(i==j||i==-j)continue;
int newY=y+i;
int newX=x+j;
if(newY><0||newX<0||newY>=board.array.length||newX>=board.array[0].length)continue;
if(newY==prevPos[0]&&newX==prevPos[1])continue;
//int old=board[newY][newX];
Board newboard=clone(board);
newboard.array[y][x]=board.array[newY][newX];
newboard.array[newY][newX]=EMPTY;
Vector v=solveRecur(new int[]{newY,newX},newboard,steps,pos,(Vector)cache.clone());
if(v.size()>0)return v;
//board[newY][newX]=old;
//board[y][x]=EMPTY;
}
}
System.err.println("return new vector");
return new Vector();
}
public static Board clone(Board b){
Board c=new Board(clone(b.array));
return c;
}
public static int[][]clone(int[][]board){
int[][]b=new int[board.length][board[0].length];
for(int i=0;i<board.length;i++){
for(int j=0;j<board.length;j++){
b[j]=board[j];
}
}
return b;
}
}
public class Board{
int[][]array;
public Board(int[][]array){
this.array=array;
}
public boolean equals(Object obj){
//System.err.println("eq");
Board b=(Board)obj;
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length;j++){
if(array[j]!=b.array[j])return false;
}
}
return true;
}
}>
[4549 byte] By [
irulet1a] at [2007-9-29 20:30:28]
> 1.what is the complexity of such method? is it 9!?
> 2.the code got a stackOverFlow Error at 2351 recursive calls.
The complexity (big-Oh) is far smaller than that, it's linear to the board size, hence 2351 recusrive calls
are way too many. Of course, when you apply a depth-first search, you might end up with an enormous
amount of board configurations before you find the winning configuration. Just for the fun of it I gave
it a try myself. Basically this method (see below) is a depth-first search too but with a maximum
recursion depth limit. Note that this method doesn't necessarily find the sortest path to the solution.
Here's what I crafted -- import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class test {
// don't go deeper than MAXR recursion steps
private static final int MAXR= 20;
// the start configuration
private static int[] board = { 1, 2, 3, 4, 0, 8, 7, 6, 5 };
// the winning configuation
private static int[] win= { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
// the empty square in the start configuration
private static inte=4;
// have we been at configuration 'board' before?
public static int[] contains(List l, int[] board) {
for (int i= 0; i < l.size(); ++i)
if (Arrays.equals(board, (int[])l.get(i)))
return null;
// if not, add the new board to the list
l.add(board);
return board;
}
// make a move and check if we're repeating ourselves
public static int[] push(int[] board, List l, int i, int j) {
int[] b= new int[board.length];
System.arraycopy(board, 0, b, 0, board.length);
int t= b[i];
b[i] = b[j];
b[j] = t;
return contains(l, b);
}
// print a single board configuration
public static void print(int[] board) {
for (int i= 0; i < board.length; ++i) {
System.out.print((board[i] == 0)?"-":(""+board[i]));
if (i%3 == 2)
System.out.println();
}
System.out.println();
}
// print all board configuration from start to winning
public static void moves(List l) {
for (int i= 0; i < l.size(); ++i)
print((int[])l.get(i));
}
// find a solution given a 'board' configuration
// 'l' contains previous configurations, 'i' is
// the position of the empty square and 'm' is
// the recursion depth.
public static boolean find(int[] board, List l, int i, int m) {
// did we make it?
if (Arrays.equals(board, win)) {
moves(l);
return true;
}
// not allowed to go any deeper?
if (m == MAXR)
return false;
// try all possible moves
for (int d= -3; d <= 3; d+= 2) {
switch (d) {
case -3: if (i+d < 0) continue; break;
case -1: if (i+d < 0) continue;
case 1: if (i/3 != (i+d)/3) continue; break;
case 3: if (i+d >= 9) continue; break;
}
int[] b= push(board, l, i, i+d);
// more moves possible?
if (b != null) {
if (find(b, l, i+d, m+1))
return true;
l.remove(l.size()-1);
}
}
return false;
}
// solve the '8 puzzle
public static void main(String[] args) {
List l= new ArrayList();
find(push(board, l, e, e), l, e, 0);
}
}
kind regards,
Jos
thanks for your help!!
I modified my code and applied the maximum recursion depth. However when i ran my code against a 3x3 puzzle with a recursion depth of 30, it didn't end after examing more than 9! states! which leads me to wonder about the complexity of depth first search on this problem. Is it O(9!) ? If the answer is yes, and I avoided examing repeated states, how could My program still be running after it examed 9! states in search for the right state.?
thank you, here is my code again with formatting added.
import java.util.*;
public class PuzzleSolver{
Board initialState;
Board finalState;
static int EMPTY=-1;
public static void print(int[][]board){
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
System.out.print(board[i][j]+" ");
}
System.out.println("");
}
}
public static void main(String[]args){
//int[][]a={{0,1,2},{3,4,5},{6,EMPTY,7}};
//int[][]f={{0,1,2},{3,4,5},{6,7,EMPTY}};
int[][]a={{2,1,0},{5,3,4},{6,EMPTY,7}};
int[][]f={{0,1,2},{3,4,5},{6,7,EMPTY}};
//int[][]a={{3,0,2},{1,EMPTY,4}};
//int[][]f={{0,1,2},{3,4,5}};
Board ab=new Board(a);
Board fb=new Board(f);
PuzzleSolver p=new PuzzleSolver(ab,fb);
try{
Vector steps=p.solve(30);
for(int i=1;i<steps.size();i++){
int[]step=(int[])steps.get(i);
int[]prev=(int[])steps.get(i-1);
System.out.println("move from "+prev[0]+","+prev[1]+" to "+step[0]+","+step[1]);
}
}catch(Error ex){
ex.printStackTrace();
System.err.println(p.ct);
}
//print(p.initialState.array);
}
public boolean sameState(Board a, Board b){
for(int i=0;i<a.array.length;i++){
for(int j=0;j<a.array[i].length;j++){
if(a.array[i][j]!=b.array[i][j])return false;
}
}
return true;
}
public PuzzleSolver(Board initialState, Board finalState){
this.initialState=initialState;
this.finalState=finalState;
}
public int[] getPosition(int piece, Board board){
for(int i=0;i<board.array.length;i++){
for(int j=0;j<board.array[i].length;j++){
if(board.array[i][j]==piece)return new int[]{i,j};
}
}
return new int[]{-1,-1};
}
public Vector solve(int depth){
int[] initPos=getPosition(EMPTY,initialState);
//int n=-count(initialState,EMPTY);
Vector v=new Vector();
return solveRecur(initPos,initialState,new Vector(),initPos,v,0, depth);
}
int ct=0;
public Vector solveRecur(int[]pos, Board board, Vector steps,int[]prevPos,Vector cache, int curDepth, int maxDepth){
int y=pos[0];
int x=pos[1];
System.out.println(y+" "+x);
System.out.println("--");
print(board.array);
System.out.println("--");
ct++;
System.out.println(ct);
if(sameState(board,finalState)){
System.err.println("sameState");
return steps;
}
if(curDepth==maxDepth){
System.out.println("depth reached");
return new Vector();
}
if(cache.contains(board)){
//System.err.println("returning");
return new Vector();
}
//System.out.println("move "+board.array[y][x]+" from "+prevPos[0]+","+prevPos[1]+" to "+y+","+x);
cache.add(board);
steps.add(pos);
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
if(i==j||i==-j)continue;
int newY=y+i;
int newX=x+j;
if(newY><0||newX<0||newY>=board.array.length||newX>=board.array[0].length)continue;
if(newY==prevPos[0]&&newX==prevPos[1])continue;
//int old=board[newY][newX];
Board newboard=clone(board);
newboard.array[y][x]=board.array[newY][newX];
newboard.array[newY][newX]=EMPTY;
Vector v=solveRecur(new int[]{newY,newX},newboard,steps,pos,(Vector)cache.clone(),curDepth+1,maxDepth);
if(v.size()>0)return v;
//board[newY][newX]=old;
//board[y][x]=EMPTY;
}
}
//System.err.println("return new vector");
return new Vector();
}
public static Board clone(Board b){
Board c=new Board(clone(b.array));
return c;
}
public static int[][]clone(int[][]board){
int[][]b=new int[board.length][board[0].length];
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
b[i][j]=board[i][j];
}
}
return b;
}
}
public class Board{
int[][]array;
public Board(int[][]array){
this.array=array;
}
public boolean equals(Object obj){
//System.err.println("eq");
Board b=(Board)obj;
for(int i=0;i<array.length;i++){
for(int j=0;j<array[i].length;j++){
if(array[i][j]!=b.array[i][j])return false;
}
}
return true;
}
}
>
> > int[][]a={{2,1,0},{5,3,4},{6,EMPTY,7}};
> int[][]f={{0,1,2},{3,4,5},{6,7,EMPTY}};
I my, I should have noticed that earlier -- the configuration you're trying to solve happens to be
unsolvable. Try this one instead --
int[][]a={{2,1,0},{5,3,4},{7,EMPTY,6}};
kind regards,
Jos
Allow me to elaborate a bit more on my previous reply -- A 3x3 board configuration is solvable if and
only if, after moving the empty square to the bottom right position, the board can be oredered in
an *even* number of swaps. BTW, for an even sized square, the number of swaps need to be *odd*.
There are 9! different board configurations, half of them need even number of swaps, so the number
of solvable configurations equals 9!/2 = 181440. If one of the four corner positions is empty there are
two possible moves, if it's on one of the four sides there are three possible moves and when it's in
the center, there are four possible moves.
So for any board configuration there are (a bit sloppy math) (4*2 +4*3 +1*4/9) = 24/9 possible moves
on average. Thus any search tree has (on average) 24/9 possible children, so (more sloppy math)
solving (24/9)^n = 181440 for 'n' gives you the maximum number of moves 'n' to solve the 8 puzzle.
(n ~ 12.345, that 'swhy I (cowardly) set my upperbound on the recursion depth = 20).
kind regards,
Jos
> So for any board configuration there are (a bit sloppy
> math) (4*2 +4*3 +1*4/9) = 24/9 possible moves
> on average. Thus any search tree has (on average) 24/9
> possible children, so (more sloppy math)
> solving (24/9)^n = 181440 for 'n' gives you the
> maximum number of moves 'n' to solve the 8 puzzle.
> (n ~ 12.345, that 'swhy I (cowardly) set my upperbound
> on the recursion depth = 20).
>
thanks for the help. However with a max recursion depth set to 20, my code finishes without finding a solution. It couldn't find a solution even with a max recursion depth of 30, it did with a depth of 100.
can yours find a solution with a max recursion depth set to 20? Here is my code again, there was a bug earlier. If your analysis of the complexity is correct, what's wrong with my code?
import java.util.*;
public class PuzzleSolver{
Board initialState;
Board finalState;
static int EMPTY=-1;
public static void print(int[][]board){
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
System.out.print(board[i][j]+" ");
}
System.out.println("");
}
}
public static void main(String[]args){
int[][]a={{2,1,0},{5,3,4},{7,EMPTY,6}};
int[][]f={{0,1,2},{3,4,5},{6,7,EMPTY}};
Board ab=new Board(a);
Board fb=new Board(f);
PuzzleSolver p=new PuzzleSolver(ab,fb);
try{
Vector steps=p.solve(30);
for(int i=1;i<steps.size();i++){
int[]step=(int[])steps.get(i);
int[]prev=(int[])steps.get(i-1);
System.out.println("move from "+prev[0]+","+prev[1]+" to "+step[0]+","+step[1]);
}
}catch(Error ex){
ex.printStackTrace();
System.err.println(p.ct);
}
//print(p.initialState.array);
}
public boolean sameState(Board a, Board b){
for(int i=0;i<a.array.length;i++){
for(int j=0;j<a.array[i].length;j++){
if(a.array[i][j]!=b.array[i][j])return false;
}
}
return true;
}
public PuzzleSolver(Board initialState, Board finalState){
this.initialState=initialState;
this.finalState=finalState;
}
public int[] getPosition(int piece, Board board){
for(int i=0;i<board.array.length;i++){
for(int j=0;j<board.array[i].length;j++){
if(board.array[i][j]==piece)return new int[]{i,j};
}
}
return new int[]{-1,-1};
}
public Vector solve(int depth){
int[] initPos=getPosition(EMPTY,initialState);
//int n=-count(initialState,EMPTY);
Vector v=new Vector();
return solveRecur(initPos,initialState,new Vector(),initPos,v,0, depth);
}
int ct=0;
public Vector solveRecur(int[]pos, Board board, Vector steps,int[]prevPos,Vector cache, int curDepth, int maxDepth){
int y=pos[0];
int x=pos[1];
/*
System.out.println(y+" "+x);
System.out.println("--");
print(board.array);
System.out.println("--");
ct++;
System.out.println(ct);*/
if(sameState(board,finalState)){
System.err.println("sameState");
return steps;
}
if(curDepth==maxDepth){
//System.out.println("depth reached");
return new Vector();
}
if(cache.contains(board)){
//System.err.println("returning");
return new Vector();
}
//System.out.println("move "+board.array[y][x]+" from "+prevPos[0]+","+prevPos[1]+" to "+y+","+x);
cache.add(board);
steps.add(pos);
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
if(i==j||i==-j)continue;
int newY=y+i;
int newX=x+j;
if(newY><0||newX<0||newY>=board.array.length||newX>=board.array[0].length)continue;
if(newY==prevPos[0]&&newX==prevPos[1])continue;
//int old=board[newY][newX];
Board newboard=clone(board);
newboard.array[y][x]=board.array[newY][newX];
newboard.array[newY][newX]=EMPTY;
Vector v=solveRecur(new int[]{newY,newX},newboard,steps,pos,cache,curDepth+1,maxDepth);
if(v.size()>0)return v;
//board[newY][newX]=old;
//board[y][x]=EMPTY;
}
}
//System.err.println("return new vector");
return new Vector();
}
public static Board clone(Board b){
Board c=new Board(clone(b.array));
return c;
}
public static int[][]clone(int[][]board){
int[][]b=new int[board.length][board[0].length];
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length;j++){
b[i][j]=board[i][j];
}
}
return b;
}
}
thanks for the guidance!!!
>
> thanks for the help. However with a max recursion
> depth set to 20, my code finishes without finding a
> solution. It couldn't find a solution even with a max
> recursion depth of 30, it did with a depth of 100.
> can yours find a solution with a max recursion depth
> set to 20? Here is my code again, there was a bug
> earlier. If your analysis of the complexity is
> correct, what's wrong with my code?
I haven't looked at your code yet (bizzy, bizzy, bizzy), but your initial board configuration is solved using
25 moves using my code ... This shows two things --
1) there's something wrong with your code;
2) my cowardesque estimation of 20 was the result of my very sloppy math.
No matter 2) (I simply ignored the fact that every other level in the tree, reduces the fan-out by one,
because no previous board configurations are allowed), 100 levels of recursion are simply not
correct because at least one board configuration must occur more than once then ...
I'll check it out later, ok?
kind regards,
Jos
thanks for your kindness! I'll be waiting for your pointers..
> cache.add(board);
> steps.add(pos);// <-- here you add board configurations
> for(int i=-1;i<=1;i++){
> for(int j=-1;j<=1;j++){
// skipped the loop body
You're adding every possible configuration, (i.e. it wasn't in the cache before) to the cache, but you
never delete them after the loop body has finished and, consequently has figured out that this
current configuration is not on a path to the solution. Hence a lot of spurious configurations are
stacked in that 'cache' possibly preventing a path to the solution (elsewhere) to be completed.
I haven't studied your code any further yet, but this definitely is a little nono ... ;-)
kind regards,
Jos
