Discussion :

[casperfr]

Bonjour à tous,

dans le cadre d'un projet en python, je dois intégré une résolution d'un problème (sudoku) en swi-prolog pour remplir un tableau,
la création du fichier prolog pour résoudre un sudoku est suffisamment documenté pour n'avoir aucun problème ,
j'ai d’ailleurs essayé de créé des grille de sudoku automatiquement par prolog mais je ne suis arrivé a rien, je début vraiment en prolog et je ne maitrise vraiment pas bien

voila mon problème, lors de la création des sudolu sous python, je créé une liste et j'utilise la bibliothèque py-swi pour résoudre cette liste mais elle ne fonctionne que pour python2 pour python3 je démarre l'interpréteur prolog, j'execute mon fichier et je récupère l'affichage, cela fonctionne relativement bien dans les deux cas, mais dans certain le temps pour récupéré la grille est absolument gigantesque (jusqu’à plusieurs jour) après avoir cherché d’où venais le problème je me suis aperçus qu'il n'y avais en faite aucun problème mais le faite que prolog essai de résoudre toutes les possibilité de la grille de sudoku, et dans le cas ou la grille possède que très peut de chiffre connu, il y a tellement d'autre possibilité que les résultats ce fond attendre,
je précise que dans mon cas, la taille du sudoku est paramétrable d'une grille de 4x4 jusqu’à 25x25 ce qui rend le nombre de possibilité très importante,

j'aimerais savoir si dans le fonctionnement de la résolution d'une grille de sudoku, il existe un moyen pour forcer prolog a ne résoudre que la première possibilité et non les autres, puisque quand je récupère l'information, je ne récupère que la première donc même s'il y a d'autre possibilité elles ne seront pas récupéré, donc inutile

merci pour votre aide ou vos information qui permettrons de m’orienter,

merci a tous,
casperfr

[Trap D]

Bonjour

Utilisez-vous la bibliothèque clpfd ?
Une possibilité est l'utilisation de once/1, qui s'arrête une fois que le but à réussi.

[casperfr]

Bonjour,

Merci pour votre suggestion,
dans un premier temps, comme j'utilise la bibliothèque swi-prolog pour python, je me suis dis, je vais évité de charger des bibliothèque, je n'utilisais donc pas all_different ou les bornages de domaine avec ins, dans ma deuxième méthode d'intégration comme j'utilisais le chargement de swi-prolog et l'execusion d'un fichier pl, cela n'avait donc plus d’intérêt de ne pas utilisé les bibliothèque j'ai donc utilisé bounds et all_distinct j'ai aussi utilisé clpfd mais dans mon première essais, quand je faisait un affichage de la grille de sudoku il ne m'affichait que la première ligne résolu et pas la grille au complet
mais je n'ai pas essayé d'utilisé once,

voila par exemple l'un de mes essai pour résoudre une grille de 16x16, (j'ai essayé de faire vraiment au plus simple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
:- use_module(library(clpfd)).
 
sudoku(Lignes) :-  
  append(Lignes, Vs), Vs ins 1..16,
  maplist(all_distinct, Lignes),
  transpose(Lignes, Colonnes),     
  maplist(all_distinct, Colonnes),     
  Lignes = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P],     
  blocks(A, B, C, D), blocks(E, F, G, H), blocks(I, J, K, L), blocks(M, N, O, P),     
  maplist(label, Lignes).      
 
blocks([], [], [], []).       
blocks([A,B,C,D|Bs1], [E,F,G,H|Bs2], [I,J,K,L|Bs3], [M,N,O,P|Bs4]) :-     
  all_distinct([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]),      
  blocks(Bs1, Bs2, Bs3, Bs4).

mon entré étant du type list :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sudoku([[3, 8, 9, 12, 14, 16, 1, 5, 4, 15, 13, 11, 10, 6, 2, 7],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [7, 5, 13, 16, 15, 1, 8, 4, 11, 14, 10, 12, 9, 3, 6, 2],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [2, 14, 10, 15, 8, 12, 13, 11, 7, 9, 3, 5, 16, 4, 1, 6],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [13, 12, 1, 6, 10, 11, 5, 9, 2, 16, 4, 3, 8, 15, 7, 14],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _]]).

Merci encore pour votre aide

[Trap D]

Bonjour

