start  find  index  login or register  edit  
20051004
by earl, 5093 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: n(V) for each valid numbervalue 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 minsize)* out of competition, slightly different machine (2000mhz athlon xp vs 1800mhz intel pentiumm) 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 SWIProlog, SICStus Prolog and ECLiPSe [CLP] compare to the results of gnu prolog. both, gnu prolog and dlv have to solve a constraintsatisfaction 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 8 active users
backlinks (more) none, yet recent stores (more) recent comments echo earlZstrainYattr ZY @.


earl.strain.at • esa3 • online for 6768 days • c'est un vanilla site 