Dear Ross,
On 10.11.2005, at 07:08, Russ Abbott wrote:
As I mentioned earlier, FD.distinct does such an efficient job with
Sudoku that it seems like a waste of time to program special-purpose
Sudoku deduction rules. By deduction rules, I mean rules like the one
that tells you that the cell between the 7 and 6 on the third row must
contain a 2. (This is from
http://www.paulspages.co.uk/sudoku/howtosolve/index.htm.)
If the cells containing the 7 and 6 are already determined, you can
simply traverse the list containing the row, to find them (e.g. using
something similar to List.filter) and apply the respective constraint.
In case you want to add such knowledge without knowing where 7 and 6
are positioned, you could apply a reified constraint on all candidate
triples like
% X1 X2 X3 are any three neighbouring cells
{FD.impl {FD.conj (X1=:7) (X3=:6)}
(X2=:2)
1}
Best,
Torsten
<image.tiff>But let's assume one wanted to program such rules anyway.
It seems to me that it would be much more tedious a task than it
should be.
Oz is supposed to provide the best of logic programming and functional
programming. With all that power, it should be easy to express simple
rules like this. But it seems to me that it would take an awful lot
of infrastructure work to build up enough mechanism to make expressing
such rules straightforward. Does anyone know of an easy way to write
such rules?
One problem is that the board itself is expressed as a list of lists,
which is inconvenient. One could write accessor methods that allowed
one to address it as an array. But we don't have a library of array
accessors, especially accessors that talk about particular array rows,
columns, and 3x3 sub-blocks. One could write those also--as we did
for the basic Sudoku solution. But even then, writing rules would be
tedious.
Does anyone see a simple way of writing the easy deduction
(propagator) rule above, even if one expressed such a rule in terms
of references to rows, columns, and sub-blocks?
-- Russ
P.S. By the way, I generalized my version of the Sudoku solver
(http://cs.calstatela.edu/~wiki/index.php/Courses/CS_460/Fall_2005/
Simplified_Sudoku_Solver ) so that it uses (at the user's option) FD,
thread bombs, or *very* naive search within the same basic structure.
When I ran it on the example, FD took < 1 ms; thread bombs took 1.2
minutes; and I didn't have the nerve to run the very naive search.
_______________________________________________________________________
__________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
--
Torsten Anders
Sonic Arts Research Centre
Queen's University Belfast (UK)
www.torsten-anders.de
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
