In answer to the question in the previous message, it appears that FD.distinct doesn't figure out that the cell between 7 and 6 must be 2.
declare A B C V = [A B C]
V ::: 1#3
{FD.distinct V}
A \=: 2
B \=: 2
{Show V}
produces:
[A{1 3} B{1 3} C{1#3}]
even though C must be 2.
-- Russ
On 11/9/05, Russ Abbott <[EMAIL PROTECTED]> wrote:
Probably the biggest problem is that there are so many symmetries. The one generic rule illustrated below applies in 54 different ways, 27 horizontal and 27 vertical. And that doesn't count the symmetries (a) created by the numbers themselves or (b) by the positions in which the common numbers can appear outside the 3x3 grid or (c) by the position of the vacant square in the 3x3 grid. Yet one wants to be able to express this rule in one form and not have to re-express it multiple times. So perhaps this isn't even a good way to think about this rule--even though it is a common technique used by Sudoku players.A simpler (and more general) way to look at this rule is to notice that the cell between the 7 and the 6 is the only cell in the 3x3 sub-grid in which a 2 is valid. Will FD.distinct figure that out? If so, this deduction rule is unnecessary.
On 11/9/05, Russ Abbott <[EMAIL PROTECTED] > 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.)
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?-- RussP.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
