Le jeu de Wyx

Le jeu Wyx inventé par Joël Gauvain peut se jouer à deux ou à un seul joueur. Cette page est consacrée au puzzle à un seul joueur qui utilise des grilles préparées.
Visitez le site de Wyx, si vous jouez seul, procurez-vous les grilles du jeu et excercez-vous. Vous pourrez aussi jouer en ligne sur une centaine de grilles Wyx.

Wyx est un jeu mathématique pour tous publics, certaines grilles parmi les moins compliquées peuvent être résolues par des enfants. Wyx permet d'aborder le plus simplement possible un grand nombre de notions mathématiques diverses, en géométrie ce sont la translation plane, les vecteurs et la somme vectorielle, en théorie des graphes ce sont les chemins hamiltoniens multicolores (ou arcs-en-ciel)...

Rechercher une solution incite à élaborer des algorithmes réfléchis, justifiés et efficaces, c'est-à-dire à faire des mathématiques.

Sur chaque feuille vous apercevez à gauche un échiquier de 8x8=64 cases, certaines marquées d'un rond .
La case de départ est marquée d'un cavalier qui devra aller d'un rond à l'autre jusqu'au dernier. Parfois le premier et le deuxième arrêt sont indiqués.

À droite de la feuille de jeu, vous avez 12 dominos qui correspondent chacun à un déplacement de plusieurs cases vers la gauche ou la droite et aussi de plusieurs cases vers le bas ou le haut. Ainsi le domino correspond à un déplacement de 3 cases vers la gauche et deux cases vers le bas, c'est-à-dire tout simplement à une translation de vecteur u(-3, -2). Ces 12 déplacements sont deux à deux différents.
Dans ses déplacements, le cavalier devra effectuer une fois et une seule chacun des 12 déplacements. Les grilles sont construites pour qu'il y ait une solution et une seulement.

Tout d'abord on peut remarquer que si l'on connaît la case de départ (le cavalier), on connaît aussi la case d'arrivée : en composant les dominos et leurs déplacements dans n'importe quel ordre, vous obtenez le même point d'arrivée, même si vous ne passez pas par les bonnes cases intermédiaires.
(En effet l'addition des vecteurs est associative et commutative).

Résoudre une grille de Wyx, c'est trouver un chemin allant du point de départ (le cavalier) au point d'arrivée (déterminé ci-dessus), en passant une fois et une seule par chacun des autres sommets, en utilisant une fois et une seule chaque domino dans un passage d'un sommet au suivant du parcours.
Par exemple, l'application placée plus bas dans la page m'indique pour une certaine grille cette solution :
Points : A L F K G H E C B D J I M
Vecteurs : i k e h f a l g j c d b
Le jeu est constitués de 13 points que l'on peut appeler A B C ... K L M et de 12 dominos appelés de même a b c d ... j k l.
Le chemin trouvé passe par les points 13 points, non pas dans l'ordre alphabétique, mais dans l'ordre A L F K G H E C B D J I M, en utilisant successivement les dominos dans l'ordre i k e h f a l g j c d b.
En effet, pour ce jeu, le domino i permet d'aller du point de départ A au point L (second de la liste), ensuite le domino k permet de joindre L à F, puis e de F à K et ainsi de suite.

comme ci-dessus, appelons A=cavalier=départ, B, C, ..., K, L, M=arrivée, les 13 cases marquées sur l'échiquier.
Appelons aussi a, b, c, ..., k, l, les 12 dominos, les déplacements ou leurs vecteurs.
Très généralement, lorsqu'un domino u permet d'aller d'une certaine case P vers une autre case Q, tracez une flèche de P vers Q sur la figure.
Mieux, coloriez avec 12 couleurs toutes les flèches, en choisissant une seule et même couleur pour les flèches qui correspondent à un même domino.
Finalement vous obtenez la figure d'un graphe orienté G dont l'ensemble des sommets est {A, B, C, ..., L, M} et dont les arcs sont coloriés à l'aide de 12 couleurs.

La solution du jeu est un chemin hamiltonien multicoloré du graphe, passant par tous les sommets de A à M et empruntant un arc et un seul de chaque couleur disponible (ce sous-graphe est un arc-en-ciel).

Le graphe peut être redessiné sans respecter les positions des sommets ni longueurs et les directions des arcs, le principal étant que la figure soit lisible.

Je préfère utiliser la matrice du graphe ou plus exactement un tableau dont les marges de gauche et du haut contiennent les noms des sommets de A à M et dont les cases intérieures contiennent les noms des dominos (c'est-à-dire les vecteurs ou les couleurs des arcs) : à l'intersection de la P et de la colonne Q on place la couleur u de l'arc qui va de P vers Q, lorsqu'un tel arc existe, sinon on n'inscrit rien.
Par exemple, ci-dessous, à l'intersection de la ligne E et de la colonne J, se trouve la couleur f.
(Sur la grille de Wyx, le domino f permet d'aller de la case E à la case J).

    A B C D E F G H I J K L M
--+---------------------------
A |     c
B |             k   e
C | l       e b         j
D |               c j
E | d j   e           f
F |               h         a
G | j                   g
H |       l d
I |                       a
J |     a                   l
K |   e               i
L |   f   i
M | a                 c

Dans ce qui suit on désigne par 'u' une couleur d'arc quelconque, ce peut être a ou b ou ...
Commencez par effectuer une fois pour toute les deux manipulations ci-dessous.

1. Effacez la dernière ligne, celle de M, en effet le point M est le point d'arrivée.
2. Pour une raison similaire, effacez la première colonne, celle du point de départ.

Dans ce qui suit le tableau n'a plus que 12 lignes et 12 colonnes.
La méthode proposée consiste à effacer successivement, par un raisonnement adapté, les couleurs à l'intérieur du tableau jusqu'à ne conserver que 12 noms différents, une par ligne et une par colonne, on aura alors une solution.

1. Lorsqu'il n'y a qu'une seule couleur 'u' sur une ligne, alors elle apparaîtra dans la solution, à cet endroit et pas ailleurs.
   • Effacez tous les autres 'u' du tableau.
   • Effacez tous les autres couleurs de la colonne de 'u' (mais pas 'u', elle fait partie de la solution)
2. De même, lorsqu'il n'y a qu'une seule couleur 'u' inscrite dans une colonne
   • Effacez les autres 'u' du tableau.
   • Effacez les autres couleurs de la ligne de 'u'
3. Si la couleur 'u' ne figure que dans une seule case du tableau, effacez toutes les autres couleurs de sa ligne et de sa colonne.
4. Si vous observez qu'une ligne ou une colonne est vide, alors il n'y a pas de solution. (Dans le tableau de 12 lignes et 12 colonnes, pas dans le tableau initial).
5. Si un circuit XY...Z apparaît entre deux ou plusieurs points, alors vous n'obtiendrez plus de chemin hamiltonien dans cette grille. Rejetez cette grille.
6. On n'arrive pas toujours directement au résultat à l'aide des manipulations précédentes. Si vous n'arrivez plus à progresser, choisissez une ligne ou une colonne contenant le moins possible de couleurs et faites autant de copies de votre tableau, mais ne gardez dans les différentes copies qu'une seule des couleurs de cette ligne ou de cette colonne.

Évidemment recommencez ces manipulations autant de fois que nécessaire, jusqu'à obtenir les solutions, s'il en existe.

    B C D E F G H I J K L M    il ne reste que 12 lignes et 12 colonnes
--+-------------------------
A |   c                        <-- 1) c est seul sur la ligne
B |           k   e
C |       e b         j
D |             c j            <-- 1) effacez c, le j reste seul
E | j   e           f
F |             h         a
G |                   g        <-- 2) observez
H |     l d
I |                     a      <-- 3) observez
J |   a<--1) effacez      l
K | e               i         
L | f   i

