Can You Fill It
On this page... (hide)
I have some questions for you mathematicians, I guess I won't formalize correctly but here it goes:
Be a square grid of n-cell side. I want to fill all the cells. I want to do this by tracing a single stroke.
(For no reason I started to work on a 9x9 grid)
I call success the stroke that fills all the grid and failure when some cells remain empty.
Yes if n is even. Let a, b, c, d be the corners of the square, e the chosen starting point. Consider the four following rectangles, denoted by opposite corners: ea, eb, ec, ed. Because n is even, we can assume withohut loss of generality that eb has edges of even length, ed has edges of odd length, while ea and ec have one even edge and one odd edge.
No if n is odd: paint the square as a checkerboard, with the four corners black. If you start on a white cell, the number of white cells you fill will be greater or equal to the number of black cells you fill. But there is one more black cell in the square. Yes if you start on a black cell: first fill a line towards the edge of the square, then fill it in the same manner as when n is even, ie one quadrant after another.
4.2 Can I know how many different strokes lead to success? (two identical stokes by rotations are one only)
Too many to be of any practical use ;-) Actually the problem has been well studied, ask for instance http://scholar.google.com about "hamiltonian paths grid".
After a very quick and partial bibliographic search: