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.

A | B | C | D | E | F | G | H | I | J | |
---|---|---|---|---|---|---|---|---|---|---|

A | ||||||||||

B | 2 | |||||||||

C | 2 | 2 | ||||||||

D | ||||||||||

E | 2 | 1 | 2 | |||||||

F | ||||||||||

G | 2 | 2 | ||||||||

H | 2 | |||||||||

I | ||||||||||

J |

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

A | B | C | D | E | F | G | H | I | J | |
---|---|---|---|---|---|---|---|---|---|---|

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 very quickly and use up to eight threads.

Rust ImplementationJava Implementation

The very nature of this problem is computationally taxing. Fast algorithms for solving such problems 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 is technically capable of uncovering all solutions, given infinite time.

These programs generate output showing their starting point and move 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 output.

Visualization Engine1 | 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 |