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 ?
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.