Can You Fill It?

Self-avoiding hamiltonian paths on a square grid.
Chemins auto-évitants hamiltoniens sur une grille carrée.

[EN]
[FR]

[EN]

Maths

The mathematical question is formalized on this page:
https://lma.metelu.net/LMA/CanYouFillIt
(thanks to Thierry Monteil for administrating the page)

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)

Plastic realization

For each possibility, an ink stroke with a 15cm brush and 0.5cm gap between circumvolutions will be made. Each combination will only be made once.On the small grids I will try to exhaust all the combinations. From the 4×4 grid I will adopt a strategy consisting in building series featuring logical links and notable permutations. The point is to offer the viewer who doesn't know the whole project, an access to the inner logics of the series and, from this, to the general case.

Nomenclature

The series are named in a human readable way to facilitate the communication. Also, a rationalized nomenclature will allow the dissociation of the combinations and to sort those in the alphabetical order.

Except for the last one, each cell contains the information of the direction to the next one. The cardinal directions are renamed "1" for North, "2" for East, "3" for South, and "4" for West. The final name contains: the grid dimensions; the coordinates of the start cell; and the n2-1 directions.

[FR]

Mathématiques

La question mathématique est posée sur cette page (anglais) :
https://lma.homelinux.org/wiki/LMA/CanYouFillIt
(remerciements à Thierry Monteil pour l'administration de la page)

À 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)

Réalisation plastique

Pour chaque possibilité, un tracé d'encre avec un pinceau de 15 cm et un écart de 0,5 cm entre les circonvolutions sera réalisé. Chaque combinaison ne sera produite qu'une seule fois. Sur les petites grilles j'essaierai d'épuiser toutes les combinaisons. À partir de la grille de 4×4 j'adopte une stratégie qui consiste à dégager des séries comportant des liens logiques et des permutations remarquables. L'idée est de proposer au spectateur qui ne connait pas la totalité du projet un accès aux logiques propres aux séries et par extension au cas général.

Nomenclature

Les séries portent des noms humainement lisibles pour faciliter la communication. Par ailleurs, une nomenclature rationalisée permettra de dissocier les combinaisons et de les trier par ordre alphabétique.

À l'exception de la dernière, chaque case, contient l'indication de la direction de la case suivante empruntée par le tracé. Les directions cardinales sont renommées "1" pour Nord, "2" pour Est, "3" pour Sud et "4" pour Ouest. Le nom final, comporte : les dimensions de la grille ; les coordonnées de la case de départ ; et les n2-1 directions.


5×5-[A1]-222233334111433341114333 


5×5-[A1]-222234444333211233211233 


5×5-[A1]-222234444322223341434143 

detail
Can you Fill It?: detail