Re: Speed Up Sudoku Solver

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

Andrew wrote:
I have cobbled together a Sudoku solver in Prolog (see below).
However, it is extremely slow (almost a minute with only 8 squares missing!)
as it only uses a backtracking method to solve it.

I'm guessing it could be speeded up with cuts, but I am only guesssing.

Can you give me some advice please?


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,...]...]]),
...

---
Geoff

Hi Geoff,

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.

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:

Regards

/Andrew
.

Relevant Pages

  • 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)
  • Re: Speed Up Sudoku Solver
    ... 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 ... Although, if not, it might explain the confusing trace with lots of 1,1. ... Actually it probably exists on your prolog as permutation/2 but I ...
    (comp.lang.prolog)