Prolog - Sudoku with a pure logic program?

Author

Sudoku with a pure logic program?

Herbert Meier

2006-07-18, 3:59 am

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

Cesar Rabak

2006-07-18, 3:59 am

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.

Marco Gavanelli

2006-07-18, 3:59 am

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/

Lars

2006-07-18, 7:59 am

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

Marco Gavanelli

2006-07-18, 7:59 am

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/

Herbert Meier

2006-07-18, 7:00 pm

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

Sponsored Links