A Hamiltonian Path

The problem is as follows: within a ten by ten grid the first square is marked one, and you must then place the second and all subsequent points in the fashion shown below. This forms a heavily constrained Hamiltonian path wherein each node is liked with eight other nodes.

The problem is as follows: within a ten by-ten grid the first square is marked one, and you must then place the second and all subsequent points in the fashion shown below. This forms a heavily constrained Hamiltonian path wherein each node is liked with eight other nodes.

	C	D	F	H	I
A
B			2
C		2		2
D
E	2		1		2
F
G		2		2
H			2
I
J

This process is repeated until the whole grid is covered using the same rules. Below is an example of the process completed by linking several nodes.

	B	C	E	F	H
A	1		2
B
C		3		8
D
E			4		7
F
G
H			5		6
I
J

I have written two systems for generating solutions to this problem. My first implementation was written in Java for easy prototyping. A subsequent version was developed in Rust that can validate quickly and use up to eight threads.

Rust Implementation
Java Implementation

The very nature of this problem is computationally taxing. Fast algorithms for solving such issues generally are not capable of enumerating all possible solutions: which is a design goal of my programs. Although I have only processed a tiny fraction of all possible solutions, the program can technically uncover all solutions, given infinite time.

These programs generate output showing their starting point and movement pattern in a CSV text stream. Some example results are given below.

X	Y	Pattern
0	0	412244500024447005024446030030503446005050330505224460500503334165602503600305424614165017424614700
0	0	412244500024447005024446030030503446005050330505224460500644147427250303250674360003644203057030544
0	3	410224450002444700502444603003050344600505033050522446050064336113416755217460027444205053160035016
0	3	410224450002444700502444603003050344600505033050522446050742325756136036136113650357002503642500306

I also created a JavaScript-based visualization engine that uses the output of either generator to draw up a table to show the results. Below is a link to the visualizer and an example of its work.

Visualization Engine

1	100	91	2	99	92	89	98	95	88
60	76	79	59	75	80	69	74	83	68
43	3	49	42	90	72	96	87	71	97
78	58	61	77	57	93	84	56	94	85
48	41	44	47	40	81	70	73	82	67
20	4	50	19	62	55	26	86	54	25
11	46	39	10	45	38	9	66	37	8
33	18	29	32	17	28	63	16	27	64
21	5	51	22	6	52	23	7	53	24
12	31	34	13	30	35	14	65	36	15

A Hamiltonian Path

Read next

Miles Till Wall Drug

Quizbowl Schedule Generator

1	100	91	2	99	92	89	98	95	88
60	76	79	59	75	80	69	74	83	68
43	3	49	42	90	72	96	87	71	97
78	58	61	77	57	93	84	56	94	85
48	41	44	47	40	81	70	73	82	67
20	4	50	19	62	55	26	86	54	25
11	46	39	10	45	38	9	66	37	8
33	18	29	32	17	28	63	16	27	64
21	5	51	22	6	52	23	7	53	24
12	31	34	13	30	35	14	65	36	15

1	100	91	2	99	92	89	98	95	88
60	76	79	59	75	80	69	74	83	68
43	3	49	42	90	72	96	87	71	97
78	58	61	77	57	93	84	56	94	85
48	41	44	47	40	81	70	73	82	67
20	4	50	19	62	55	26	86	54	25
11	46	39	10	45	38	9	66	37	8
33	18	29	32	17	28	63	16	27	64
21	5	51	22	6	52	23	7	53	24
12	31	34	13	30	35	14	65	36	15

1	100	91	2	99	92	89	98	95	88
60	76	79	59	75	80	69	74	83	68
43	3	49	42	90	72	96	87	71	97
78	58	61	77	57	93	84	56	94	85
48	41	44	47	40	81	70	73	82	67
20	4	50	19	62	55	26	86	54	25
11	46	39	10	45	38	9	66	37	8
33	18	29	32	17	28	63	16	27	64
21	5	51	22	6	52	23	7	53	24
12	31	34	13	30	35	14	65	36	15