Re: Speed Up Sudoku Solver


"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



.