Exercez-vous sur les exemples calculés par l'application ci-dessous.
L'application vous donne les coordonnées des points et des vecteurs, un schéma des positions des points dans le plan et le tableau à simplifier. Le point de départ est A, le point d'arrivée est M, les autres points et les vecteurs sont donnés dans le désordre.
Pour obtenir la solution, cochez à tout moment la petite case de droite. L'application ne donne qu'une solution même s'il en existe plusieurs. Dans tous les cas le nombre de solutions existantes est indiqué.
Utilisez les flèches <- et -> pour retrouver les exemples précédents.

Graphes de Wyx

   Joindre une solution

Les 12 dominos sont choisis dans un ensemble symétrique de 64 vecteurs de coordonnées (x, y), -4≤x≤4, -4≤y≤4, et différents de (0, 0), (±3, ±3), (±3, ±4), (±4, ±4).
Les points doivent être tous contenus dans un carré de 8×8=64 points.
Ne vous privez pas d'utiliser ces grilles, plus de 2×10⁸ sont produites à la minute par l'équivalent, en C, du programme ci-dessus.

La résolution de ce jeu de Wyx a été réalisée en Prolog par Fabrice Bizec (fichier wyx.pl).
Prolog est tout à fait indiqué pour résoudre ce problème, on appréciera la grande simplicité de la programmation Prolog.

wyx(_, [], _, []) :- !.

wyx(DOMINOS, LOCATIONS, p(ACTU_X, ACTU_Y), [NEW_POS|SOLUTION_INTER]) :-
	select(d(X, Y), DOMINOS, RES_DOMINOS),
	NEW_X is ACTU_X + X,
        NEW_Y is ACTU_Y - Y,
	NEW_POS = p(NEW_X, NEW_Y),
	select(NEW_POS, LOCATIONS, RES_LOCATIONS),
	wyx(RES_DOMINOS, RES_LOCATIONS, NEW_POS, SOLUTION_INTER).

problem(SOLUTION) :-
	DOMINOS = [d(-1, +4), d(+2, -1), d(-2, -2), d(+3, -2), d(0, -1), d(0, +1), d(-3, +1), d(+1, -1), d(-2, -1), d(0, +2), d(+2, +3), d(-2, 0)],
	LOCATIONS = [p(1, 0), p(1, 3), p(2, 4), p(3, 4), p(4, 4), p(4, 5), p(6, 5), p(1, 6), p(2, 6), p(4, 6), p(6, 6), p(2, 7)], 
	ORG = p(3, 3),
	wyx(DOMINOS, LOCATIONS, ORG, SOLUTION).

Les données du problème doivent être indiquées dans DOMINOS, LOCATIONS, ORG.
On peut exécuter ce programme en utilisant SWI Prolog (par exemple en ligne de commande : swipl -s wyx.pl). On indique ensuite problem(S). pour obtenir les solutions :

wyx$ swipl -s wyx.pl
% library(swi_hooks) compiled into pce_swi_hooks 0.00 sec, 3,856 bytes
...

?- problem(S),print(S).
[p(3,4),p(1,6),p(2,7),p(4,4),p(1,3),p(4,5),p(6,6),p(6,5),p(4,6),p(2,6),p(2,4),p(1,0)]
S = [p(3, 4), p(1, 6), p(2, 7), p(4, 4), p(1, 3), p(4, 5), p(6, 6), p(6, 5), p(..., ...)|...]