This paper was also mentioned earlier, and I appreciate the reference. I did look at it but found that I was unable to understand it without additional reading. It says that the use of hyper-arc consistency along with shaving will solve all the Sudoku puzzles that they attempted without search.
But here are two things that confused me. The paper says:
n^2 x n^ 2 matrix of finite domain variables with domain 1 to n^2. We set up 3 *n^2 alldifferent constraints for each row, each column and each major n x n block. (For standard Sudoku, n = 3.) I don't understand why it's necessary to set up so many allDifferent constraints. In the basic problem one needs only 3*n^2 constraints all together, not that many for each row, column, and subgrid. Or am I reading the sentence the wrong way? Should it read: " We set up 3*n^2 alldifferent constraints, one for each row, each column and each major n x n block."The program uses a
The paper also talks about using hyper arc consistency checking and shaving. I didn't know what those mean. In particular, from the brief description given, shaving sounds like a form of search. The paper says that shaving
considers the complete constraint set by trying to set variables to values in their domain. If the assignment fails, then this value can be removed from the domain, possibly eliminating many inconsistent values before starting search.
But that sounds a lot like search to me. So why isn't it considered search?
Any help in understanding this would be appreciated.
-- Russ
On 11/10/05, Christian Schulte <[EMAIL PROTECTED]> wrote:
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
> ofreferences 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
--
_____________________________________________
Professor, Computer Science
California State University, Los Angeles
o Check out my blog at http://russabbott.blogspot.com/
_________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
