Kata

In this kata your task is to create a hamiltonian cycle on a grid: a closed path which visits every single square in the grid exactly once.

Finding hamiltonian cycles is in general a NP-complete problem; however, in the case of a grid, the problem is not, and you can find a much simpler solution! Interestingly, the game Snake can be solved through a hamiltonian cycle or, when it doesn't exist, a slightly modified version of it; but you are required to find out by yourself when the modification is needed, so I can't say more on the topic ;).

Task

Given the size of the grid as two arguments a and b:

• If no hamiltonian cycle exists, return None
• Otherwise, return a list of tuples representing the path: for a grid a * b the solution consists of tuples (x,y) such that 0 <= x < a and 0 <= y < b. Note that you can only move horizontally or vertically to adjacent squares.
• Any valid hamiltonian cycle can be used to solve the kata.
• The start/end point must be present at both ends of the output.
• The case 1 x 1 is not considered a hamiltonian cycle here, so return None.

Examples

• A possible solution for a 2 x 2 grid is:

  [(0,0),(0,1),(1,1),(1,0),(0,0)]
  

• The image below shows a possible hamiltonian path for a 6 x 6 grid: