Re: Speed Up Sudoku Solver


Andrew wrote:
On Mon, 17 Apr 2006 13:47:20 -0700, Geoffrey Summerhayes wrote:

Test as soon as possible. Suppose the first line contains X and Y,
the code generates all variables -> 1,1,...1,1 on it's first pass,
which fails, now it generates 1,1,...,1,2 which will still fail
because X and Y haven't changed. If you move the first line test
right after generating it, you get 1,1 and nothing else then 1,2 etc.
before going on to the rest.

OTOH, the solver I cobbled together doesn't check for uniqueness,
per se, I wrote a permute/2 that takes a list and returns a permutation
so I can write:

possibles([1,2,3,4,5,6,7,8,9]).

horizontals([]).
horizontals([H|T]):-possibles(X),permute(X,H),horizontals(T).
...
sudoku(P) :- horizontals(P),boxes(P),verticals(P).
...
sudoku([[A1,A2,A3,A4,A5,A6,A7,A8,A9],
[B1,...]...]]),
...

---

I didn't quite understand what you meant in your first paragraph.
the code generates all variables -> 1,1,...1,1 on it's first pass,
Shouldn't that be -> 1,1,...9,9?
Although, if not, it might explain the confusing trace with lots of 1,1.
Could you elaborate for me please. I'm only just getting into Prolog.

Just follow your code, first you bind what you can. Let's say A1,A2,B3,
and C4 are left as variables. First pass through the my_number section
will give (A1=1,A2=1,B3=1,C4=1)

Then comes the unique([A1,A2...])-> fails,backtracks to my_number(C4)
and we get (A1=1,A2=1,B3=1,C4=2) then (A1=1,A2=1,B3=1,C4=3), etc.
if you move unique([A1,A2...]). to just under my_number(A9) you'll
get (A1=1,A2=1,B3(free),C4(free)) then (A1=1,A2=2,B3(free),C4(free))
before reaching my_number(B3).

How does your predicate permute/2 actually work?
Are you passing the possibles list and the horizontals head of list to it?
What does it return? :confused:


Actually it probably exists on your prolog as permutation/2 but I
like practicing by writing a lot of the built-ins as exercise.

1 ?- permute([1,2,3],L).
L = [1, 2, 3] ;
L = [1, 3, 2] ;
L = [2, 1, 3] ;
L = [2, 3, 1] ;
L = [3, 1, 2] ;
L = [3, 2, 1] ;
No
2 ?- permute([1,2,3],[3,X,Y]).
X = 1
Y = 2 ;
X = 2
Y = 1 ;
No

---
Geoff

.

Relevant Pages

  • Re: Speed Up Sudoku Solver
    ... I'm guessing it could be speeded up with cuts, ... which fails, now it generates 1,1,...,1,2 which will still fail ... Although, if not, it might explain the confusing trace with lots of 1,1. ... How does your predicate permute/2 actually work? ...
    (comp.lang.prolog)
  • Re: Speed Up Sudoku Solver
    ... as it only uses a backtracking method to solve it. ... I'm guessing it could be speeded up with cuts, ... which fails, now it generates 1,1,...,1,2 which will still fail ... I wrote a permute/2 that takes a list and returns a permutation ...
    (comp.lang.prolog)