Traveling Through a Square

Date: 11/25/2001 at 20:23:04
From: stephen
Subject: Traveling through a square

How do I get from the bottom left-hand corner of a 64-block square to 
the top right-hand corner, only going through each square once?

Date: 11/26/2001 at 11:36:51
From: Doctor Ian
Subject: Re: Traveling through a square

Hi Stephen,

This is a pretty interesting question! Let's try looking at some small 
squares, to see if we can find some kind of pattern that we can apply 
to squares of any size.  

I'm assuming that you can cut across a corner. For example, I think 
this would be a legal way to move from the LL corner to the UR corner 
of a 2x2 square:

  +-+-+
  |2|4|
  +-+-+
  |1|3|
  +-+-+

For convenience, I'm not going to draw the borders of the squares from 
now on, so the figure above would look like 

  2 4
  1 3

Now, for any NxN square, where N is odd, the answer is pretty easy - 
just go up and down the columns until you reach the end:

  
  3 4 9
  2 5 8     3x3
  1 6 7


  5  6 15 16 15
  4  7 14 17 24
  3  8 13 18 23   5x5
  2  9 12 19 22
  1 10 11 20 21

Unfortunately, in our case, N = 8, which is even. So the next thing we 
might try is this: Can we find a way to transform the problem into a 
different problem, where the solution is obvious?  

For example, suppose we have a 6x6 square: 

  *  *  *  *  *  *
  *  *  *  *  *  *
  *  *  *  *  *  *
  *  *  *  *  *  *
  *  *  *  *  *  *
  *  *  *  *  *  *

We could 'cut off' the first three columns this way:

  6  7  8  *  *  *
  5  9 10  *  *  *
  4 11 12  *  *  *
  3 13 14  *  *  *
  2 15 16  *  *  *
  1 17 18 19  *  *

Now, what's left isn't a square... but we can still zip up and down 
the columns to get to the UR corner.  

Can you generalize this so that it works for an 8x8 square, or any 
other (even)x(even) square? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/