Can you fill it?
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)
Rules:
- I can start anywhere.
- I can change direction but only at 90° or -90°
- I cannot fill twice the same cell, means there are no crossings allowed.
I call success the stroke that fills all the grid and failure when some cells remain empty.
Examples:
Questions
- Can I successfully start anywhere?
- Can I know how many different strokes lead to success? (two identical stokes by rotations are one only)
-- Anonymous
Answers
Can I successfully start anywhere?
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.
- Fill ea like you fill the first example, first tracing a line along the odd edge. You draw an even number of lines and end up in an unnammed corner of eb.
- Fill eb the same way, first tracing a line towards b. (Actually ea and eb share one line of cells, so you fill only the remaining of eb).
- You end up in a corner of the remaining rectangle (ec plus ed minus a line), fill it the same way.
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.
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:
- Many paths even if you consider only those going from one corner to the opposite one:
@misc{ collins-number,
author = "K. Collins and L. Krompart",
title = "The number of Hamiltonian paths in a rectangular grid",
url = "citeseer.ist.psu.edu/487802.html" }
- Counting is difficult:
@misc{ liskiewicz-complexity,
author = "M. Liskiewicz and M. Ogihara and S. Toda",
title = "The Complexity of Counting Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs",
url = "citeseer.ist.psu.edu/liskiewicz01complexity.html" }
--
JeanBaptisteRouquier - 07 Aug 2007
to top
