Re: Speed Up Sudoku Solver


"Andrew" <someone@xxxxxxxxxxxxx> wrote in message
news:5nk3g.11237$tc.5541@xxxxxxxxxxxxxxxxxxxxxxxxxxxx

"Andrew" <someone@xxxxxxxxxxxxx> wrote in message
news:uCz2g.121319$8Q3.73387@xxxxxxxxxxxxxxxxxxxxxxxxxxxx
You were right.
Geoffs response did improve the performance slightly, but there is still
an overhead.

I thought that if I kept a list of available choces for a row (column/box
etc) I could cut out some of the overhead.

For this I have made the choices predicate (in this case List1 will
always be [1,2,3,4,5,6,7,8,9])

%Deletes all elements of List2 from List1 and puts the result in the List
Choices
choices(List1,List2,Choices):-
list_to_set(List1, Set1),
list_to_set(List2, Set2),
subtract(Set1, Set2, Choices).

However, I am not sure how to implement it in the program so that Prolog
only backtracks through the numbers in the Choices list rather than all
possible numbers.

/Andrew

Although I have it working using CLP, I am still interested in the
original method.
I am trying to speed it up by restricting the choices (as above) so I
have written the following 2 predicates.

numeric(X,List) :-
choices([1,2,3,4,5,6,7,8,9],List,Choices),
member(X, Choices).

%Deletes all elements of List2 from List1 and puts the result in the List
Choices
choices(List1,List2,Choices):-
list_to_set(List1, Set1),
list_to_set(List2, Set2),
subtract(Set1, Set2, Choices).

These work fine in the test environment
e.g. numeric(X,[_,2,3,4,5,_,7,8,9]).
returns X=1, X=6, No.

However, in my main program X seems to get instantiated early when I do
Row1=[A1,A2,A3,A4,A5,A6,A7,A8,A9],
numeric(A1,Row1),

(Row 1 looks like this - 0 9 3 4 5 8 2 7 0 )

what happens is that X=9 BEFORE member(X, Choices). is called!
I don't understand how this could happen.

/Andrew




OK. I understand now, but I don't know how to fix it.
During choices/3 list_to_set(List2, Set2) not only creates a set but also
instantiates everything in List2.
List2 from choices/3 corresponds to List in numeric/2, which contains X.
Since list has now been instantiated, X is now instantiated.

How can achieve this without instantiating X?

%This should output the following
%A=4, A=8, No
%B=4, B=8, No
go:-
numeric(A,[1,2,3,A,5,6,7,B,9]),
numeric(B,[1,2,3,A,5,6,7,B,9]).

numeric(X,List) :-
choices([1,2,3,4,5,6,7,8,9],List,Choices),
member(X, Choices).

%Deletes all elements of List2 from List1 and puts the result in the List
Choices
choices(List1,List2,Choices):-
list_to_set(List1, Set1),
list_to_set(List2, Set2),
subtract(Set1, Set2, Choices).


.