Algorithm for a dice problem

Question

I was thinking what should be the best algorithm for finding all the solutions of this puzzle.

http://1cup1coffee.com/puzzle/endice/

Could backtracking be the an approach for solving this or can you suggest any other approach?

Thanks

Answer 1

Backtracking is definitely the way to go if you want ALL the solutions. BFS / A* / Dijkstra and the rest might work (one would need to prove it), but either way they most likely won't give you all the solutions.

Backtracking shouldn't take too long here, since the playable area is really small and you have a relatively small number of pieces and moves, which allows for good heuristics.

Answer 2

In order to avoid searching every reachable position, you will need a way of quickly determining if a position is unsolvable. You won't be able to quickly rule out all unsolvable positions, but you can rule out many of them.

One thing to check is for each die D, and for each hole H, whether it is possible for die D to reach hole H. Even this is not easy to figure out exactly. As a conservative bound, you can add up the numbers left on all the dice, assume that D has that much movement left (because each of those movements could theoretically push D), and see if D can reach H. As a slightly less conservative bound, you could instead assign all the excess movement to whichever die E is closest to being able to push D, and then see if D (with E's help) can reach H.

Once you've determined which dice might still be able to reach which holes, if there is a die that can't reach any hole, or a hole that can't be reached by any die, then the position is unsolvable. Similarly, if there are N dice that can't reach N distinct holes, or H holes that can't be reached by N distinct dice, then the position is unsolvable.

This heuristic won't completely solve your problem, but it may make the search space more manageable for certain ranges of boards.