I am trying to write IDA* for Sokoban puzzle problem (http://en.wikipedia.org/wiki/Sokoban) but It seems that my heuristic is not so good for making the algorithm fast.
My heuristic is to consider $h(s)$ as minimum distance between the Player and Boxes plus minimum distance between a Box and a Target in state $s$.
Can you please provide some better heuristics for this problem?
Edit: consider the number of Boxes(and Targets) is at most 3!
Hi there CoderInNetwork,
That ain't an easy question and any advances regarding a good heuristic function would be very welcome. Indeed, I will refer in my answer to Andreas Junghanns' PhD written in 1999 (yeap, 16 years ago and still the current state of the art in the field). You can find it in citeseer:
Go to Section 4 and you will see a discussion about a heuristic function. The easiest one comes from a simple observation: every stone has to go to one and only one target location so you have to solve a minimum cost perfect matching in a bipartite graph where one set of vertices is made of the stones and the other one is made of the target locations ---so that there are obviously edges going only from the first set to the second and the goal is to find the minimum assignment of stones to goals. The cost of every edge would be equal to the estimated distance to get to the goal assigned from every stone.
This can be done in $O(n^3\log_{2+\frac{n}{4}}n)$ using minimum cost augmentation ---again refer to Andreass Junghanns' PhD, Section 4.3.3 in page 52.
Even considering that this heuristic can be computed in an acceptable time (after making a good number of code optimizations) note that it does not account for dead locks. This is, it will naively move the stones without considering that either the walls or other stones can lead to unsolvable configurations.
From this observation, Andreas Junghanns introduced the idea of using Pattern Databases (PDBs) for improving this lower bound (see a discussion of their implementation in Chapter 5). At the time of writing his PhD, PDBs were not very well known but they are quite well known nowadays and a lot of progress has been made.
Finally, regarding your question: even if there are only 3 stones, problems can be really difficult to solve (or, at least, to solve optimally if that's what you are aiming for). See Appendix B, page 158, The 61 Kids Problems and you'll see lots of challenging problems. Many of those contain only 3 stones.
Hope this helps,
