la résolution du sudoku c'est un exemple trivial de programmation en prolog, voici un truc que j'avais fait vite fait (il faut un prolog avec solveur de contraintes sur les domaines finis, comme gnu prolog). Le code est optimisé pour énumérer le moins de variables possible parce que c'était le but de l'exercice, mais si on ne veut pas ces optimisations, c'est encore plus trivial.
En gros il suffit de dire à prolog : « voila une grille dont tels cases sont connues et telles autres inconnues. chaque ligne, colonne et bloc doit contenir les chiffres entre 1 et 9 une seule fois. Résouds la grille. »
Bon mais en fait c'est encore mieux, parce que ce n'est pas qu'un simple solveur : si il y a plusieurs solutions, on peut lui faire énumérer. Donc si on lui fait résoudre la grille vide, il énumère toutes les grilles de sudoku possibles. Comme le finite domain checking c'est super fort, trouver une solution, même à partir de la grille vide, est instantané.
Le code fait 200 lignes mais si on vire ce qui sert à rien il doit rester 15 lignes intéressantes (plus la définition de Rows, Cols et Blocks).
Ensuite effectivement pour générer une grille il suffit de choisir trois quatre nombres au pif (pour avoir du hasard), de demander a prolog une solution, puis de supprimer des nombres tant que la solution est unique.
/*************************************************************************/
/* Constraint Programming Project */
/* */
/* Name : sudoku.pl */
/* Title : Sudoku Solver */
/* Date : 02/10/2006 */
/* */
/* Enumerates all possible solutions for a given Sudoku grid. */
/*************************************************************************/
/*************************************************************************/
/* CONSTRAINTS */
/*************************************************************************/
/*
* sudoku_constraints/1
*
* Given a list of lists, applies some constraints to these lists. They
* must contain integers which are all differents and are in [|1,9|].
*/
sudoku_constraints([]).
sudoku_constraints([Head|Tail]) :-
fd_domain(Head,1,9),
fd_all_different(Head),
sudoku_constraints(Tail).
/*
* sudoku_redundant_constraints/1
*
* Given a list of lists, applies some more constraints to these lists.
* They must contain exactly one 1, one 2, ..., one 9.
*/
sudoku_redundant_constraints([]).
sudoku_redundant_constraints([Head|Tail]) :-
fd_exactly(1,Head,1),
fd_exactly(1,Head,2),
fd_exactly(1,Head,3),
fd_exactly(1,Head,4),
fd_exactly(1,Head,5),
fd_exactly(1,Head,6),
fd_exactly(1,Head,7),
fd_exactly(1,Head,8),
fd_exactly(1,Head,9),
sudoku_redundant_constraints(Tail).
/*************************************************************************/
/* LABELING */
/*************************************************************************/
/*
* get_greatest/3
*
* Given a list of finite domain variables, and an integer N, returns the
* maximum between N and the greatest domain size in the list.
*/
get_greatest([],N,N).
get_greatest([Head|Tail],N,M) :-
fd_size(Head,P),
(P > N -> get_greatest(Tail,P,M) ; get_greatest(Tail,N,M)).
/*
* get_var/3
*
* Given a list of finite domain variables, and a domain size N, returns
* the first variable of the list whose domain size is N.
*/
get_var([Head|Tail],N,A) :-
(fd_size(Head,N) -> A = Head ; get_var(Tail,N,A)).
/*
* sudoku_labeling/2
*
* Given a sudoku grid filled with finite domain variables, tries to label
* them while minimizing the number of enumerated variables. N is the
* number of enumerated variables.
*/
sudoku_labeling(Grid,N) :-
get_greatest(Grid,1,S),
(S =\= 1 -> /* If the greatest domain size is 1, then the grid is */
/* solved. */
get_var(Grid,S,A), /* We find the variable with the greatest domain, */
fd_labeling(A), /* hoping that its labeling will propagate enough */
/* to allow us to enumerate less variables */
sudoku_labeling(Grid,M),
N is M+1
; N is 0).
/*************************************************************************/
/* OUTPUT */
/*************************************************************************/
/*
* write_row/1
*
* write_row/1 is used by write_grid/1 to output a Sudoku grid.
*/
write_row([]) :-
write('|').
write_row([A1,A2,A3|Tail]) :-
write('|'), write(A1), write(A2), write(A3),
write_row(Tail).
/*
* write_grid/1
*
* Given a Sudoku grid by its list of rows, outputs it.
*/
write_grid([]) :-
write('+---+---+---+'), nl.
write_grid([Row1,Row2,Row3|Tail]) :-
write('+---+---+---+'), nl,
write_row(Row1), nl,
write_row(Row2), nl,
write_row(Row3), nl,
write_grid(Tail).
/*************************************************************************/
/* MAIN PREDICATE */
/*************************************************************************/
/*
* sudoku/1
*
* Given an unsolved Sudoku grid, applies necessary and redundant
* contraints to it, then tries to solve it while minimizing the number of
* enumerated variables. Finally prints the number of enumerated variables
* and the solution.
*/
sudoku(Grid) :-
Grid = [A11,A12,A13,A14,A15,A16,A17,A18,A19,
A21,A22,A23,A24,A25,A26,A27,A28,A29,
A31,A32,A33,A34,A35,A36,A37,A38,A39,
A41,A42,A43,A44,A45,A46,A47,A48,A49,
A51,A52,A53,A54,A55,A56,A57,A58,A59,
A61,A62,A63,A64,A65,A66,A67,A68,A69,
A71,A72,A73,A74,A75,A76,A77,A78,A79,
A81,A82,A83,A84,A85,A86,A87,A88,A89,
A91,A92,A93,A94,A95,A96,A97,A98,A99],
Row1 = [A11,A12,A13,A14,A15,A16,A17,A18,A19],
Row2 = [A21,A22,A23,A24,A25,A26,A27,A28,A29],
Row3 = [A31,A32,A33,A34,A35,A36,A37,A38,A39],
Row4 = [A41,A42,A43,A44,A45,A46,A47,A48,A49],
Row5 = [A51,A52,A53,A54,A55,A56,A57,A58,A59],
Row6 = [A61,A62,A63,A64,A65,A66,A67,A68,A69],
Row7 = [A71,A72,A73,A74,A75,A76,A77,A78,A79],
Row8 = [A81,A82,A83,A84,A85,A86,A87,A88,A89],
Row9 = [A91,A92,A93,A94,A95,A96,A97,A98,A99],
Rows = [Row1,Row2,Row3,Row4,Row5,Row6,Row7,Row8,Row9],
Col1 = [A11,A21,A31,A41,A51,A61,A71,A81,A91],
Col2 = [A12,A22,A32,A42,A52,A62,A72,A82,A92],
Col3 = [A13,A23,A33,A43,A53,A63,A73,A83,A93],
Col4 = [A14,A24,A34,A44,A54,A64,A74,A84,A94],
Col5 = [A15,A25,A35,A45,A55,A65,A75,A85,A95],
Col6 = [A16,A26,A36,A46,A56,A66,A76,A86,A96],
Col7 = [A17,A27,A37,A47,A57,A67,A77,A87,A97],
Col8 = [A18,A28,A38,A48,A58,A68,A78,A88,A98],
Col9 = [A19,A29,A39,A49,A59,A69,A79,A89,A99],
Cols = [Col1,Col2,Col3,Col4,Col5,Col6,Col7,Col8,Col9],
Block1 = [A11,A12,A13,A21,A22,A23,A31,A32,A33],
Block2 = [A14,A15,A16,A24,A25,A26,A34,A35,A36],
Block3 = [A17,A18,A19,A27,A28,A29,A37,A38,A39],
Block4 = [A41,A42,A43,A51,A52,A53,A61,A62,A63],
Block5 = [A44,A45,A46,A54,A55,A56,A64,A65,A66],
Block6 = [A47,A48,A49,A57,A58,A59,A67,A68,A69],
Block7 = [A71,A72,A73,A81,A82,A83,A91,A92,A93],
Block8 = [A74,A75,A76,A84,A85,A86,A94,A95,A96],
Block9 = [A77,A78,A79,A87,A88,A89,A97,A98,A99],
Blocks = [Block1,Block2,Block3,Block4,Block5,Block6,Block7,Block8,Block9],
sudoku_constraints(Rows), /* These constraints mean that each row, */
sudoku_constraints(Cols), /* each column and each block, contain */
sudoku_constraints(Blocks), /* integers all different between 1 and 9. */
sudoku_redundant_constraints(Rows), /* These constraints mean that */
sudoku_redundant_constraints(Cols), /* each row, column and block, */
sudoku_redundant_constraints(Blocks), /* contain exactly 1 of each */
/* integer between 1 and 9 */
sudoku_labeling(Grid,N), /* This solves the grid. */
nl, /* Then we */
write('Number of enumerated variables: '),write(N), nl, /* print the */
write('------------------------------------'), nl, /* solved grid */
write('Solution:'), nl,
write_grid(Rows).
) mais je ne vois a priori pas de raison que cet algorithme ne fonctionne pas...
