Le grand serpent va résoudre les sudokus, le jeu de grille classique, en semant de petits cailloux sur son chemin. L’algorithme de résolution en Python 3 utilisera la technique du backtracking sans récursivité. Le code effectuera les vérifications nécessaires avant la résolution et signalera une grille sans solution.
En dix ans, le Sudoku (Fig. 1) est devenu un classique des rubriques de jeux des magazines et des journaux comme des étals de magazines spécialisés dans les casse-tête. La difficulté est variable, de simplissime à diabolique, parfois impossible car il contient des informations contradictoires. Une grille est censée n’avoir qu’une solution.
Fig. 1 : Exemple de Sudoku 9×9 fourni par le paquet sgt-puzzles [1] dans Debian ; le jeu s’appelle « solo » dans le menu.
Je rappelle les règles du jeu pour éviter un lézard. Le jeu consiste en une grille de 9×9 cases, qui soit contiennent un chiffre entre 1 et 9 (les indices), soit sont vides (représentées par un 0). Il faut compléter les cases vides pour que chaque ligne, colonne ou cellule (les carrés de 3×3 cerclés de gras) contiennent tous les chiffres de 1 à 9 et une seule fois chacun. Mathématiquement, il s’agit du résultat de permutations [2] des neuf chiffres et la grille résolue est un carré latin.
Je commencerai par les vérifications de droits et de règles, puis je m’attaquerai à la partie plus difficile, la résolution par backtracking sans récursivité. Le code est en général présenté dans l’ordre de lecture (voir les numéros de lignes) ; les deux fonctions sont expliquées quand elles sont appelées.
De temps en temps, un point sur un élément du langage, une astuce ou une erreur classique sera fait.
Le code est en Python 3, mais si vous tenez vraiment à l’écrire en Python 2, il vous suffit de changer le shebang, d’ajouter l’import et de modifier les deux divisions entières dans la fonction casepos comme suit :
01: #!/usr/bin/python2
04: from __future__ import print_function
13: cellule = case[0] / 3 , case[1] / 3
1. Le parcours d’obstacles
Je vais commencer par une batterie de tests avant toute tentative de résolution :
- Le fichier existe-t-il ?
- A-t-on le droit de le lire ?
- Est-il dans le bon format de 9×9 chiffres ?
- La grille contient-elle de grossières contradictions ?
- Quand est-ce qu’on mange ?
Une fois tous ces tests passés, le grand serpent pourra commencer son chemin vers la digestion^w résolution.
1.1 Premières vérifications et initialisations
Tout d’abord, le shebang (la deuxième ligne, inutile en Python 3, n'est pas gênante puisqu'il s'agit d'un commentaire et qu'elle pourra servir en cas de passage à Python 2) :
1: #!/usr/bin/python3
2: # -*- coding: utf-8 -*-
Suivent l’import de la commande exit pour interrompre en cas d’erreur et argv pour obtenir le nom du fichier contenant la grille depuis la ligne de commandes :
5: from sys import exit, argv
Le code est court, on ne risque pas de conflit, donc je n’importe que ce dont j’ai besoin au lieu de toute la bibliothèque.
On teste si un nom de fichier a été donné en entrée, sinon on affiche une courte aide. On aurait aussi pu tester la longueur de la liste argv.
29: try:
30: fichier = argv[1]
31: except IndexError:
32: print("Usage : " + argv[0] + " fichier.txt")
33: exit(0)
La commande try permet, en cas d’erreur prévue dans le bloc qui suit, de ne pas planter le programme avec un message cryptique pour l’utilisateur, tout en lui donnant une information compréhensible. Pour obtenir une erreur et le message à intercepter, on peut consulter la liste dans la documentation de Python [3] ou la provoquer :
$ ./sudoku.py sudoku.txt
Traceback (most recent call last):
File "./sudoku.py", line 98, in <module>
sudoku[trous[casearemplir][0]][trous[casearemplir][1]]=possibles[casearemplir].pop()
IndexError: pop from empty list
On initialise la grille du jeu et les coordonnées des cases à compléter (les trous) par des listes vides.
38: sudoku = []
39: trous = []
J’expliquerai dans la section 1.3 comment sont stockées les informations dans les variables sudoku et trous.
1.2 Les tests sur le fichier lui-même
Comme suggéré dans l’article sur les bonnes pratiques en Python de GLMF n°173 [4], j’utilise with au lieu de f=open(fichier,"r") suivi de f.close() ailleurs dans le code. Les deux erreurs gérées sont évidentes.
41: try:
42: with open(fichier,"r") as f:
La suite dans la section 1.4.
54: except FileNotFoundError:
55: print("Fichier " + fichier + " non trouvé.")
56: exit(1)
57: except PermissionError:
58: print("Vous n’avez pas le droit de lire le fichier " + fichier + ".")
59: exit(1)
with permet la gestion transparente (en clair, sans effort) de la fermeture du ficher à la fin du bloc.
1.3 Le format du fichier et des variables
Avant de poursuivre l’explication du code, il est nécessaire de préciser le format des trois variables essentielles : sudoku, trous et possibles. Un problème avec cette liste de variables ?
sudoku contient la grille du jeu, c’est une liste qui contient les neuf lignes.
Voici le fichier sudoku.txt qui correspond à la grille de la copie d’écran de solo :
$ cat sudoku.txt
004903008
003050002
978200000
269030000
000060000
000090615
000005486
700080100
400109500
La liste sudoku est égale à [[0,0,4,9,0,3,0,0,8],[0,0,3,0,…],…] à la fin du remplissage expliqué dans la section suivante. Les cases qui contiennent 0 seront remplies par un chiffre non nul ou remises à 0 durant l’algorithme de backtracking, les autres sont invariables.
trous contient la liste des coordonnées des cases à compléter ; elles valent 0 dans sudoku lors du remplissage. Cette liste est invariable, c’est elle que parcourt le grand serpent pour remplir le plateau de jeu. Dans notre cas, trous sera égal à [[0,0],[0,1],[0,4],…] (les lignes d’abord, de haut en bas, puis les colonnes, c’est le sens de la lecture). Par exemple, sur la première ligne, notée [0,0,4,9,0,3,0,0,8] dans la liste sudoku, il y des cases vides en position 0, 1, 4, 6 et 7. Donc, un trou en ligne 0 et position 0 ([0,0]), puis en ligne 0 et position 1 ([0,1]), etc.
Enfin, la variable possibles est une liste de même dimension que trous, mais qui contient, pour chaque élément en regard de celui dans trous, la liste des chiffres possibles et non encore testés. Par exemple, au tout début de l’algorithme de résolution, possibles sera égal à [[1,5,6],[],[],[],…] parce que les chiffres 1, 5 et 6 sont les seules valeurs possibles de la cellule [0,0] à ce moment précis. Cette variable est modifiée au fur et à mesure du déroulement de l’algorithme.
Ce petit tableau présente les chiffres possibles des trois premières cases vides de la grille vierge :
|
rang dans la liste |
0 |
1 |
2 |
… |
|
trous |
[0,0] |
[0,1] |
[0,4] |
… |
|
possibles |
[1,5,6] |
[1,2,5] |
[1,7] |
… |
1.4 Le remplissage initial de la grille
Voici la partie manquante de la section 1.2 :
43: for nl,ligne in enumerate(f):
44: try:
45: nouvelle = [int(i) for i in list(ligne.strip())]
46: except ValueError:
47: print("La ligne " + str(nl + 1) + " contient autre chose qu’un chiffre.")
48: exit(1)
49: if len(nouvelle) != 9:
50: print("La ligne " + str(nl + 1) + " ne contient pas 9 chiffres.")
51: exit(1)
52: trous = trous + [[nl,i] for i in range(9) if nouvelle[i] == 0]
53: sudoku.append(nouvelle)
On utilise la fonction enumerate qui retourne le numéro de la ligne courante dans nl et son contenu dans ligne, c’est plus élégant et plus pythonique que d’incrémenter nl à la fin de la boucle.
Pour chaque ligne du fichier (c’est une chaîne de caractères), ligne 45, on tente de stocker les entiers qui la composent dans la variable nouvelle. On applique la méthode strip pour supprimer l’éventuel saut de ligne à la fin de la ligne, puis on transforme le résultat en une liste de caractères qu’on tente de convertir en entiers. On a construit nouvelle par une définition en compréhension.
Comme en mathématiques, on peut définir une liste (comme un ensemble ou un dictionnaire, voir encadré suivant) en extension ou en compréhension. En extension, on donne la liste explicite des éléments qui la constituent, par exemple L = [4,9,25,49]. En compréhension, on reprend la manière mathématique, par exemple [i ** 2 for i in [2,3,5,7]]. Mathématiquement, on écrit {i²/i∈{2,3,5,7}}. On peut restreindre la liste avec un test, par exemple [i ** 2 for i in range(1,10) if estpremier(i)] si on a au préalable écrit la fonction estpremier au nom bien choisi, c’est-à-dire {i²/i∈[1,9]∩ℙ} si ℙ est l’ensemble des nombres premiers ; ∩ est l’opération d’intersection de deux ensembles, c’est l’opérateur & en Python.
La méthode append ajoute un seul élément en fin de liste, alors que l’addition concatène deux listes. Si L = [1,2], L.append([3,4]) transforme L en [1,2,[3,4]] alors que L = L + [3,4] transforme L en [1,2,3,4]. La concaténation n’est pas commutative, car L = [3,4] + L transforme L en [3,4,1,2]. J’évite d’utiliser une syntaxe comme L += [3,4], même si elle correspond à la première forme.
Quant à la variable trous, ligne 52, on lui ajoute les coordonnées des cases nulles et uniquement d’elles. La définition en compréhension se termine par le test de nullité de la case.
Les numéros de ligne des erreurs sont rendus lisibles pour un humain, ils commencent à 1, contrairement aux indices des lignes de Python.
Cette série de tests se termine juste après les deux instructions except de la section 1.2 par une vérification du nombre de lignes :
60: if nl != 8:
61: print("Le jeu contient " + str(nl+1) + " lignes au lieu de 9.")
62: exit(1)
L’énumération commence à 0, c’est pourquoi neuf lignes donneront à nl la valeur de 8.
Le fichier peut se terminer par une ligne vide, elle sera supprimée automatiquement par la méthode strip sur la dernière ligne du jeu.
1.5 Les tests de validité avant résolution
La fonction estcontradictoire renvoie True si un chiffre non nul est présent plus d’une fois dans la liste en paramètre et False sinon.
18: def estcontradictoire(liste):
23: chiffres = set(liste) - {0}
24: for c in chiffres:
25: if liste.count(c) != 1:
26: return True
27: return False
Pour cela, chiffres est un ensemble (au sens de Python) des chiffres non nuls de la liste, c’est-à-dire que chaque chiffre n’est présent qu’une fois. La différence E - F entre deux ensembles n’enlève à E que ses éléments qui sont aussi dans F, il n’y a donc pas d’erreur à soustraire {0} si la liste ne contient que des chiffres non nuls (elle est complète).
La méthode count(c) appliquée à une liste compte le nombre d’occurrences de l’élément c.
Un ensemble E, en Python, est une liste non ordonnée, ce qui veut dire que ses éléments n’ont pas d’indice : une syntaxe comme E[1] est erronée. De plus, chaque élément ne peut être présent qu’une fois. Ainsi, {1,2,3} ou set([1,2,3]) est un ensemble au sens de Python, pas {1,1,2}. Ajouter à un ensemble un élément déjà présent ne le modifie pas. Python autorise le parcours des éléments de l’ensemble avec une syntaxe du type for e in E:, mais l’ordre de parcours n’est pas garanti d’un parcours à l’autre pour un même ensemble, contrairement à une liste classique. Un ensemble est un itérable non ordonné.
Tout matheux qui a touché à Python a essayé d’écrire des ensembles d’ensembles et a constaté une erreur de type (TypeError) parce que dans ce langage, les éléments d’un ensemble doivent être hashables. Ils possèdent la méthode __hash__, leur id dépend de leur adresse en mémoire et de leur valeur. En gros, les types de variables immutables sont hashables comme les nombres, les chaînes de caractères, les tuples (les listes invariables) ou les frozen sets (voir plus bas) ; les conteneurs modifiables ne le sont pas (comme les ensembles, les listes ou les dictionnaires). Certains auteurs [5] parlent d’une implantation fautive du concept d’ensemble.
Voici un petit tableau qui illustre ce qui se passe si on tape ces commandes suivies de l’affichage de l’id de la variable concernée dans une console Python :
|
commande |
a = 2 |
a += 3 |
b = 2 |
c = 2 |
a = [5] |
|
id |
138356144 |
138356192 |
138356144 |
138356144 |
3072288940 |
|
commande |
a.append(4) |
a = [5,4] |
a = a + [6] |
b = [5] |
c = [5] |
|
id |
3072288940 |
3072288236 |
3072288396 |
3072288236 |
3072288940 |
N’utilisez pas id(_), mais id(a). _ contient bien le dernier résultat obtenu, mais id(_) contient l’id de _, pas de la dernière variable affichée. _ peut par ailleurs servir de poubelle sans fond, comme dans a , _ , c = range(3).
Pour contourner cette impossibilité, Python dispose des ensembles « gelés » ou frozen sets. Ces derniers peuvent contenir n’importe quoi, y compris des ensembles et des listes. En contrepartie, ils sont invariables et n’ont pas de méthode remove, discard ou add. Cela dit, si E = frozenset([1,2,3,4]), une syntaxe comme E = E & {-1,0,1,2} ou E &= {-1,0,1,2} fonctionne et E sera bien égal à frozenset([1,2]).
Python dispose aussi des dictionnaires ou tables de hachage. Il s’agit d’un ensemble de paires clé:valeur, un matheux y reconnaît l’archétype d’une fonction représentée avec des flèches. Les clés sont uniques (comme les éléments de l’ensemble de départ d’une fonction n’ont qu’une seule image), mais doivent être hashables ; les valeurs peuvent contenir n’importe quoi, y compris des ensembles, des listes ou d’autres dictionnaires. Par exemple, si D = {-1:1,0:0,1:1,2:4,3:9,"inf":"inf","i":-1}, D[-1] et D[1] retournent 1, alors que D["inf"] retourne "inf". On peut parcourir les clés d’un dictionnaire avec for c in D: ou for c in D.keys(): et les valeurs avec for v in D.values(): (attention, les valeurs en double seront présentes deux fois dans le parcours). L’ordre de parcours n’est encore une fois pas garanti.
À ce propos, {} ou dict() désignent le dictionnaire vide, alors que l’ensemble vide est set().
On aurait pu éviter d’utiliser un ensemble et tester chaque élément de la liste, mais il aurait fallu vérifier si l’élément c était égal à zéro, qui a le droit d’être répété. Cela aurait donné ce code :
18: def estcontradictoire(liste):
23: for c in liste:
24: if c != 0 and liste.count(c) != 1:
25: return True
26: return False
Si c est égal à 0, l’opérateur and s’arrête et ne fait pas compter les occurrences du 0. On teste éventuellement plusieurs fois un élément.
On teste si chaque ligne est contradictoire ou non :
66: for l in range(9):
67: if estcontradictoire(sudoku[l]):
68: print("La ligne " + str(l + 1) + " est contradictoire.")
69: exit(1)
Puis chaque colonne :
70: for c in range(9):
71: colonne = [sudoku[l][c] for l in range(9)]
72: if estcontradictoire(colonne):
73: print("La colonne " + str(c + 1) + " est contradictoire.")
74: exit(1)
sudoku étant une liste de listes, sudoku[1] retourne la deuxième ligne et vaut [0,0,3,0,5,0,0,0,2], sudoku[1][2] vaut donc 3, c’est le troisième élément de la deuxième ligne.
Enfin, chaque cellule de 3×3 est formatée en une ligne pour pouvoir être gérée par la fonction estcontradictoire :
75: for l in range(3):
76: for c in range(3):
77: cellule = []
78: for i in range(3):
79: cellule = cellule + sudoku[l * 3 + i][c * 3:(c + 1) * 3]
80: if estcontradictoire(cellule):
81: print("La cellule (" + str(l + 1) + ";" + str(c + 1) + ") est contradictoire.")
82: exit(1)
La construction du contenu de la cellule utilise les tranches (slices) qui sont construites sur le même modèle que range. range(1,16,3) retourne successivement les entiers 1, 4, 7, 10 et 13, mais pas 16 (c’est une particularité de cette fonction en Python où la borne supérieure d’un range n’est jamais atteinte). De même, liste[1:16:3] retourne une liste formée des éléments de mêmes indices s’ils existent. Les valeurs par défaut sont dans l’ordre, 0, len(liste) et 1 pour le pas, on peut les omettre. liste[::-1] inverse la liste.
En Python 2, range retourne une liste, ce qui veut dire que range(10 ** 12) est déconseillé. En revanche, xrange en Python 2 et range en Python 3 sont des générateurs qui consomment peu de mémoire, car les éléments retournés sont créés à la demande.
En Python, sudoku[:][0] ne retourne pas la liste des premiers éléments de chaque ligne mais la première ligne puisque sudoku[:] est égal à sudoku. Si vous voulez une construction des tranches à plusieurs dimensions plus intuitive (plus proche de Scilab), renseignez-vous sur la classe array de la bibliothèque Numpy [6]. Cette classe a pour contrainte de contenir uniquement le même type (par exemple des entiers, mais pas à la fois des entiers et des flottants), mais a pour avantage d’être plus rapide.
2. La voie du grand serpent
Le code de résolution m’a été inspiré par celui présent dans le livre de José Ouin [7]. Après plusieurs lectures, je ne rentrais pas dans son code qui teste toutes les cases, pas seulement les cases initialement vides et utilise deux variables pour la grille, une fixe (la grille initiale) et une variable (la grille à compléter). Mon code ne contient pas une ligne du sien, j’ai préféré qu’il soit tout entier de mon cru.
J’ai compris grâce à lui le principe du backtracking à force de relectures : le grand serpent avance de case en case jusqu’à rencontrer une condition (ici une impossibilité) qui le fait reculer tant que l’impossibilité perdure ou le fasse sortir de la grille. Il recommence le va-et-vient tant qu’il peut ou jusqu’à terminer la grille.
2.1 La fonction casepos
Voici la fonction qui retourne la liste des chiffres que peut prendre la case de la ligne case[0] et de la colonne case[1] :
07: def casepos(case,sudoku):
11: chiffres = set(sudoku[case[0]])
12: chiffres |= {sudoku[i][case[1]] for i in range(9)}
13: cellule = case[0] // 3 , case[1] // 3
14: for i in range(3):
15: chiffres |= set(sudoku[cellule[0] * 3 + i][cellule[1] * 3:(cellule[1] + 1) * 3])
16: return list(set(range(1,10)) - chiffres)
L’ensemble chiffres contient à la ligne 11 les chiffres de la ligne de la case. L’opérateur tube | entre ensembles est la réunion, le OU inclusif, la ligne 12 lui ajoute la colonne qui contient la case, l’ensemble ajouté est créé en compréhension.
Voici un petit tableau qui récapitule les opérations sur les ensembles :
|
Opération logique |
ET |
OU inclusif |
OU exclusif |
|
|
Symbole pythonique |
& |
| |
^ |
- |
|
Symbole mathématique |
∩ |
∪ |
∆ |
∖ |
|
Opération ensembliste |
intersection |
réunion |
différence symétrique |
soustraction |
Les trois premiers opérateurs pythoniques ont pour effet d’agir bit à bit sur les écritures binaires des nombres entiers. Ainsi, 25&14 vaut 8 car 25=16+8+1 et 14=8+4+2.
La suite calcule le tuple qui contient les coordonnées de la cellule qui contient la case avec une simple division entière (euclidienne, comme à l’école). On ajoute alors à chiffres le contenu ensembliste de chaque tranche horizontale de la cellule.
Enfin, on retourne la liste des éléments qui ne sont pas dans chiffres, autrement dit, tous les chiffres non nuls possibles. Le 0 est exclu puisque set(range(1,10)) vaut {1,2,3,4,5,6,7,8,9}.
2.2 La résolution
casearemplir est le numéro de la case à remplir où le grand serpent se pose lors d’une étape, à la fois dans possibles et dans trous.
On initialise la liste possibles par une liste de len(trous) listes vides.
86: possibles = [[] for i in trous]
87: casearemplir = 0
Python comprend une syntaxe comme "123"*3 ou [1,2,3]*3, qui valent respectivement "123123123" et [1,2,3,1,2,3,1,2,3]. Cependant, si on avait initialisé possibles avec la forme plus élégante [[]*len(trous)], possibles aurait toujours contenu len(trous) fois la même liste parce que ce faisant, les len(trous) listes de possibles pointeraient toutes vers la même zone de mémoire. Ce n’est pas du tout ce qu’on souhaite.
Voici maintenant la partie délicate, le cœur de la résolution :
089: while casearemplir < len(trous):
090: possibles[casearemplir] = casepos(trous[casearemplir],sudoku)
091: try:
092: while not possibles[casearemplir]:
093: sudoku[trous[casearemplir][0]][trous[casearemplir][1]] = 0
094: casearemplir -= 1
095: except IndexError:
096: print("Le sudoku n’a pas de solution.")
097: exit(1)
098: sudoku[trous[casearemplir][0]][trous[casearemplir][1]] = possibles[casearemplir].pop()
099: casearemplir += 1
Si casearemplir vaut len(trous), c’est qu’on vient de remplir la dernière case vide lors du dernier passage dans la grande boucle while et la grille est alors résolue.
Sinon, casearemplir est inférieur à len(trous) et on complète d’abord, ligne 90, la liste des chiffres possibles de la case courante.
trous[casearemplir] est la paire de coordonnées [ligne,colonne] de la case à compléter numéro casearemplir, donc trous[casearemplir][0] en est le numéro de ligne et trous[casearemplir][1] le numéro de colonne. sudoku[trous[casearemplir][0]][trous[casearemplir][1]] contient alors la valeur de la case à compléter dans la variable sudoku. On la remet à 0 ligne 93 et on la complète ligne 98.
- Si elle est vide, le grand serpent se prépare à revenir sur ses pas : il réinitialise la case courante à 0 ligne 93 et recule d’une case à remplir. Il recommence tant que possibles[casearemplir] — c’est-à-dire la liste des chiffres possibles à la case courante — est vide, puisque not liste retourne True si la liste est vide et False sinon. Si on recule trop, on sort de la liste et une exception IndexError est levée, cela veut dire que la grille n’admet pas de solution.
- Si elle n’est pas vide, on remplit la case courante par la dernière valeur de la liste des chiffres possibles, valeur qui est ôtée de cette liste via la méthode pop, ce qui permet de ne jamais repasser par un état de la grille déjà rencontré puisqu’un chemin entamé est retiré de la liste des chemins possibles. On avance ensuite d’une case à compléter.
Le couple de méthodes append() et pop() sur une liste permet de l’utiliser comme une pile (d’assiettes).
Si on utilise append() et pop(0) (qui sort le premier élément et non le dernier), on a un tuyau ou un tube.
2.3 L’affichage de la solution
On affiche chaque ligne chiffre à chiffre en utilisant le paramètre nommé end de la fonction print, qui permet de continuer à écrire sur la même ligne s’il vaut la chaîne vide. Sa valeur par défaut est "\n". Le print() de la ligne 106 permet de passer à la ligne une fois chaque ligne du sudoku parcourue.
103: for l in sudoku:
104: for c in l:
105: print(c, end="")
106: print()
Il est possible de le faire en remplissant une chaîne de caractères :
103: for l in sudoku:
104: ch = ""
105: for c in l:
106: ch = ch + str(c)
107: print(ch)
C’est moins élégant, mais évite l’import en Python 2 (ou alors on désactive le saut à la ligne de Python 2 par print c,).
Voici le résultat :
$ time ./sudoku.py sudoku.txt
524913768
613758942
978246351
269531874
851467293
347892615
132675489
795384126
486129537
real 0m0.027s
user 0m0.024s
sys 0m0.000s
Conclusion
Le code initial ne contenait pas les tests puisqu’il a été écrit pour résoudre des grilles qui ont une solution. Il permettait, en modifiant seulement la fonction casepos, de résoudre des Sudokus de tailles ou de cellules de formes différentes (non nécessairement carrées). L’explication et la relecture du code m’ont obligé à le rendre plus clair, un peu mieux écrit et à enlever quelques redondances dans la résolution.
Kaa [8] est maintenant tout-terrain et il peut se risquer en dehors de la forêt. Il sait dorénavant résoudre une grille de Sudoku parmi les plus difficiles [9] en moins de cinq minutes (essayez à la main !) ; la voie est libre et il a tout le temps de croquer Mowgli sans craindre Shere-Khan.
Il peut aussi utiliser le backtracking pour résoudre d’autres problèmes, comme vérifier tous les points chauds de la forêt le plus rapidement possible [10], ou plus généralement, les parcours de graphes et d’arbres des vautours, traverser la plaine sans se faire écraser par les éléphants du colonel Hathi [11] pour aller faire courir un cavalier sur un jeu d’échecs avec le roi Louie [12].
Vous pouvez améliorer le code pour qu’il propose toutes les solutions au cas où elle n’est pas unique.
Pour ne plus craindre Bagheera non plus et résoudre les Sudokus difficiles en une fraction de seconde, Kaa peut s’intéresser à d’autres algorithmes de résolution : des algorithmes logiques, de programmation linéaire ou d’autres manières de coder le backtracking qui sont bien plus rapides que celle-ci.
Amusez-vous bien !
Références
[1] Il s’agit de la collection, empaquetée par les développeurs de Debian, de casse-tête fournie par S. G. Tatham sur son site : http://www.chiark.greenend.org.uk/~sgtatham/puzzles/. Les jeux sont jouables en Java et en JavaScript en ligne et téléchargeables (code compris).
[2] Une permutation est une bijection d’un ensemble dans lui-même ; ici on échange des chiffres de 1 à 9. Par exemple, ou (2 3 5 9 1 4 7 6 8) est la permutation qui envoie le 1 sur le 2, le 2 sur le 3, le 3 sur le 5 et ainsi de suite. Il y a 1×2×3×4×5×6×7×8×9=9!=362880 permutations différentes des neuf chiffres non nuls. Voir par exemple : http://www.les-mathematiques.net/d/c/a/node24.php.
[3] Page de documentation de Python 3 sur les exceptions : https://docs.python.org/3/library/exceptions.html.
[4] Colombo T., « Les expressions idiomatiques en Python », GNU/Linux Magazine n°173, Juillet/Août 2014, p. 52 à 61.
[5] Par exemple Audibert T. et Oussalah A., « Informatique Programmation et calcul scientifique en Python et Scilab », Ellipses, 2013, p. 423.
[6] Chazallet S., « Les bases du calcul scientifique avec NumPy », GNU/Linux Magazine hors-série n°73, Juillet/Août 2014, p. 8 à 21 notamment les p. 12 et 13, ou la fin de http://docs.scipy.org/doc/numpy/reference/arrays.indexing.html#basic-slicing mais c’est moins bien expliqué.
[7] Ouin J., « Algorithmique et calcul numérique », Ellipses, 2013, p. 29 à 42. Il écrit l’algorithme en pseudo-code, en Scilab puis en Python.
[8] Kaa est le serpent Python du « Livre de la jungle » de R. Kipling et du film de W. Disney. Mowgli est l’enfant de la forêt, Shere-Khan le tigre qui veut lui aussi manger Mowgli, Hathi est le chef des éléphants, Louie le roi des orangs-outangs et Bagheera la panthère noire protectrice.
[9] Page de Gordon R. sur les Sudokus minimums (avec 17 indices seulement, il n’est pas possible de faire moins) : http://units.maths.uwa.edu.au/~gordon/sudokumin.php.
[10] Il s’agit de celui du problème du voyageur de commerce qui veut parcourir un graphe en passant une seule fois par chaque sommet et en minimisant le coût ou en maximisant le gain : http://villemin.gerard.free.fr/LogForm/GrVoyage.htm ou https://interstices.info/jcms/c_37686/le-probleme-du-voyageur-de-commerce.
[11] C’est le jeu de la traversée de route en évitant les voitures, classique des jeux sur écran LCD : http://www.codeabbey.com/index/task_view/crossing-the-road.
[12] Trouver un trajet du cavalier qui lui fait parcourir chaque case de l’échiquier une seule fois (plus difficile s’il revient au point de départ) : http://zanotti.univ-tln.fr/algo/CAVALIER.html ou http://bayledes.free.fr/carres_magiques/Cavaliers.html. La résolution peut se faire sans backtracking si l’heuristique est bien choisie.
