The grid in question is undirected.
The length of the Hamiltonian cycle should be even which should be possible in this grid since any N × M grid is bipartite. Besides this, I am not able to grasp any other insights which might help me to prove this.
What would be a good strategy to prove this?