2005-10-04
by earl, 6987 days ago
while at the quite amazing REBOL DevCon 2005 (more on that later) viktor and i decided to write some simple sudoku solvers. viktor did so using REBOL, i used DLV. here is what i came up with (more discussion after the code!):%this relies on a representation of the sudoku "board" as follows:
% simple sudoku solver
% andreas bolka, 2005-09-30
%
% -- guess --
place(Y,X,V) v -place(Y,X,V) :-
f(Y,X), n(V), not has_given(Y,X).
% -- check --
% can't have a cell with nothing on it
:- f(Y,X), not has_value(Y,X).
% prune 3x3 regions containing a digit twice
:- f(Y1,X1), r(Y1,X1,S), value(Y1,X1,V),
f(Y2,X2), r(Y2,X2,S), value(Y2,X2,V),
not same_field(Y1,X1, Y2,X2).
% prune rows containing a digit twice
:- f(Y,X1), f(Y,X2), value(Y,X1,V), value(Y,X2,V),
not same_field(Y,X1, Y,X2).
% prune cols containing a digit twice
:- f(Y1,X), f(Y2,X), value(Y1,X,V), value(Y2,X,V),
not same_field(Y1,X, Y2,X).
% -- helpers --
value(Y,X,V) :- given(Y,X,V).
value(Y,X,V) :- place(Y,X,V).
has_given(Y,X) :- given(Y,X,_).
has_value(Y,X) :- value(Y,X,_).
same_field(Y1,X1,Y2,X2) :- f(Y1,X1), f(Y2,X2), Y1 = Y2, X1 = X2.
n(V) for each valid number-value V (1..9) that may be placed on a field. f(Y,X) for each valid field, Y being the row (1..9) and X being the column (1..9). r(Y,X,S) associating each field Y,X with the 3x3 region S containing the field, i.e. square(2,1,11). or square(7,9,33)..sudoku problem instances are then described using any amount of
given(Y,X,V) facts which state the values V given for fields Y,X.even i myself was surprised at how concise DLV allows to express the problem and how quickly the program was written. i went on to some performance measurements and trying things at the console, answers appeared quickly, but not instantly, even for evil problems. so the thing was at least generally viable (while coding i pondered, more than once, the combinatorical space dlv has to potentially cope with).
if we compare the performance of the DLV solution given above and viktors REBOL solution to the c++ and prolog versions discussed on a TU Wien weblog and Arthur Whitney's K4 version, we get the following timings for "riddle 7":
prolog version: 2 ms (gplc --min-size)* out of competition, slightly different machine (2000mhz athlon xp vs 1800mhz intel pentium-m)
c++ version: 3 ms (g++ -O3)
rebol version: 120 ms (rebol 2.5.6)
python version: 130 ms (python 2.3.5)
dlv version: 890 ms (dlv 2005-02-23)
k version: 28 ms * (kdb+ 2.2 2005.08.17)
for now, i leave the interpretation of those results up to you. what i personally find very interesting is the performance achieved by the prolog version. that's a compiled program using GNU Prolog's constraint solving capabilities. it would be interesting how implementations using the constraint solving of SWI-Prolog, SICStus Prolog and ECLiPSe [CLP] compare to the results of gnu prolog.
both, gnu prolog and dlv have to solve a constraint-satisfaction problem and both use superficially similar methods to express the problem but seemingly quite different methods for solving it. for me, that definitely warrants more exploration into that area ;)
search
40 active users
- unknown (40)
backlinks (more)
none, yet
recent stores (more)
recent comments
echo earlZstrainYat|tr ZY @.
