reset password
Author Message
rabbott
Posts: 1649
Posted 15:48 Nov 03, 2012 |

There is a version of the 8-puzzle using A* on the wiki page (and in the Dropbox). Download the new versions of SearchState and EightPuzzleState. 

It finds the same 20-step solution found by BFS but after looking at only 216 states.

Last edited by rabbott at 17:31 Nov 03, 2012.
ummata
Posts: 68
Posted 17:16 Nov 03, 2012 |

I forget what is your strategy for the heuristic function.
Could you explain one more time? Then I will go read your code.

Thanks

rabbott
Posts: 1649
Posted 17:35 Nov 03, 2012 |

It's the sum of the Manhattan distances of all the tiles from their proper locations.  The code is pretty straightforward.

public int h() {
int h = 0;
for (int r = 0; r < 3; r++)
for (int c = 0; c < 3; c++) {
int value = board[r][c];
// Don't bother with the Manhattan distance of the blank square.
// If the other are in their proper places, it will be too. That also
// makes the computation of manhattanDistanceToGoal easier.
if (value > 0) h += manhattanDistanceToGoal(r, c, value);
}
return h;
}
 
 
/**
*   Find the distance from location (r, c) to the correct location for the value in board[r][c] (which is i).
*/
private int manhattanDistanceToGoal(int r, int c, int i) { ... }
 
Last edited by rabbott at 17:40 Nov 03, 2012.
ummata
Posts: 68
Posted 18:44 Nov 03, 2012 |

OK, we have the same strategy but the way you get the Manhattan distance for each sqaure is a lot cleaner.
I have been wondering how someone be able to come up with this sort of clean ways or equations like this right after looking at the problem.
 

rabbott
Posts: 1649
Posted 18:50 Nov 03, 2012 |

The best way to come up with a clean way of doing something is to continue thinking about it and editing it until it's as good as you can make it. I am continually editing and refactoring my code. The first version included the 0 tile, which made the computation a lot messier. Then I realized it wasn't necessary to do that.

ummata
Posts: 68
Posted 19:54 Nov 03, 2012 |

That's true, however this technique is nice to work with a 2-d array and I'll keep in mind.
It reminds me Gauss's series, sometimes we don't need looping to get an index.

ummata
Posts: 68
Posted 21:45 Nov 03, 2012 |

Looking at only 216 states

It is not a number of states in the closed set, where is this number from?

Last edited by ummata at 21:52 Nov 03, 2012.
rabbott
Posts: 1649
Posted 23:13 Nov 03, 2012 |
 
The final state (the state when it reached the goal) is this.
(
 1  2  3 
 4  5  6 
 7  8  _ 
)<#:216(214) d:20 g:20 h:0 f:20>
 
The part that says #: 216 is the id. Every time a new state is generated a new id is generated for it. Since the last state has id 216, that means that only 216 states were generated.  The id is generated in SearchState.checkStateIn
Last edited by rabbott at 23:17 Nov 03, 2012.
ummata
Posts: 68
Posted 23:34 Nov 03, 2012 |

I got it, mine is  #:1660(1659) and I didn't know that is the first version. 
That's why I got a big different number of states.