Este programa es tipico de ejemplo para quien se introduce en competiciones de programacion.
Recuerda siempre que el nombre lo dice, back-tracking es recorrer al reves...
Y al recorrerlo, si un paso ha costado mas que el anterior, no lo hagas.
Aqui tienes información sobre algoritmica
http://hispabyte.net/foro/index.php?board=92.0