Today I thought I would take a break from serious science and mathematics, and present for your viewing pleasure a beautiful little puzzle. This puzzle comes from a discussion I had with a student I was tutoring many years ago, and although it seems quite simple as yet no one I have shown it to has been able to solve it (and I must admit, that includes me). I also do not know the origins of this puzzle, as I have never seen it published before and so I do not know whether or not it is already well known or something new and interesting. My former student called it the Greedy Snake, because it is similar to a 1980s video game of that name. Anyway, here it is:

Start with an NxM lattice of points, as displayed below.



The challenge is to draw a single path which passes through each point exactly once. The path must be composed of straight lines that are either horizontal or vertical (no diagonals), and only at a point can the path make a turn to the right or left. This is actually very easy to do, and the answer is trivial.
However the variation that we were discussing adds one more simple condition. Suppose you were to make the path out of some stiff material that cannot bend easily, and so U-turns as shown below are not permitted.


Instead the path must pass straight through one point after each turn before it can turn again, such as this example:

With this additional constraint, is there a path that passes through each and every point exactly once? And which values of N and M have such a solution?

It is a fun little problem to play around with, and I hope you enjoy it.