Dans cet article en deux parties, je vais montrer une implémentation simple en Go du problème du cavalier, les écueils sur lesquels je suis tombé, et l’évolution du code au fur et à mesure

Après avoir bricolé mon petit script de mail en Go, et ayant envie de rejouer un peu avec des langages non scriptés, j’ai décidé de tester un peu plus le langage en implémentant une recherche de solution pour le coup du cavalier.

L’idée du coup du cavalier est de poser le cavalier sur une case de l’échiquier, et de lui faire parcourir l’intégralité de l’échiquier, sans repasser 2 fois sur la même case. Ce problème avait pas mal occupé mes heures de terminales dans les matières où je m’ennuyais (les enfants, ne faites pas ça chez vous), et je ne m’y étais plus intéressé depuis.

Une solution du problème du cavalier

Pour plus d’informations, la page Wikipédia qui en parle.

Le code

Au début je voulais faire un programme qui me sortirait toutes les solutions possibles. Vu le temps que prenait mon premier test, j’ai commencé par mettre en place une version qui s’arrête à la première solution trouvée (il se trouve aussi que le nombre de solutions possible pour un tour fermé, c’est à dire qui revient à sa case de départ, est de 26 534 728 821 064. Donc ça fait beaucoup).

L’idée c’est donc de :

  • Créer une matrice de 8x8 contenant le cheminement
  • Créer une fonction récursive qui teste les 8 possibilités pour chaque déplacement
  • Pour chaque possibilité, tester le coup suivant
  • Sortir si on a une solution

C’est une methode basique, bourine, bref debrute forcepas en finesse du tout. C’est même franchement naïf, ne nous voilons pas la face. Mais il faut bien commencer par quelque chose.

Donc tout d’abord j’ai créé unarray valuesde 8 sur 8, que je remplis de 0. Bien sûr j’aurai pu l’affecter directement à la main, mais je me suis dit que s’il me poussait l’envie de changer les dimensions de mon échiquier, je pourrai le changer là.

Ensuite je lance la récursion et je m’arrête si (quand) j’ai une solution (testOk à vrai).

J’ai défini les directions par un indice de 1 à 8, correspondante chacune à un mouvement du cavalier sur l’échiquier. Le premier appel est à 0 pour positionner le cavalier en 0,0 dans la matrice (position a1) et ne pas le déplacer.

Une fois une solution trouvée j’affiche ma matrice de résultat en bouclant sur chaque entrée.

 1import "fmt"
 2
 3func main() {
 4
 5    // Initialisation de la matrice à 0
 6    values := [8][8]int{}
 7
 8    for i := 0; i < 8; i++ {
 9        for j := 0; j < 8; j++ {
10            values[i][j] = 0
11        }
12    }
13
14    // Lancer la récursion
15    valueRetour, testOk := coupSuivant(values, 0, 0, 0, 0)
16    if testOk {
17        for j := 7; j >= 0; j-- {
18            for k := 0; k < 8; k++ {
19                fmt.Printf("|%3d", valueRetour[j][k])
20            }
21            fmt.Print("|\n")
22        }
23    }
24}

La fonction récursivecoupSuivantprend en paramètre l’état actuel de la matrice, la position où on se trouve en X et Y, la direction vers laquelle on veut tester, et enfin la profondeur.
Elle renvoie une matrice modifiée si le coup était possible, et la même matrice sinon. Le deuxième paramètre renvoyé est un booléen qui devient vrai si la matrice est remplie (et donc la solution trouvée)

Après avoir testé si on a une solution (condition de sortie finale de la récursion : on a bien eu 64 cases remplies), on effectue le mouvement. Par exemple la direction 1 correspond à un déplacement à droite puis en diagonale en bas pour le cavalier.

On teste si on n’est pas sorti de l’échiquier, puis si la case est libre (on n’est pas déjà passé par là).

Toutes les conditions sont bonnes, on peut jouer le coup (marquer la profondeur dans la matrice), et boucler à nouveau sur les 8 directions suivantes.

Pour s’arrêter, on propage le booleen une fois qu’il est vrai.

 1func coupSuivant(values [8][8]int, posX int, posY int, direction int, profondeur int) ([8][8]int, bool) {
 2
 3    // On vérifie si on a terminé
 4    if profondeur == 64 {
 5        return values, true
 6    }
 7
 8    // Appliquer le déplacement suivant la direction
 9    switch direction {
10    case 1:
11        posX -= 1
12        posY -= 2
13    case 2:
14        posX += 1
15        posY -= 2
16    case 3:
17        posX += 2
18        posY -= 1
19    case 4:
20        posX += 2
21        posY += 1
22    case 5:
23        posX += 1
24        posY += 2
25    case 6:
26        posX -= 1
27        posY += 2
28    case 7:
29        posX -= 2
30        posY += 1
31    case 8:
32        posX -= 2
33        posY -= 1
34
35    }
36    // Tester si on sort de l'échiquier
37    if posX < 0 || posY < 0 || posX > 7 || posY > 7 {
38        return values, false
39    }
40    // Tester si on est déjà passé par là
41    if values[posX][posY] != 0 {
42        return values, false
43    }
44
45    // Incrémenter la profondeur
46    profondeur++
47
48    // Affectation de l'entrée dans la matrice
49    values[posX][posY] = profondeur
50
51    // Tester les 8 directions
52    for i := 1; i <= 8; i++ {
53        valueRetour, testOk := coupSuivant(values, posX, posY, i, profondeur)
54        if testOk {
55            return valueRetour, true
56        }
57    }
58    return values, false
59}

