[Magictour] Non crossing knight tours

> > Direct access is: http://www.ktn.freeuk.com/2b.htm.
> >
I found another formula to approximate the number of jumps.

Let's count the number of all possible moves for every size.
We get the following table:

size number of possible moves
3*3 8
4*4 24
5*5 48
6*6 80
7*7 120
8*8 168
9*9 224
10*10 288
11*11 360
12*12 440
etc...
A quick look at the encyclopedia of integer sequences show that the formula
is:
4*n^2+4*n
http://www.research.att.com/projects/OEIS?Anum=A033996

Now, let's compute the ratio: number_of_jumps/longest_known_tour
we get:
3*3 4.0
4*4 4.8
5*5 4.8
6*6 4.70
7*7 4.8
8*8 4.8
9*9 4.76
10*10 4.72
11*11 4.73
12*12 4.68
13*13 4.67
14*14 4.65
15*15 4.60
16*16 4.63
17*17 4.57
18*18 4.59

Squares with prime sizes seem to give a better ratio than others.
Also, the 16*16 square seems to have a longest tour roughly equal to
840/4.59=183 !

Following this discovery, I found an heuristic for non-crossing knight tours
!
I simply test if the remaining number of possible jumps divided by 4 PLUS
the current jump is bigger than the current record.

This heuristic is very simple, but gave me the following results:
8*8 length=35 found in 2 seconds
9*9, length=47 found in 285 seconds
For the 9*9 case, I found the 4 following tours:
e4 c3 d5 b4 c6 a5 b7 a9 c8 b6 d7 c5 e6 d4 f5 e3 g4 f2 d3 b2 c4 a3 b1 d2 f1
g3 h5 f4 g6 e5 f7 d6 e8 c7 d9 f8 h9 i7 g8 f6 h7 g5 i6 h4 g2 i1 h3 i5 in
255516 ticks
e3 c2 d4 b3 c5 d7 b6 c8 a9 b7 a5 c6 b4 a2 c3 b1 d2 f1 g3 e2 f4 d3 e5 c4 d6
e8 c7 d9 f8 h9 i7 g8 e7 d5 f6 e4 g5 f3 h4 g2 i1 h3 i5 g4 h6 f5 g7 e6 in
260407 ticks
e3 c2 d4 b3 c5 d7 b6 c8 a9 b7 a5 c6 b4 a2 c3 b1 d2 f1 g3 e2 f4 d3 e5 c4 d6
e8 c7 d9 f8 h9 i7 g8 e7 d5 f6 e4 g5 f3 h4 g2 i1 h3 i5 g4 h6 f5 g7 i6 in
260407 ticks
e3 g2 f4 h3 g5 f7 h6 g8 i9 h7 i5 g6 h4 i2 g3 h1 f2 d1 c3 e2 d4 f3 e5 g4 f6
e8 g7 f9 d8 b9 a7 c8 e7 f5 d6 e4 c5 d3 b4 c2 a1 b3 a5 c4 b6 d5 c7 a6 in
260672 ticks
e3 g2 f4 h3 g5 f7 h6 g8 i9 h7 i5 g6 h4 i2 g3 h1 f2 d1 c3 e2 d4 f3 e5 g4 f6
e8 g7 f9 d8 b9 a7 c8 e7 f5 d6 e4 c5 d3 b4 c2 a1 b3 a5 c4 b6 d5 c7 e6 in
260672 ticks

One tick=1/1000th of second

Using a divisor of 5, instead of 4, gave me:
9x9, 44 moves in 1/2 second
10x10, 57 moves in 7 seconds
11x11, 73 moves in 17 seconds
12x12, 89 moves in 395 seconds

JC

Magictour mailing list
To unsubscribe: mailto:magictour-request@ml.free.fr?subject=unsubscribe
To mail to the mailing list: mailto:magictour@ml.free.fr



Received on Thu Dec 04 14:24:18 2001