Hi people! Anyone can give me a clue of how can I program the 8 or (n*n) puzzle game using the Incremental Deepening (tree) and/or IDA* algorithms in Java? Unfortunately I''m not finding valueable resources that really teach these algorithms, and those that do, are written in Lisp... which I''m not interested. I''m looking for a tutorial/source type of document. Thanks a lot VisualFX

What I would suggest is to read those Lisp documents and convert the Lisp code into Java. Assuming you are a fairly decent Java programmer, this shouldn''t take you very long. Try googleing this, and see what you come up with.

My Kung Fu is stronger.
neo88

I''ll show you iterative deepening algo in pseudo code. Here''s first simply depth first search, which isn''t even guaranteed to ever return so it sucks big time:

//(emptyX, emptyY) is the location of the empty slot that you can//move around//map is the 3x3 grid for 8-puzzleboolean depthFirst8puzzle(int emptyX, int emptyY, int[][] map) {  if (map is in goal state) {    return true; //return true when we reach goal  }  for d in directions { //up,down,left,right     if (emptyslot can be moved to direction d) {       try {         swap empty slot and the piece where the empty moves         if (depthFirst8puzzle(emptyX + d.x, emptyY + d.y)) {           //we have found solution! so print out the map           print current map           //and return true so the code that called this will           //also know we have found the goal, and print the map.           //the finally block below will make sure that the            //effect of this function call are undoed           return true;         }       } finally {         swap empty slot and the piece where the empty moves (this undoes the effect we did above before recursive call)       }     }  }  return false; //return false when no move could reach goal} 

Ok that''s it. But since it doesn''t check if it''s been in some state earlier, it can easily lead to infinite loop by swapping the pieces back and forth. Well fear not, you don''t even have to add code to test if some map combination has been visited before (although it would make it faster, and plain depth first would also find some solution then). All you need is the iterative deepening algo. The depth first part is essentially the same but it now has a ''depth'' parameter that tells how far to search the tree until returning failure.

//(emptyX, emptyY) is the location of the empty slot that you can//move around//map is the 3x3 grid for 8-puzzle//map is the 3x3 grid for 8-puzzleboolean depthFirst8puzzle(int emptyX, int emptyY, int[][] map, int depth) {  if (depth == 0) {     return 0;  }    if (map is in goal state) {    return true; //return true when we reach goal  }  for d in directions { //up,down,left,right     if (emptyslot can be moved to direction d) {       try {         swap empty slot and the piece where the empty moves         if (depthFirst8puzzle(emptyX + d.x, emptyY + d.y, depth-1)) {           //we have found solution! so print out the map           print current map           //and return true so the code that called this will           //also know we have found the goal, and print the map.           //the finally block below will make sure that the            //effect of this function call are undoed           return true;         }       } finally {         swap empty slot and the piece where the empty moves (this undoes the effect we did above before recursive call)       }     }  }  return false; //return false when no move could reach goal} 

Then we need to set the cut-off value for the depth that the tree is to be searched:

void iterativeDeepening(int[][] map) {  find emptyX and emptyY from the map  int i=1;  while (true) {    if (depthFirst8puzzle(emptyX, emptyY, map, i)) {      return; //leave after finding a solution    }    i++;  }} 

so it first searches the tree to depth 1, then to depth 2 and so on until it finds the solution. Because it adds more steps to the search one-by-one, starting from 1, the solution it finds is guaranteed to be optimal in terms of steps taken.