wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Knight Moves
        
(Message started by: mattian on Nov 1^st, 2004, 10:51am)

Title: Knight Moves
Post by mattian on Nov 1^st, 2004, 10:51am

Given an n by n grid, start by placing a "1" in a cell. From that position move anywhere within the grid as a chess knight would (ie. two cells in one direction and one cell in the other). Number the second position "2", and so on. Without visiting the same cell twice, attempt to visit all the cells in the grid.

For example, in a 3x3 grid, starting at (1,1) will allow a maximum number of visited cells of 8, while starting in (2,2) the maximum number of visited cells is 1.

+	---	+	---	+	---	+
\|	1	\|	6	\|	3	\|
+	---	+	---	+	---	+
\|	4	\|		\|	8	\|
+	---	+	---	+	---	+
\|	7	\|	2	\|	5	\|
+	---	+	---	+	---	+

What are the maximum number of cells that may be visited in this way for the following grids?:
4x4, 5x5, 6x6, 7x7, 8x8, 9x9, 10x10, nxn

Title: Re: Knight Moves
Post by Grimbal on Nov 2^nd, 2004, 3:33am

4x4 I can do [hide]15[/hide]. For 8x8, I know it is [hide]64[/hide]. For 2nx2n, n>2, I believe it is [hide](2n)²[/hide]. The interesting is in the odd numbers.

Title: Re: Knight Moves
Post by towr on Nov 2^nd, 2004, 4:22am

There must be good ways to make a graph from it and find the longest path going through each node at most once..
Of course the integer sequence database probably already has the answer in it somewhere, or google if that fails :P

Title: Re: Knight Moves
Post by asterix on Nov 2^nd, 2004, 7:18am

I think I found a solution for both n=5 and n=7, and I would imagine it only gets easier as the board gets bigger, since the number of path permutations grows rapidly.

Title: Re: Knight Moves
Post by mattian on Nov 2^nd, 2004, 7:23am

I concur with these results and am trying to solve n=9. No solution yet.

Title: Re: Knight Moves
Post by Barukh on Nov 2^nd, 2004, 7:39am

on 11/02/04 at 07:23:12, mattian wrote:

I concur with these results and am trying to solve n=9. No solution yet.

One of the first approaches to solving this problem (going back at least to de Moivre) is to divide the nxn board into a smaller (n-4)x(n-4) board in the center and a remaining frame of width 2. Once the solution for the smaller board is at hand, it's not difficult to complete the frame first, and then jump to the square of the smaller board.

In your case, you have the 5x5 solution; so, 9x9 should be easy.

Title: Re: Knight Moves
Post by rmsgrey on Nov 2^nd, 2004, 7:59am

Sounds like solutions for n[ne]4. The only question is whether you can get all 16 on the 4*4?

Title: Re: Knight Moves
Post by mattian on Nov 2^nd, 2004, 8:52am

Absolutely can not get 16 on 4x4.

In order to ensure a solution of n², at least three of the four corners must have an entry point and an exit point. In the case of n=5, these entry and exit points are discrete for each corner w.r.t. all the other corners. In the case of n=4, these cells are shared between diagnonally opposite corners, so three of the four corners can be visited, but the third will be the final cell visited because there is no exit route.

Now if we introduce the concept of wrapping so that moving from (2,4) to (4,1) is valid, I believe the solution to n=4 may be 16. But don't quote me on that... Actually - do quote me on that; it's trivial.

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

Title: Re: Knight Moves
Post by rmsgrey on Nov 2^nd, 2004, 9:50am

on 11/02/04 at 08:52:44, mattian wrote:

In order to ensure a solution of n², at least three of the four corners must have an entry point and an exit point. In the case of n=5, these entry and exit points are discrete for each corner w.r.t. all the other corners. In the case of n=4, these cells are shared between diagnonally opposite corners, so three of the four corners can be visited, but the third will be the final cell visited because there is no exit route.

