Edited by author 28.10.2009 16:46

For every point on the board, we change it into 24 different points in our graph. Every point means a state where the cube move onto it, eg (a,b) means "a" at bottom and "b" at front. Weights are the numbers on the bottom. Use dijkstra at last.

Start dfs from starting node and when you crossed through some node more than 2 then return.