TP Logique : Sudoku
Cette fois nous allons nous attaquer à un jeu, un classique des TP Prolog : le fameux Sudoku. Vous trouverez sans doute des implémentations sur internet, mais elles ne sont pas détaillées et en général elles ne vous aideront pas à comprendre ce qui se passe. Je vous propose donc de suivre ce TP étape par étape, et la résolution des Sudoku par Prolog n'aura plus aucun secret pour vous.

Table des Matières

Introduction

Pour ceux qui ne connaissent pas le Sudoku, il s'agit d'un puzzle consistant à remplir une grille avec des chiffres. Les chiffres ne peuvent cependant pas être choisis au hasard, il faut respecter certaines règles :
Nous allons travailler avec les Sudoku sous leur forme la plus classique : une grille carrée de 9 cases de côté. Chaque ligne, colonne ou carré contenant donc les chiffres de 1 à 9. Il en existe des version plus simple, comme avec une grille de taille 4. Il existe des versions plus compliquées, avec une grille de taille 16 ou un cube de 9 voire 16 cases de côté ! Si vous avez du temps à perdre (c'est-à-dire après avoir fini le TP), essayez ksudoku. En attendant, voici une définition de grille sudoku en Prolog, utilisant une liste de listes :
grille([[_,_,_,_,_,_,_,_,_], [_,_,_,_,_,3,_,8,5], [_,_,1,_,2,_,_,_,_], [_,_,_,5,_,7,_,_,_], [_,_,4,_,_,_,1,_,_], [_,9,_,_,_,_,_,_,_], [5,_,_,_,_,_,_,7,3], [_,_,2,_,1,_,_,_,_], [_,_,_,_,4,_,_,_,9]]).
Si vous essayez de visualiser cette grille dans l'interpréteur Prolog avec le but
grille(L).
, vous n'aurez pas un affichage lisible. Ça ne sera pas pratique pour vérifier si votre programme marche, ou pour avoir la solution tout simplement.
Définissez le prédicat
printline/1
qui affiche une ligne de grille Sudoku, représentée par une liste de nombres. Nous pouvons utiliser le prédicat
integer/1
pour déterminer si un élément est un nombre ou une variable non instanciée, let les prédicats
write/1
et
writeln/1
pour l'affichage.
Exemple
?- printline([_,_,_,_,_,3,_,8,5]). | | | | | |3| |8|5| true.
Définissez le prédicat
print/1
qui affiche une grille Sudoku complète.
Exemple
?- grille(L), print(L). | | | | | | | | | | | | | | | |3| |8|5| | | |1| |2| | | | | | | | |5| |7| | | | | | |4| | | |1| | | | |9| | | | | | | | |5| | | | | | |7|3| | | |2| |1| | | | | | | | | |4| | | |9| L = [[_G56040, _G56043, _G56046, _G56049, _G56052, _G56055, _G56058, _G56061|...], [_G56070, _G56073, _G56076, _G56079, _G56082, 3, _G56088|...], [_G56100, _G56103, 1, _G56109, 2, _G56115|...], [_G56130, _G56133, _G56136, 5, _G56142|...], [_G56160, _G56163, 4, _G56169|...], [_G56190, 9, _G56196|...], [5, _G56223|...], [_G56250|...], [...|...]].

Vérifications de la structure

Pour résoudre notre Sudoku, il faut tout d'abord vérifier que le format de la table est correct.
Définissez le prédicat
bonnelongueur/2
qui vérifie qu'une liste a bien une longueur donnée.
Exemple
?- bonnelongueur([_,_,_,_,_,3,_,8,5], 9). true.
Définissez le prédicat
bonnetaille/2
qui vérifie que chaque ligne d'une table a bien la bonne dimension.
Exemple
?- bonnetaille([[1,2,3],[4,5,6]], 3). true.

Vérifications du domaine

Nous devons maintenant contraindre les valeurs de chaque case à être bien entre 1 et 9. Le problème a l'air simple au premier abord, il suffirait d'écrire quelque chose du genre :
verifier([]). verifier([X | L]) :- X >= 1, X =< 9, verifier(L).
On peut vérifier que lorsque l'on donne une liste de nombres, ce prédicat vérifie bien si tous les nombres de la liste donnée sont bien entre 1 et 9 :
?- verifier([1,2,3]). true. ?- verifier([1,42,3]). false.
Le problème que nous allons rencontrer est que nous cherchons à trouver des nombres manquants, donc tous les éléments de la liste ne seront pas instanciés. Dans ce cas si nous essayons quelque chose de ce genre, nous aurons un souci :
[debug] ?- verifier([1,X,3]). ERROR: >=/2: Arguments are not sufficiently instantiated Exception: (8) _G56315>=1 ? abort % Execution Aborted
Ce message barbare nous explique que le prédicat
>=
a besoin de paramètres instanciés. En effet : comment peut-on comparer deux valeurs si il nous en manque une ? Le problème est que Prolog ne sait pas définit les valeur possibles pour la variable. Quand il va chercher à unifier et donc retourner une valeur pour
X
, il ne saura pas comment les choisir. Nous aurions voulu que Prolog nous propose les solutions
X=1
,
X=2
, …,
X=9
.
La solution est la librairie
clpfd
(Constraint Logic Programming over Finite Domains), qui permet de manipuler des domaines finis. Nous chargerons cette librairie en ajoutant cette ligne à notre fichier .pl :
?- :- use_module(library(clpfd)).
Grâce à cette librairie, nous pouvons à la fois vérifier le domaine d'une valeur et spécifier le domaine d'une variable.
?- 4 in 1..9. true. ?- 42 in 1..9. false. ?- X in 1..9. X in 1..9. ?- [1,2,3,4] ins 1..9. true. ?- [1,2,3,4,42] ins 1..9. false. ?- [1,2,3,X,3] ins 1..9. X in 1..9. ?- [1,2,3,X,42] ins 1..9. false.
La librairie
clpfd
permet de faire des manipulations sur ces domaines. Dans notre cas nous souhaitons aurons besoin de vérifier que des éléments d'une liste sont tous différents. C'est le rôle du prédicat
all_distinct/1
.
?- all_distinct([1,2,3,4]). true. ?- all_distinct([2,2,3,4]). false.
Notre grille de Sudoku est une liste de lignes, chaque ligne étant une liste de nombres. Définissez le prédicat
verifie/1
qui prend une grille en paramètre et vérifie que chaque élément de chaque ligne est compris entre 1 et 9 et distinct des autres.
Exemple
?- verifie([[1,2,3,4], [5,6,7,8]]). true. ?- verifie([[2,2,3,4], [5,6,7,8]]). false. ?- verifie([[10,2,3,4], [5,6,7,8]]). false.

Vérifications des colonnes

Les lignes étaient faciles à vérifier car les données étaient disposées de manière adéquate. Pour vérifier les colonnes nous aurons besoin de transposer la matrice. Nous allons procéder en deux étapes. Je vous conseille de sortir une feuille de papier pour bien comprendre ce qu'il faut faire. N'ayez pas honte, moi-même je l'ai fait.
Écrivez le prédicat
eclate/3
qui prend en paramètre une liste
L
et une liste de liste
L'
, et qui ajoute chaque élément de la
L
aux listes de
L'
.
Exemple 1
?- eclate([1,2,3], [[4,7],[5,8],[6,9]], L). L = [[1, 4, 7], [2, 5, 8], [3, 6, 9]].
Exemple 2
?- eclate([7,8,9], [], L). L = [[7], [8], [9]].
Écrivez le prédicat
transp/2
qui prend en paramètre une matrice sous forme de liste de listes et retourne sa transposée.
Exemple
?- transp([[1,2,3],[4,5,6],[7,8,9]], L). L = [[1, 4, 7], [2, 5, 8], [3, 6, 9]].

Vérifications des carrés

La dernière vérification qu'il nous reste à faire concerne les carrés. La grille de Sudoku de taille 9 contient 9 carrés de taille 3, illustrés ci-dessous. Par exemple
[A1,B1,C1,A2,B2,C2,A3,B3,C3]
est un carré. Nous allons devoir créer une liste des 9 carrés à partir de la liste des lignes. Nous procéderons de nouveau en deux temps.
A1B1C1D1E1F1G1H1I1
A2B2C2D2E2F2G2H2I2
A3B3C3D3E3F3G3H3I3
A4B4C4D4E4F4G4H4I4
A5B5C5D5E5F5G5H5I5
A6B6C6D6E6F6G6H6I6
A7B7C7D7E7F7G7H7I7
A8B8C8D8E8F8G8H8I8
A9B9C9D9E9F9G9H9I9
Écrivez le prédicat
decoupe/4
qui prend en paramètre trois lignes, et qui retourne une liste de carrés. chacun des carrés contiendra 3 éléments successifs de chacune des 3 lignes.
Exemple
?- decoupe([1,2,3,4,5,6],[10,11,12,13,14,15],[19,20,21,22,23,24],L). L = [[1, 2, 3, 10, 11, 12, 19, 20, 21], [4, 5, 6, 13, 14, 15, 22, 23, 24]].
Écrivez le prédicat
carres/2
qui prend en paramètre une matrice sous forme de liste de listes et retourne la liste de ses carrés.
Exemple
?- carres([[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18]], L). L = [[1, 2, 3, 7, 8, 9, 13, 14, 15], [4, 5, 6, 10, 11, 12, 16, 17, 18]].

Solution

Nous avons maintenant tout ce dont nous avons besoin pour résoudre un sudoku.
Écrivez le prédicat
solution/1
qui prend en paramètre une grille de Sudoku, sous forme de liste de liste dont certains éléments ne sont pas instanciés, et qui va unifier toutes ces variables en respectant les contraintes définies par les règles du jeu :
  • Toutes les lignes sont de longueur 9.
  • Toutes les colonnes sont de longueur 9.
  • Chaque ligne contient des valeurs de 1 à 9 différentes.
  • Chaque colonne contient des valeurs de 1 à 9 différentes.
  • Chaque carré contient des valeurs de 1 à 9 différentes.
Vous pouvez vérifier que votre algorithme fonctionne avec ce but :
grille(L), solution(L), print(L).

Variantes

Si vous obtenez la bonne réponse : félicitations, vous avez gagné le droit de vous amuser un peu. Les questions suivantes sont en bonus. Je vous propose d'implémenter ces variantes :
Crossdoku : ajout de la contrainte que les deux diagonales doivent avoir des valeurs différentes.
Minidoku : le sudoku de taille 4.
grillehex([[2,_,_,3], [_,_,2,_], [_,4,1,_], [1,_,_,_]]).
Maxidoku : le sudoku de taille 16.
grillehex([[11,2,_,7,_,_,_,15,6,14,_,_,_,3,_,13], [_,_,_,9,11,_,2,_,_,_,_,_,15,1,_,6], [_,10,_,12,_,_,7,_,4,_,8,_,_,_,14,_], [_,8,_,3,_,_,1,_,_,_,15,12,10,_,4,2], [_,_,14,_,_,_,_,_,1,6,10,_,_,_,3,_], [3,_,_,_,_,_,_,_,_,4,_,15,8,_,6,11], [_,_,_,13,2,_,_,_,_,11,_,_,7,4,_,_], [_,11,8,4,0,_,_,13,7,_,9,3,14,_,_,_], [_,_,_,15,3,7,_,4,5,_,_,9,0,13,12,_], [_,_,12,8,_,_,10,_,_,_,_,11,4,_,_,_], [4,9,_,5,14,_,13,_,_,_,_,_,_,_,_,10], [_,13,_,_,_,6,12,1,_,_,_,_,_,7,_,_], [9,1,_,14,7,4,_,_,_,15,_,_,3,_,13,_], [_,3,_,_,_,9,_,2,_,1,_,_,5,_,0,_], [15,_,4,11,_,_,_,_,_,3,_,13,1,_,_,_], [5,_,13,_,_,_,15,14,9,_,_,_,2,_,11,4]]).
3Ddku : le sudoku 3D. Voir ksudoku. Commencez par un cube de taille 4. :)