Discussion :

[Shaitan00]

J'ai écrit un programme pour résoudre Sudoku 4x4 dans SWI-Prolog en utilisant le module clp/bounds pour définir mes limites numérique sur les variables :

Code :

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

1
2
3
 
  % Define Bounds for Cell Values
  Cells in 1..4,

Le problème c'est que je viens de me faire dire que je ne dois utiliser aucun module pour résoudre le problème. Alors j'ai écrit le predicat "possibleValue" pour s'assurer que les valeurs sont NUMERIQUES et entre 1-4 (1,2,3,4) comme vous pouvez voir plus tard. Je pensais que cela aurait marché mais maintenant mon programme roule à 45% CPU et ça fait 40 minutes sans aucune réponse - ce qui n'est pas normal car l'autre version (avec bounds) ne prenait même pas une seconde.

Voyez-vous ce que je fais d'incorrect ? N'oubliez pas je n'ai pas le droit d'utiliser des modules et probablement pas des prédicats pré-faits. Il doit y avoir une façon plus efficace pour s'assurer que les valeurs de Cells soient NUMERIQUES et entre 1-4 (1,2,3,4) ?

Si vous pouvez me donner un coup-de-main ce serait très apprécié...
Merci...

Code complet :

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
%%% Sudoku Puzzle Solution %%%
solve_sudoku(L):-
 
  % Declare the 4x4 Sudoku Puzzle Board as Cells
  % where Rows are defined by [A-D] and Columns by [1-4]
  Cells =
  [
      A1,A2,A3,A4,
      B1,B2,B3,B4,
      C1,C2,C3,C4,
      D1,D2,D3,D4
  ],
 
  % Define Bounds for Cell Values
  possibleValue(A1),
  possibleValue(A2),
  possibleValue(A3),
  possibleValue(A4),
  possibleValue(B1),
  possibleValue(B2),
  possibleValue(B3),
  possibleValue(B4),
  possibleValue(C1),
  possibleValue(C2),
  possibleValue(C3),
  possibleValue(C4),
  possibleValue(D1),
  possibleValue(D2),
  possibleValue(D3),
  possibleValue(D4),
 
  % Ensure all Rows have distinct values
  alldifferent([A1,A2,A3,A4]),
  alldifferent([B1,B2,B3,B4]),
  alldifferent([C1,C2,C3,C4]),
  alldifferent([D1,D2,D3,D4]),
 
  % Ensure all Columns have distinct values
  alldifferent([A1,B1,C1,D1]),
  alldifferent([A2,B2,C2,D2]),
  alldifferent([A3,B3,C3,D3]),
  alldifferent([A4,B4,C4,D4]),
 
  % Ensure all Sub-matrices have distinct values
  alldifferent([A1,A2,B1,B2]),
  alldifferent([A3,A4,B3,B4]),
  alldifferent([C1,C2,D1,D2]),
  alldifferent([C3,C4,D3,D4]),
 
  % Initialize Puzzle Board
  flatten(L, Cells).
 
 
%%% Sudoku Possible Values
%% Ensure that the values are either 1-2-3-4
possibleValue(1).
possibleValue(2).
possibleValue(3).
possibleValue(4).
 
 
%%% Sudoku Distinct Cell Validation %%%
%% Ensure that values passed in are all different
alldifferent([]).
alldifferent([X|Xs]) :-
        different(Xs,X),
        alldifferent(Xs).
 
different([],_).
different([Y|Ys],X) :-
        X \= Y,
        different(Ys,X).
 
 
%%% Sudoku Predicate %%%
go:- L = [ [_,4,2,_], [_,2,1,_], [4,_,_,2], [2,_,_,1] ], solve_sudoku(L).

[Trap D]

Je pense que tu dois changer de conception pour la résolution du Sudoku. Tu es trop orientée gestion de contraintes, mais comme tu n'as pas le droit d'utiliser la bibliothèque ...
Tu essaies toutes les valeurs possibles 1 2 3 4 pour une case, ce qui est absurde, puisque tu sais déjà par exemple que, si je prends ta grille [ [_,4,2,_], [_,2,1,_], [4,_,_,2], [2,_,_,1] ], la première case est soit 1 soit 3.
A mon avis cherche de ce côté.

