Dear all,
if you want to know all about constraint programming for Sudoku, please
check Helumt Simonis' findings on it:
http://www.icparc.ic.ac.uk/~hs/
Christian
--
Christian Schulte, http://www.imit.kth.se/~schulte/
-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On
Behalf Of Torsten Anders
Sent: Thursday, November 10, 2005 9:39 AM
To: [EMAIL PROTECTED]
Subject: Re: Sudoku, again
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
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