Les résultats

Bon, pour faire court, je n’ai pas eu de résultat en lançant le programme tel quel. C’est long. Très. Le programme tourne sur un i7-6700K à 4.00GHz (sur un seul thread). J’ai rajouté un compteur pour voir le nombre d’itération nécessaires pour avoir un résultat. Pour l’exemple je l’ai relancé il y a quelques heures, il tournait toujours lorsque je l’ai arrêté. J’en étais à 252 811 463 itérations :-) Sans solution.

Je me suis donc dit que j’avais dû faire une erreur soit dans ma condition de sortie, soit dans un de mes tests. Alors je l’ai lancé pour une profondeur de 10 (modification de la ligne 4 de ma fonction). Le résultat a été quasi instantané. Donc j’ai testé avec 20. Pareil. 32 ? La même. 40, 50, 60… Toujours instantané. 64 à nouveau. Tourne dans le vide.

Donc j’ai essayé 61, et ça a pris 9 secondes. Ah ! On touche du doigt quelque chose.

A B C D E F G H
8 16 13 10 5 26 29 0 0
7 9 4 17 14 11 6 27 30
6 18 15 12 7 28 25 44 51
5 3 8 19 24 43 50 31 34
4 20 23 38 49 32 35 52 45
3 39 2 21 36 55 42 33 58
2 22 37 48 41 60 57 46 53
1 1 40 61 56 47 54 59 0

On peut constater que cette “solution” est une impasse pour la résolution, mais elle montre que la récursion fonctionne correctement.

Donc j’ai testé avec 62. Là aussi, une dizaine de secondes ont suffit.

A B C D E F G H
8 16 13 10 5 26 29 0 0
7 9 4 17 14 11 6 27 30
6 18 15 12 7 28 25 48 41
5 3 8 19 24 47 40 31 34
4 20 23 46 39 32 35 42 49
3 53 2 21 36 43 58 33 60
2 22 45 52 55 38 61 50 57
1 1 54 37 44 51 56 59 62

Alors 63 ! On passe à environ 40 secondes (et on est toujours dans une impasse)

A B C D E F G H
8 16 13 10 5 26 29 0 63
7 9 4 17 14 11 6 27 30
6 18 15 12 7 28 25 62 49
5 3 8 19 24 51 48 31 36
4 20 23 52 47 32 37 50 61
3 53 2 21 42 45 58 35 38
2 22 43 46 55 40 33 60 57
1 1 54 41 44 59 56 39 34

Bref, la solution à 64 reste inaccessible en terme de temps d’exécution alors qu’à 63 on en trouve une très vite. Frustrant.

Par dépit, j’ai inversé l’ordre de mes règles (direction de 8 vers 1). Et là, un résultat quasi instantané.

Itérations : 2635139

A B C D E F G H
8 48 51 30 55 14 63 28 7
7 31 56 49 62 29 8 13 64
6 50 47 52 25 54 15 6 27
5 41 32 57 46 61 26 9 12
4 58 45 40 53 24 11 16 5
3 39 42 33 60 35 18 21 10
2 44 59 2 37 20 23 4 17
1 1 38 43 34 3 36 19 22

Ce qui donne en coups d’échec :

a1 c2 e1 g2 h4 g6 h8 f7 g5 h3 f4 h5 g7 e8 f6 g4 h2 f3 g1 e2 g3 h1 f2 e4 d6 f5 h6 g8 e7 c8 a7 b5 c3 d1 e3 f1 d2 b1 a3 c4 a5 b3 c1 a2 b4 d5 b6 a8 c7 a6 b8 c6 d4 e6 d8 b7 c5 a4 b2 d3 e5 d7 f8 h7

La solution est valide. L’ordre d’exécution des règles a eu une importance alors que je partais du coin en bas à droite. Probablement que ce ne serait pas cet ordre là en partant d’un autre coin.

Donc j’ai une solution. Wéééé.

Dans un prochain post, je modifierai le code pour afficher les solutions que je trouve en laissant tourner le programme, en lançant un thread pour chaque direction initiale. Et la lecture de la page Wikipédia donne une information importante (règle de Warnsdorf) Pour réussir un parcours, il suffit de choisir pour chaque nouveau saut une case libre parmi celle offrant le moins de sauts ultérieurs possibles. On verra si ça accélère le calcul et combien de résultats on trouve dans un laps de temps raisonnable.

Crédit photo : Michał Parzuchowski