I can get routes that visit all four corners on a 4*4 (with 10 or 12 moves total) by starting in one corner and ending in another. It's not clear to me that an n² solution in the general case requires more than 2 corners to have both entry and exit points.

On the other hand, I have managed to prove that you can't get a 16 square solution on the 4*4 - since the corners are so crowded, a 16 square path must start (and end) in a corner, effectively forcing the first (and the last) 4 moves (down to symmetry). Without loss of generality, and labelling the cells with hexadecimal digits 0-F in the obvious way, the path must start 06F9 and end either 53AC or A35C. Therefore the midsection of th path must visit all 8 side cells without visiting any of the four center cells. Unfortunately, the side cells form two distinct orbits - 17E8 and 24DB, which can ony be moved between by going via one of the center cells: 5, 6, 9, and A.

Title: Re: Knight Moves
Post by Grimbal on Nov 2^nd, 2004, 9:50am

??? 7-8 looks wrong to me.

PS: oh, I see. I didn't see the part about wrapping.

Title: Re: Knight Moves
Post by rmsgrey on Nov 2^nd, 2004, 9:56am

on 11/02/04 at 09:50:45, Grimbal wrote:

??? 7-8 looks wrong to me.

Right 2 and down 1...

Title: Re: Knight Moves
Post by mattian on Nov 2^nd, 2004, 9:57am

Try this one (it only uses the wrapping once)

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

Title: Re: Knight Moves
Post by Grimbal on Nov 2^nd, 2004, 10:20am

And I am convinced that 15 is the best you can do with 4x4.

A B C D
E F G H
I J K L
M N O P

If all the cells are used, considering 2 opposite corners A and P, one of them must be and end of the path, else you get a loop AGPJA. Same for M and D, so the ends must be in corners, and not opposite corners.

If A is an end, A connects to G or J, but P connects to G and J. So, the path must start with AGPJ or AJPG (or end the other way round).
At both ends, the path starts in a corner and in 3 steps reaches one of the center squares (FGJK). The 2 center squares connected to the ends are always adjacent, and on the way, the paths go through the other 2 center squares. By symetry we can assume the ends connect to F and G.

The following remains:
# B C #
E F G H
I # # L
# N O #

A path starts in a corner, goes to F, you need to make it go to G where it goes to the other end. Cells marked # are used up by the start and end paths.

Now you can see that B can only connect to I and H, and H only to B and O. You must have IBHO (or OHBI) in your path. Then, from I, you cannot connect to O, it would close a loop, so you have to connect I to G. Similarily, you must connect O to F.
But now, you have a path from the start to the end, while 4 cells, NECL, are unused.

So, it is impossible to cover all cells with a single path.

Title: Re: Knight Moves
Post by mattian on Nov 2^nd, 2004, 10:38am

Exactly.

Title: Re: Knight Moves
Post by mattian on Nov 2^nd, 2004, 11:38am

I still don't have a solution for n=9 - I can do 80, but not 81. I have a solution for n=10 based on the solution for n=5, but n=9 is still problematic.

Title: Re: Knight Moves
Post by towr on Nov 2^nd, 2004, 2:10pm

As long as n>4 you can get all squares
http://mathworld.wolfram.com/KnightsTour.html

interesting related problems:
"The Prime Queen Attacking Problem" (http://users.aol.com/s6sj7gt/primeq.htm)
longest "uncrossed" knight's tours (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003192)

Title: Re: Knight Moves
Post by mattian on Nov 2^nd, 2004, 2:21pm

I have 81 for n=9 - YAY!

Title: Re: Knight Moves
Post by Barukh on Nov 3^rd, 2004, 12:00am

on 11/02/04 at 14:21:40, mattian wrote:

I have 81 for n=9 - YAY!

Please find enclosed the solution for 9x9 board that uses the algorithm described in my previous post. Note how the external frame is filled by moves 1-56, and then the inner frame is filled by moves 57-80, leaving just one final square. Using this technique, it was almost straightforward to find the solution.