[Shaitan00]

Serieux - je comprends totalement se que tu veut dire mais j'ai absolument auqune idee comment programmer quelque chose comme ca dans Prolog - j'aurait tu besoin de re-ecrier mon program au complet? J'y pense mais j'ai rien qui me vient en tete pour resoudre le problem de cette facon.

Il a tu une possibiliter de definier A2=4 (par example) au debut pour reduire la recherche? Comme ca les variable dans Cells (quelque'uns) peux-etre defini d'avance? Ou oublie Cells au complet et passe L directement dans alldifferent? (mais j'ai quand meme besoin de definire que les _ peuve extre des chiffre de 1-4...)... Comme tu voit - je suis un peut perdu...

Mais je veux une solution flexbile aussi pour different 4x4 (si possible - peut-etre pas).
Peut-tu donner un example? Je suis perdu in peut avec cette question.
Merci...

[Trap D]

Immenses excuses de ma part, je viens de regarder ton code, il fonctionne très bien et donne la solution instantanément !!!
Simplement, l'initialisation des variables est très mal placées : déplace le flatten(L, Cells), juste après la déclaration de Cells, et tu verras

[Shaitan00]

Parfait - donc faire le flatten au debut vas associer A2=4, A3=2, etc... qui va reduire l'espace de recherche - je comprends (merci beaucoup).

Une derniere petite question - il as tu une meilleure facon d'implimenter "possibleValue"? Quelque chose de plus beaux? Ou est-ce-que c'est une facon generalment utilier?

Mon but c'est pour me proteger d'un cas comme:
go:- L = [ [_,X,Y,_], [_,2,1,_], [4,_,_,2], [2,_,_,1] ], solve_sudoku(L).

Dans ce case A2=X et A3=Y (qui son't des variables, pas des numero) mais mon programme marche quand meme - je voulait essayer d'introduire "number(X)" avec une version optimiser de "possibleValue(X)" ou quelque chose comment ca - quand pense tu?

Quelque chose comme:

Code :

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

1
2
3
4
5
6
 
possibleValue(X):-number(X), valid(X).
valid(1).
valid(2).
valid(3).
valid(4).

Mais 1- ca marche pas et 2- j'essaye de la faire dand une linge...
Bonne idee?

[Trap D]

Tu peux implémenter possible value en disant

Code :

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

1
2
possibleValue(I) :-
  between(1,4,I).

A mon avis, pas la peine d'utiliser number(X) dans ce cas.

[Shaitan00]

J'aurais pensé que "between" aurait confirmé que la valeur passée serait numérique - et donc utiliser "number(I)" n'était pas nécessaire.

Mais j'ai testé le suivant :

Code :

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

  go:- L = [ [_,a,2,_], [_,2,1,_], [4,_,_,2], [2,_,_,1] ], solve_sudoku(L).

Et cela a causé une erreur :

ERROR: between/3: Type error: `integer' expected, found `a'
Exception: (10) between(1, 4, a) ?

J'ai besoin de garder contre cette situation ...
Alors j'ai essayé le suivant :

Code :

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

possibleValue(I) :- number(I),between(1,4,I).

Mais cela retourne "No" - "number(I)" marche pas...
Aurais-tu des idées ?

Merci...

[Trap D]

Tu peux faire tes cas de possiblevalue comme ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
% l'argument est un nombre compris entre 1 et 4
possibleValue(I) :- number(I), !, between(1,4,I).
 
% l'argument est une variable non instanciée, 
% elle sera unifiée avec un nombre compris entre 1 et 4
possibleValue(I) :- var(I), !, between(1,4,I).
 
% dans tous les autres cas , c'est une erreur
possibleValue(I) :- 
	format('Attention ~w n''est pas un nombre ni une variable libre ~n', [I]),
	abort.