Fucking backtracking

soup /prog/, i need halp!
i'm trying to make this fucking backtracking (lol) problem: http://acm.uva.es/p/v8/861.html ; but i dont even know where to start! Any tips on how to analyse this problem?

i need your wisdom /prog/ :D

For a moment I thought this was a gdb topic ;_;