clavier ouvert

♟2026.05.13
Spirales et chevaliers | 1

Après avoir vu cette fascinante vidéo sur la chaîne Numberphile avec le Professeur Neil Sloane, j’ai eu très envie de faire mon propre générateur de visualisations, pour pouvoir tester différentes règles et configurations. Et parce que le problème a l’air intéressant. Voyons où ça nous mène.

Résumé de la vidéo

Passez directement à la section suivante si vous avez vu la vidéo, je vais juste donner un peu plus de contexte avant de commencer!

La vidéo décrit un “problème” (ou plutôt une curiosité) découverte par Jonas Karlsson. On démarre avec une grille de taille infinie, dans laquelle une case est marquée de l’indice 0. On attribue ensuite des indices croissants en formant une spirale carrée. On a donc, schématiquement, pour les dix premiers indices:

......
.432..
.501..
.6789.
......

On colore ensuite progressivement la grille en suivant la règle suivante:

Sélectionner la case avec le plus petit indice qui est:

• Libre (non-coloriée).
• Ne peut pas atteindre une case colorée via un déplacement de cavalier d’échec.

Dans le schéma ci-dessus, je pourrai donc colorier 0, 1, 2, 3 sans soucis, mais pas 4 (à un déplacement de cavalier de 1), 5 (vu par 2), 6 (vu par 3 et 1), 7 (vu par 2), 8 (vu par 3) ou 9 (vu par 0 et 2). La case libre suivante sera la case 20.

Le site de l’OEIS (l’encyclopédie des séquences entières) nous donne les premiers éléments de la séquence: https://oeis.org/A308885.

On y retrouve aussi le schéma montrant la position des cases “coloriées”, qui forme un motif régulier:

Des règles plus complexes permettent de générer des “grilles colorées” de plus en plus étranges. Par exemple, la séquence présentée dans la vidéo utilise deux “joueurs” (rouge et noir) qui colorient à tour de rôle, avec la règle: sélectionner la case avec le plus petit indice qui est libre et ne peut pas atteindre une case coloriée de l’autre couleur. La séquence se trouve également sur OEIS, et donne le schéma suivant:

D’autres exemples sont donnés dans la vidéo, avec plus ou moins de joueurs et des pièces différentes. Un tas d’illustrations pour des combinaisons de pièces différentes se trouve sur le site de Jonas Karlsson.

Objectif

On retrouve des liens vers le code de Jonas Karlsson sur le site de l’OEIS, mais je ne vais pas le regarder. Je trouve l’exercice intéressant. Mon objectif sera donc de faire un programme permettant de générer des visualisations pour:

• Un nombre de joueurs arbitraires.
• Des déplacements arbitraires (pas uniquement cavalier).
• Un nombre donné de “couches” de la spirale.

Idéalement, j’aimerais bien pouvoir partir d’une fichier de configuration simple, et générer l’image. Quelque chose comme (à raffiner)

{
    "n_layers": 10,
    "players": [
        {"color": "black", "moves": [[1, 2], [1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1], [-1, 2], [-2, -2]]},
        {"color": "red", "moves": [[1, 2], [1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1], [-1, 2], [-2, -2]]}
    ]
}

"moves" décrit les mouvements autorisés pour la pièce (ici, j’ai mis ceux du cavalier).

Échauffement

Je vais essayer de procéder pas à pas, en restant flexible sur la façon dont le code va s’agencer. Je suis beaucoup influencé pour l’instant par Ron Jeffries et son approche extrêmement fluide de la programmation: des petits pas, un code qui reste toujours fonctionnel, qu’on modifie très progressivement, avec un focus sur un code très clair, très expressif, bien maîtrisé. L’approche opposée du vibe coding, en somme.

Première étape: essayons simplement de dessiner la “spirale carrée”, pour commencer à comprendre et cerner le problème.

Mon premier instinct — qui n’est pas nécessairement bon! — est de faire un générateur de position, qui produit les coordonnées successives des “positions sur la grille” en suivant la spirale. Une fonction qui ferait:

from typing import Generator

def position_generator(max_n: int) -> Generator[tuple[int, int], None, None]:
    ...

Qu’on pourrait utiliser ensuite dans un main pour afficher les points reliés dans l’ordre. Juste pour tester le processus, commençons par simplement mettre les points dans l’ordre sur une droite. On fera les virages par la suite.

from typing import Generator

def position_generator(max_n: int) -> Generator[tuple[int, int], None, None]:
    x, y = 0, 0
    for _ in range(max_n):
        yield x, y
        x += 1

if __name__ == "__main__":
    for x, y in position_generator(10):
        print(x, y)

J’obtient bien:

0 0
1 0
...
9 0

L’affichage maintenant:

from typing import Generator, Iterable
from matplotlib import pyplot as plt

