Le cavalier (3)
Parcourir avec un cavalier toutes les cases de l'échiquier une fois et une seule
(donc en 63 coups).
Il existe de très nombreuses solutions.
On peut chercher des solutions avec des caractéristiques spéciales :
- Solution fermée (circuit), c'est à dire qu'au 64ème coup on revient au point de départ.
- Carré magique : les numéros des coups forment un carré magique
(somme des nombres d'une ligne = somme des nombres d'une colonne = cte)
- Elégance et symétries géométriques etc...
The must (in english) : Knight's Tour Notes
Ci-contre un circuit proposé par Euler.
Echiquier réduit 3×4
Nous allons nous entraîner sur cet échiquier réduit et dégager une méthode de résolution.Partons du coin a1 par exemple. Seuls coups possibles a1-c2 et a1-b3.
Essayons c2, puis b4, a2 (forcé), c1, b3 (forcé) ... plus de coups.
En fait on s'en aperçoit maintenant mais c'est bien tard :
Il faut remonter au coup a2-c1, le changer en a2-c3, seule autre possibilité, et s'apercevoir que l'on est encore bloqué un peu plus loin.
Le coup c2-b4 est donc mauvais, on le change en c2-a3, seule autre possibilité. Mais ne conduit à rien non plus.
Conclusion, c'est notre premier coup qui est mauvais : il faut jouer a1-b3, on obtient alors :
a1-b3-c1-a2 (forcés) puis c3 ne mène à rien et il faut jouer b4-c2-a3 (forcés) et là chacune des deux possibilités b1 ou c4 conduit à une solution (par une suite de coups forcés) ouf !
Nous avons trouvé deux solutions et notre méthode étant exhaustive ( = épuisante) nous sommes sûr que c'est les seules avec comme case de départ a1.
Pour trouver toutes les solutions, il "suffit" de recommencer avec une autre case de départ.
Par symétrie, seules les cases a1 (déja fait), b1, a2 et b2 sont à considèrer.
Après pas mal de travail, on trouve la seule autre solution :
b1-c3-a4-b2-c4-a3-c2-a1-b3-c1-a2-b4.
Tout ceci est assez pénible et on peut chercher une méthode qui arrêterait au plus tôt possible
une variante vouée à l'échec.
Cette méthode existe. Son fonctionnement n'est pas garanti mais donne de bons résultats :
Choisir de préférence à chaque pas la case ayant le moins de possibilités restantes.
Ceci n'empêche pas d'arriver sur une impasse, mais en limite fortement la probabilité.
(H. C. Warnsdorff)
Le cas le plus représentatif est quand, ayant le choix entre plusieurs coups,
l'un d'entre eux ne laisse qu'une possibilité d'en sortir.
Si on ne choisit pas tout de suite ce coup, il y a pas mal de chances
que la seule case permettant d'y accéder (donc forcément au dernier coup) soit
nécessaire avant la fin, conduisant à un blocage prématuré.
L'efficacité de cette méthode est telle que en partant de la case a1 on obtient directement une solution,
sans jamais avoir besoin de revenir en arrière !
S'il n'y a pas de solution pour la case de départ choisie (par exemple a2),
il faut quand même essayer les "second choix", mais la méthode permet un certain "élaguage".
Avec un échiquier normal de 64 cases, cette méthode conduit aussi "directement" à une solution,
sans retour en arrière.
Si une fois une solution trouvée, on la rejette, la méthode donne toutes les solutions pour cette case de départ.
Un programme réalisé ainsi fournit des dizaines de solutions par seconde !
Il n'y a toutefois aucun espoir de les obtenir toutes pour l'échiquier de 64 cases : il y en a beaucoup trop, plus de 1013 !
En supposant de trouver un millier de solutions par seconde, il faudrait 300 ans pour les trouver toutes.
Un programme en C :
Source, Télécharger
Mode d'emploi avec -h
-d8x8 dimensions de l'échiquier min 3x3 max 54x54
-(0,0) case de départ
-n1 nombre de solutions éditées
-f solutions fermées
-1 cavalier ordinaire (1,2)
2 = sauteur (0,3)(2,2)
3 = girafe (1,4)
4 = zebre (2,3)
5 = antilope (3,4)
-s(x,y)(x,y)... sauteur générique 4 sauts maxi
distance maxi=5
Quelques résultats :
(le programme ci-dessus ne permet pas d'obtenir certains d'entre eux, durée trop longue de la recherche)
Parcours d'une girafe (1,4) sur un échiquier 5x8
0 5 10 15 20 25 30 35 21 26 31 36 1 6 11 16 2 7 12 17 22 27 32 37 23 28 33 38 3 8 13 18 4 9 14 19 24 29 34 39
Parcours fermé d'une girafe (1,4) sur un échiquier 10x10
0 57 2 13 74 21 86 29 98 55 75 22 85 30 99 56 3 12 73 20 64 41 4 37 76 33 80 31 62 49 77 88 81 96 63 48 7 38 15 34 58 1 8 69 14 87 28 97 54 47 23 92 25 84 51 66 11 70 19 72 42 65 40 5 36 79 32 83 50 61 89 78 95 82 43 60 39 6 35 16 44 59 68 9 90 17 94 27 46 53 91 24 93 26 45 52 67 10 71 18
Parcours d'un zèbre (2,3) sur un échiquier 10x10
0 85 74 41 20 59 4 87 72 45 83 50 17 76 43 2 89 48 29 70 40 19 58 15 86 73 46 21 60 5 75 42 1 84 49 30 71 44 3 88 16 77 82 51 18 61 28 69 90 47 57 14 39 80 55 24 93 6 31 22 12 99 64 37 78 91 8 95 62 33 81 52 25 66 35 10 97 54 27 68 38 79 56 13 94 63 32 23 92 7 65 36 11 98 53 26 67 34 9 96
Le parcours fermé de A.H.Frost (1886!) d'un Zèbre sur un échiquier 10x10
0 67 84 25 12 39 96 65 60 29 69 86 3 82 27 98 63 48 5 58 24 11 40 1 66 61 30 13 38 95 83 26 99 68 85 4 59 28 97 64 2 81 70 87 10 49 6 57 62 47 41 18 23 78 43 16 37 94 31 14 88 73 52 21 80 35 92 75 50 33 71 44 9 54 19 90 77 46 7 56 22 79 42 17 74 51 32 15 36 93 53 20 89 72 45 8 55 34 91 76
Parcours fermé d'un sauteur (0,3)+(2,2) sur un échiquier 10x10
80 73 42 79 74 69 13 77 68 14 44 2 92 65 1 95 60 16 23 59 41 55 81 70 56 78 75 57 12 76 93 72 43 94 97 66 24 96 67 15 45 3 91 64 0 90 61 17 22 58 40 54 82 71 53 83 98 30 11 85 7 37 46 26 88 63 25 89 62 18 48 4 34 49 99 33 52 84 21 31 39 27 8 38 28 9 87 29 10 86 6 36 47 5 35 50 20 32 51 19
Parcours fermé d'une Antilope (3,4) sur un échiquier 14x14 de T.H. Willcocks (1978)
0 55 162 21 110 33 86 39 192 71 160 19 102 49 53 164 79 142 23 108 51 194 73 158 81 126 17 104 166 77 140 187 144 25 106 75 156 83 134 189 128 15 111 32 85 38 1 56 161 20 101 48 87 40 191 70 22 109 34 195 54 163 80 125 18 103 50 193 72 159 143 24 107 52 165 78 141 188 127 16 105 74 157 82 186 145 26 167 76 139 84 133 190 129 14 155 100 135 37 2 57 112 31 92 35 182 41 174 69 124 47 88 180 59 172 7 114 29 90 43 176 67 150 9 122 45 61 170 95 148 5 116 27 178 65 152 97 132 11 120 168 93 138 185 146 3 118 63 154 99 136 183 130 13 113 30 91 36 181 58 173 8 123 46 89 42 175 68 6 115 28 179 60 171 96 149 10 121 44 177 66 151 147 4 117 62 169 94 137 184 131 12 119 64 153 98
D'autres résultats dans "Knight's Tour Notes".
