Author |
Topic: Knight Moves (Read 2029 times) |
|
mattian
Senior Riddler
 
Gender: 
Posts: 404
|
 |
Knight Moves
« on: Nov 1st, 2004, 10:51am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Knight Moves
« Reply #1 on: Nov 2nd, 2004, 3:33am » |
Quote Modify
|
4x4 I can do 15. For 8x8, I know it is 64. For 2nx2n, n>2, I believe it is (2n)2. The interesting is in the odd numbers.
|
| « Last Edit: Nov 2nd, 2004, 3:34am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Knight Moves
« Reply #2 on: Nov 2nd, 2004, 4:22am » |
Quote Modify
|
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 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
asterix
Guest
|
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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: Knight Moves
« Reply #4 on: Nov 2nd, 2004, 7:23am » |
Quote Modify
|
I concur with these results and am trying to solve n=9. No solution yet.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Knight Moves
« Reply #5 on: Nov 2nd, 2004, 7:39am » |
Quote Modify
|
on Nov 2nd, 2004, 7:23am, 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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Knight Moves
« Reply #6 on: Nov 2nd, 2004, 7:59am » |
Quote Modify
|
Sounds like solutions for n[ne]4. The only question is whether you can get all 16 on the 4*4?
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: Knight Moves
« Reply #7 on: Nov 2nd, 2004, 8:52am » |
Quote Modify
|
Absolutely can not get 16 on 4x4.
In order to ensure a solution of n2, 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
|
| « Last Edit: Nov 2nd, 2004, 8:55am by mattian » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Knight Moves
« Reply #8 on: Nov 2nd, 2004, 9:50am » |
Quote Modify
|
on Nov 2nd, 2004, 8:52am, mattian wrote:| In order to ensure a solution of n2, 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 n2 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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Knight Moves
« Reply #9 on: Nov 2nd, 2004, 9:50am » |
Quote Modify
|
 7-8 looks wrong to me.
PS: oh, I see. I didn't see the part about wrapping.
|
| « Last Edit: Nov 3rd, 2004, 6:25am by Grimbal » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Knight Moves
« Reply #10 on: Nov 2nd, 2004, 9:56am » |
Quote Modify
|
on Nov 2nd, 2004, 9:50am, Grimbal wrote:| 7-8 looks wrong to me. |
|
Right 2 and down 1...
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: Knight Moves
« Reply #11 on: Nov 2nd, 2004, 9:57am » |
Quote Modify
|
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
|
| « Last Edit: Nov 2nd, 2004, 9:59am by mattian » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Knight Moves
« Reply #12 on: Nov 2nd, 2004, 10:20am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 2nd, 2004, 10:29am by Grimbal » |
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: Knight Moves
« Reply #13 on: Nov 2nd, 2004, 10:38am » |
Quote Modify
|
Exactly.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: Knight Moves
« Reply #14 on: Nov 2nd, 2004, 11:38am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: Knight Moves
« Reply #16 on: Nov 2nd, 2004, 2:21pm » |
Quote Modify
|
I have 81 for n=9 - YAY!
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
on Nov 2nd, 2004, 2:21pm, mattian wrote:
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove