Sudoku with a pure logic program?

Hello,

I want to write a sudoku solver with a pure logic prolog program (no
constraints). I tried with the SWI prolog program at the end of this
posting, but it seems to be very, very inefficient (in fact I never
waited if it will terminate or not).

I know it is easily done with clp and the all_different constraint, but
isn't it possible to write an efficient sudoko solver (similar to the
one beneath) with a pure logic program as well? What makes constraint
satisfaction here so much faster than backtracking?  Doesn't both have
to 'guess' values out of 1..9?

Thanks for your answers,
Herbert




:- use_module(library('lists')).

permute_all_nine(X) :- permutation([1,2,3,4,5,6,7,8,9],X).

sudoku(L) :-

[A1,A2,A3, A4,A5,A6, A7,A8,A9,
B1,B2,B3, B4,B5,B6, B7,B8,B9,
C1,C2,C3, C4,C5,C6, C7,C8,C9,

D1,D2,D3, D4,D5,D6, D7,D8,D9,
E1,E2,E3, E4,E5,E6, E7,E8,E9,
F1,F2,F3, F4,F5,F6, F7,F8,F9,

G1,G2,G3, G4,G5,G6, G7,G8,G9,
H1,H2,H3, H4,H5,H6, H7,H8,H9,
I1,I2,I3, I4,I5,I6, I7,I8,I9] = L,

 permute_all_nine([A1,A2,A3,A4,A5,A6,A7,A
8,A9]),   % Row1
 permute_all_nine([B1,B2,B3,B4,B5,B6,B7,B
8,B9]),   % Row2
 permute_all_nine([C1,C2,C3,C4,C5,C6,C7,C
8,C9]),   % Row3
 permute_all_nine([D1,D2,D3,D4,D5,D6,D7,D
8,D9]),   % Row4
 permute_all_nine([E1,E2,E3,E4,E5,E6,E7,E
8,E9]),   % Row5
 permute_all_nine([F1,F2,F3,F4,F5,F6,F7,F
8,F9]),   % Row6
 permute_all_nine([G1,G2,G3,G4,G5,G6,G7,G
8,G9]),   % Row7
 permute_all_nine([H1,H2,H3,H4,H5,H6,H7,H
8,H9]),   % Row8
 permute_all_nine([I1,I2,I3,I4,I5,I6,I7,I
8,I9]),   % Row9

 permute_all_nine([A1,B1,C1,D1,E1,F1,G1,H
1,I1]),   % Column1
 permute_all_nine([A2,B2,C2,D2,E2,F2,G2,H
2,I2]),   % Column2
 permute_all_nine([A3,B3,C3,D3,E3,F3,G3,H
3,I3]),   % Column3
 permute_all_nine([A4,B4,C4,D4,E4,F4,G4,H
4,I4]),   % Column4
 permute_all_nine([A5,B5,C5,D5,E5,F5,G5,H
5,I5]),   % Column5
 permute_all_nine([A6,B6,C6,D6,E6,F6,G6,H
6,I6]),   % Column6
 permute_all_nine([A7,B7,C7,D7,E7,F7,G7,H
7,I7]),   % Column7
 permute_all_nine([A8,B8,C8,D8,E8,F8,G8,H
8,I8]),   % Column8
 permute_all_nine([A9,B9,C9,D9,E9,F9,G9,H
9,I9]),   % Column9

 permute_all_nine([A1,A2,A3,B1,B2,B3,C1,C
2,C3]),   % Caret1
 permute_all_nine([A4,A5,A6,B4,B5,B6,C4,C
5,C6]),   % Caret2
 permute_all_nine([A7,A8,A9,B7,B8,B9,C7,C
8,C9]),   % Caret3
 permute_all_nine([D1,D2,D3,E1,E2,E3,F1,F
2,F3]),   % Caret4
 permute_all_nine([D4,D5,D6,E4,E5,E6,F4,F
5,F6]),   % Caret5
 permute_all_nine([D7,D8,D9,E7,E8,E9,F7,F
8,F9]),   % Caret6
 permute_all_nine([G1,G2,G3,H1,H2,H3,I1,I
2,I3]),   % Caret7
 permute_all_nine([G4,G5,G6,H4,H5,H6,I4,I
5,I6]),   % Caret8
 permute_all_nine([G7,G8,G9,H7,H8,H9,I7,I
8,I9]),   % Caret9

label(L).

Herbert Meier escreveu:
> Hello,
>
> I want to write a sudoku solver with a pure logic prolog program (no
> constraints). I tried with the SWI prolog program at the end of this
> posting, but it seems to be very, very inefficient (in fact I never
> waited if it will terminate or not).
>
> I know it is easily done with clp and the all_different constraint, but
> isn't it possible to write an efficient sudoko solver (similar to the
> one beneath) with a pure logic program as well? What makes constraint
> satisfaction here so much faster than backtracking?  Doesn't both have
> to 'guess' values out of 1..9?
>
[snipped]

You want to write a solver using pure logic, but used brute force. Each
permute_all_nine generates 362880 permutations. . .

You need to use more information to reduce the search space in order to
make it efficient.

Herbert Meier wrote:
> Hello,
>
> I want to write a sudoku solver with a pure logic prolog program (no
> constraints). I tried with the SWI prolog program at the end of this
> posting, but it seems to be very, very inefficient (in fact I never
> waited if it will terminate or not).
>
> I know it is easily done with clp and the all_different constraint, but
> isn't it possible to write an efficient sudoko solver (similar to the
> one beneath) with a pure logic program as well? What makes constraint
> satisfaction here so much faster than backtracking?  Doesn't both have
> to 'guess' values out of 1..9?

Hopefully not!
The power of CLP(FD) is that it removes inconsistent values _before_
having to guess, so it will have to guess taking values from a reduced
set of values.

If you do not want to use constraints, you have to figure out an
efficient algorithm for doing that, and will probably lose something in
the declarative reading of your program: you may want to implement the
concept of domains, removing values from domains, etc.

One of the good points in CLP(FD) is that it keeps a simple formulation
and makes solving this type of problems much more efficient than the LP
formulation.

Cheers,
Marco

--
http://www.ing.unife.it/docenti/MarcoGavanelli/

Marco Gavanelli wrote:
> If you do not want to use constraints, you have to figure out an
> efficient algorithm for doing that, and will probably lose something in
> the declarative reading of your program: you may want to implement the
> concept of domains, removing values from domains, etc.

In other words: you may want to reinvent CLP(FD).

Lars wrote:
> Marco Gavanelli wrote: 
>
> In other words: you may want to reinvent CLP(FD).

Yes ;-)

When I was studying at the university, I had the following assignment:
implement Forward Checking in Prolog. So, one can do it, it is less
efficient than CLP(FD) and much less readable.

Or, maybe, you want to use a totally different algorithm (local search?)

Cheers,
Marco


--
http://www.ing.unife.it/docenti/MarcoGavanelli/

Marco Gavanelli wrote:
> Lars wrote: 
>
> Yes ;-)
>

Thanks all for your answers ... that was actually what i wanted to
know. It helped me a lot to understand the difference between lp and
clp more.

Herbert