Vous avez fait une petite erreur au labeling, il faut "labeller" l'ensemble des lignes, et non pas lignes par lignes.
J'ai modifié votre code et ajouter une option au labeling pour accélérer le processus :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
:- use_module(library(clpfd)).
 
 
 
sudoku(Lignes) :-
  append(Lignes, Vs), Vs ins 1..16,
  maplist(all_distinct, Lignes),
  transpose(Lignes, Colonnes),
  maplist(all_distinct, Colonnes),
  Lignes = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P],
  blocks(A, B, C, D), blocks(E, F, G, H), blocks(I, J, K, L), blocks(M, N, O, P),
  flatten(Lignes, Flatten_Lignes),
  labeling([ff],Flatten_Lignes),
  maplist(writeln, Lignes).
 
blocks([], [], [], []).
blocks([A,B,C,D|Bs1], [E,F,G,H|Bs2], [I,J,K,L|Bs3], [M,N,O,P|Bs4]) :-
  all_distinct([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P]),
  blocks(Bs1, Bs2, Bs3, Bs4).
 
 
:- time(sudoku([[3, 8, 9, 12, 14, 16, 1, 5, 4, 15, 13, 11, 10, 6, 2, 7],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [7, 5, 13, 16, 15, 1, 8, 4, 11, 14, 10, 12, 9, 3, 6, 2],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [2, 14, 10, 15, 8, 12, 13, 11, 7, 9, 3, 5, 16, 4, 1, 6],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [13, 12, 1, 6, 10, 11, 5, 9, 2, 16, 4, 3, 8, 15, 7, 14],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _],
                         [_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _]])).

Le resultat :

3 ?- [3,8,9,12,14,16,1,5,4,15,13,11,10,6,2,7]
[1,7,6,2,4,8,11,10,12,3,14,9,5,13,15,16]
[14,4,5,10,7,9,15,13,1,2,6,16,3,8,11,12]
[15,13,16,11,3,2,6,12,5,8,7,10,1,9,14,4]
[7,5,13,16,15,1,8,4,11,14,10,12,9,3,6,2]
[6,2,12,1,11,5,9,3,13,4,8,7,14,10,16,15]
[9,10,14,3,13,7,12,2,15,5,16,6,4,1,8,11]
[8,11,15,4,16,10,14,6,3,1,9,2,12,7,13,5]
[2,14,10,15,8,12,13,11,7,9,3,5,16,4,1,6]
[4,1,3,9,5,6,16,15,14,11,12,13,7,2,10,8]
[5,6,8,13,1,3,2,7,16,10,15,4,11,14,12,9]
[12,16,11,7,9,4,10,14,8,6,2,1,15,5,3,13]
[13,12,1,6,10,11,5,9,2,16,4,3,8,15,7,14]
[16,3,2,5,6,14,4,8,10,7,11,15,13,12,9,1]
[10,9,4,8,12,15,7,16,6,13,1,14,2,11,5,3]
[11,15,7,14,2,13,3,1,9,12,5,8,6,16,4,10]
% 18,734,728 inferences, 1.625 CPU in 1.667 seconds (97% CPU, 11529063 Lips)
% c:/users/utilisateur/documents/prolog/dvp/sud_py compiled 1.63 sec, 0 clauses

[casperfr]

Bonjour,

c'est vraiment parfait, le résultat est considérablement plus rapide que ce que je faisais,

il me reste juste une toute petite chose,

dans prolog, une fois le résultat obtenus, il me marque true. jusque la normal, mais je dois appuyé sur entré pour revenir aux ligne de commande, sur prolog sa ne pose aucun problème,
mais dans le cas de l'usage dans python via la bibliotèque pyswip comme je ne peux pas envoyé le retour a la ligne une fois le résultat obtenue, il me bloque le programme,
auriez vous une solution pour qu'une fois le true. affiché j'arrive directement sur la ligne de commande

merci encore pour vos précieux conseil,

[casperfr]

en faite j'ai trouvé, c'était tout simple
il fallait simplement finir par un !

merci beaucoup pour votre aide et votre compétence

[Trap D]

Petite remarque au sujet du cut.
Ici il ne semble pas poser de problèmes puisque vous avez la solution à votre problème, mais en règle générale, il ne faut jamais utiliser un cut dans un code utilisant la bibliothèque clpfd, il casse le processus de calcul de la bibliothèque en supprimant les choix à partir de sa position.