n次元におけるチェスのナイトによるハミルトン路問題
Problem of the Hamilton Path with Knight in Chess in n-Dimensions

玉川学園高等部 ３年 栗山和大
Tamagawa Academy 12th Kazuhiro Kuriyama

Definition
A Path going along
all points of thegraph once is called
Hamiltonian Path.

The movement of the Knightof the chess is defined tomove two blocks to four
directions perpendicularlyand horizontally, and tomove one block moves
perpendicularly from there.

Precedent Research

As the end square was different from the starting square, the research we performed was called theHamiltonian Open Path, but the research of the Hamiltonian Closed Path,which the end point and the starting
point is the same, was performed in the name called "Closed Knight 's Tour” in UK. I did not notice until recently.
Knight’s Tours in Higher Dimensions,Joshua Erde,
Electronic Journal of Combinatorics: arXiv:1202.5548v1 [math.CO] 24 Feb 2012

Findings of the Hamiltonian Path by the movement of the Knight in two dimensions
Initial level : Trial and error

I inspected whether squares of n x n
had Hamiltonian Path by constituting
them concretely. (left-hand figures.)
As a result, I confirmed that theHamiltonian Path existed in thesquare with block from 5x5 to 20x20.
In addition, I showed that there wasnot Hamiltonian Path in squares of
2x2,3x3nor 4x4.

Generalization : Idea for the proof
I showed that the Hamiltonian Path which startsin (1,1) , and finished in (n,3) exists in the squareof 5×n(n=5k,5k+1,5k+2,5k+3,5k+4) byconnecting rectangle shown in the right diagram.
Using this result , I showed that the Hamiltonian
Path which starts in (1,1) , and finishes in (n-2,1)
exists in the square of n×n.
I guessed n×n is made of (n-5)×(n-5),5×(n-5),(n-5)×5 and 5×5. Then I put it out for case about
remainders when I divided 5 into n and proved it.

Conclusion 137

In the case of n x n, If n >= 5,there is
the Hamiltonian Path that (1,1) is thestarting point, and (n-2, 1) becomes theend point.

Findings of the Hamiltonian Path by the Movement of the Knight in the High Dimension
Definition

yMovement of the Knight in the n dimensions
I choose an axis to move one block and another axis to move two block from n-axes.
Then I decide which direction to move , plus and minus.

2 2z
21x

Result of trial and error in 3 and 4 dimensional cases and Conjecture in the n dimension
3dim 4×4×4…4(3)yz yx

4dim 4×4×4×4…4(4)zx

In the two dimensions, as for 4×4, Hamiltonian Path
was found not to exist, but, as for 4×4×4 of three
dimensions and 4×4×4×4 of the four dimensions,
Hamiltonian Path was found to exist.

From this, I conjectured that the condition
Hamiltonian Path exists in n×n×・・・×n×n
was n >= 4 when the number of dimensions ismore than 3.
a(b) refers to case of the b dimension with the a-squares in all directions

Outline of the proof
1．I proof that in the case n≧5,if n(2) with any n has the Hamiltonian Path which starts in(1,1) and ends in (n-2,1), n(m) (m:m >= 2,an integer) also has the Hamiltonian Path.
2．In the case of n ≧ 5, I proof that n(2) has the Hamiltonian path which starts in (1,1) andends in (n-2,1).
3.In the case of n=4, I show that the Hamiltonian Path which starts in (1,1,1) and finishes in(3,1,4) exists in 4 (3). If it is true,I show that Hamiltonian path exists in 4(m) (m:m >= 3).

Conclusion 2The condition for n(m) to have the Hamiltonian Path isn >= 4 and m >= 3 or n >= 5 and m = 2t