Tanzir5's blog

By Tanzir5, history, 8 years ago, In English

This is a problem that appeared in Hong Kong regional 2016. Only one team could solve it. In this problem, you have to find a valid closed tour in a n*m board ( 1< = n,m <= 200) where two consecutive cells in your path must have a Manhattan distance of 2 or 3 and every cell is visited exactly once. Or you should output that no valid tour is possible.

This seemed to me like a variation of a knight's tour problem on an arbitrary sized chessboard where you're allowed to move like a chess knight. I've read up a bit on Warnsdorf's rule . I was not sure if it would help here. Nonetheless I implemented the rule in this code to check its efficiency for this problem. As expected, it doesn't even work for boards like 7*7.

So does anyone have any idea how this problem can be solved ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Warnsdorf's rule is actually better suited to find a hamiltonian path, not a closed tour. Since the graph in this problem is special, I think there is a greedy strategy to find a closed tour here. I haven't solved it myself, but I don't think backtracking is the way to go here.