def show_points(positions: Iterable[tuple[int, int]]) -> None:
    plt.figure()
    for x, y in positions:
        plt.plot(x, y, 'bo')
    plt.show()


if __name__ == "__main__":
    show_points(position_generator(10))

Ce qui me donne:

Bien. Tout à l’air de fonctionner, mis à part que cela ne fait pas encore ce qu’il faut !

Comment faire pour faire “tourner” les points ? Si on regarde ce que fait la spirale carrée, on suit le processus suivant, à partir de (0, 0) et en imaginant que l’axe x va “à droite” et l’axe y va “vers le haut”:

• Avancer une fois vers la droite pour arriver en (1, 0)
• Avancer une fois vers le haut pour arriver en (1, 1)
• Avancer deux fois vers la gauche pour arriver en (-1, 1)
• Avancer deux fois vers le bas pour arriver en (-1, -1)
• Avancer trois fois vers la droite pour arriver en (2, -1)
• …

On a donc deux “cycles”: “droite”, “haut”, “gauche”, “bas”, et une augmentation de la longueur du segment tous les deux changements de direction.

C’est une bonne occasion de ressortir itertools, cet outil indispensable de la librairie standard Python. Ici, on a itertools.cycle qui nous permet de tourner entre les différentes directions à l’infini:

LEFT = (-1, 0)
RIGHT = (1, 0)
UP = (0, 1)
DOWN = (0, -1)
DIRECTION_CYCLE = [RIGHT, UP, LEFT, DOWN]

def position_generator(max_n: int) -> Generator[tuple[int, int], None, None]:
    x, y = 0, 0
    for i, direction in enumerate(itertools.cycle(DIRECTION_CYCLE)):
        if i >= max_n:
            return
        yield x, y
        dx, dy = direction
        x += dx
        y += dy
        i += 1

Maintenant, le “pas”: lorsqu’on passe de “haut” vers “gauche” et lorsqu’on passe de “bas” vers “droit”, on doit augmenter la longueur du segment. Renommons DIRECTION_CYCLE pour y ajouter cette information, et utilisons-là dans la boucle:

SPIRAL_CYCLE = [(RIGHT, 1), (UP, 0), (LEFT, 1), (DOWN, 0)]

def position_generator(max_n: int) -> Generator[tuple[int, int], None, None]:
    x, y = 0, 0
    length = 0
    for i, (direction, dl) in enumerate(itertools.cycle(SPIRAL_CYCLE)):
        if i >= max_n:
            return
        yield x, y
        length += dl
        dx, dy = direction
        x += dx*length
        y += dy*length
        i += 1

On a deux problèmes: c’est difficile de voir l’ordre des points, et on ne doit normalement pas “sauter” d’un bout du segment à l’autre comme ça. Il manque tous les points intermédiaires. Commençons par modifier la vue, toujours à l’aide de itertools, mais cette fois-ci avec itertools.pairwise pour parcourir les positions deux à deux, ce qui va me permettre de relier les points successifs.

def show_points(positions: Iterable[tuple[int, int]]) -> None:
    plt.figure()
    for (x1, y1), (x2, y2) in itertools.pairwise(positions):
        plt.plot(x1, y1, 'bo')
        plt.plot([x1, x2], [y1, y2], 'k-')
    plt.show()

Pour afficher tous les points, il faut un tout petit peu réorganiser position_generator. Au passage, je me rend compte que j’avais un i += 1 inutile en fin de boucle (puisque i était mis à jour par enumerate). De toute façon, le compteur bouge de place:

def position_generator(max_n: int) -> Generator[tuple[int, int], None, None]:
    x, y = 0, 0
    length = 0
    n_points = 1
    yield x, y
    for _, (direction, dl) in enumerate(itertools.cycle(SPIRAL_CYCLE)):
        length += dl
        dx, dy = direction
        for _ in range(length):
            if n_points >= max_n:
                return
            n_points += 1
            x += dx
            y += dy
            yield x, y

On y est. Le code n’est pas hyper lisible, cependant, essayons de rendre ça un peu plus clair. Je n’aime pas le fait d’avoir deux yield, ni les boucles imbriquées.

Mettons une seule boucle for sur le nombre de points, avec une condition pour détecter le changement de position:

def position_generator(max_n: int) -> Generator[tuple[int, int], None, None]:
    x, y = 0, 0
    dx, dy = 0, 0
    length = 0
    current_pos_in_segment = 0
    cycle = itertools.cycle(SPIRAL_CYCLE)
    
    for _ in range(max_n):
        yield x, y 
        if current_pos_in_segment == length:
            direction, dl = next(cycle)
            dx, dy = direction
            length += dl
            current_pos_in_segment = 0
        x += dx
        y += dy
        current_pos_in_segment += 1

C’est déjà mieux… et on va s’arrêter ici pour l’instant.

[lien permanent]