Can You Fill It?
Self-avoiding hamiltonian paths on a square grid.
Chemins auto-évitants hamiltoniens sur une grille carrée.
[EN]
On a square grid, like a chessboard for example, can you imagine a path that goes through each cell once and through each cell?
The mathematical question is formalized on this page:
https://lma.metelu.net/LMA/CanYouFillIt
(thanks to Thierry Monteil for administrating the page)
And has been discussed during this conference:
Journées ALÉA 2011
To this day, the question stays open, there is no formula to easily count the self-avoiding paths that go through each cell. There are computer strategies, such as make an automate crawl, but the speed at which the number of solution grows according to the grid size make those approaches quickly inefficient.
(thanks to Mathieu Sablik for his insights on the question)
From an omnipotent silkscreen print, we connect the cells to reveal a unique path identified by its number.
The number is composed this way: first the size of the grid n×n, then the coordinates of the starting cell, horizontally, from A to E, vertically from 1 to 5, finally the directions taken by the path, 1 for North, 2 for East, 3 for South and 4 for West, such as it is possible to apply an alphabetical order clockwise.
Example for a 3×3 grid
In Mathematics, a path that goes only once per cell is called "self-avoiding". A path that goes through every cells is called "Hamiltonian" after 19th Irish mathematician William Rowan Hamilton. Hence the subtitle "self-avoiding hamiltonian paths on a square grid"
Solutions known up to n=17 :
http://oeis.org/A120443
[FR]
Sur une grille carrée, comme un échiquier par exemple, peut-on imaginer un chemin qui ne passe qu'une seule fois par case et passe par toutes les cases ?
La question mathématique est posée sur cette page (anglais) :
https://lma.metelu.net/LMA/CanYouFillIt
(remerciements à Thierry Monteil pour l'administration de la page)
Et a été abordée au cours de cette conférence :
Journées ALÉA 2011
À ce jour la question reste ouverte, il n'y a pas de formule pour dénombrer simplement les tracés auto-évitants qui passent par toutes les cases. Il existe des stratégies informatiques comme, par exemple, faire faire le chemin à un automate, mais la rapidité de croissance du nombre de solutions en fonction de la taille de la grille fait que ces approches perdent vite pied.
(remerciements à Mathieu Sablik pour ses remarques sur la question)
À partir d'un tirage sérigraphié omnipotent, on connecte les cases pour faire apparaître un chemin unique identifié par son numéro.
Le numéro est formé de la manière suivante : d'abord la taille de la grille n×n, ensuite, les cordonnées de la case de départ, horizontalement de A à E, verticalement de 1 à 5, finalement les directions que prend le chemin, 1 pour Nord, 2 pour Est, 3 pour Sud et 4 pour Ouest, de sorte qu'on puisse appliquer un ordre alphabétique dans le sens de rotation horaire.
Exemple pour une grille de 3×3
En mathématiques un chemin qui ne passe qu'une fois par case est dit "auto-évitant". Un chemin qui passe par toutes les cases est dit "hamiltonien" d'après William Rowan Hamilton, mathématicien irlandais de la première partie du 19e siècle. D'où le sous-titre de "chemins auto-évitants hamiltoniens sur une grille carrée".
Solutions connues jusqu'à n=17 :
http://oeis.org/A120443