On Sun, Nov 4, 2012 at 4:47 PM, Michal D. <[email protected]> wrote: > The solver can solve sudoku puzzles (hopefully =)) but it should also be > able to handle more general csp instances where the constraints are not > symmetric. In the case of a sudoku puzzle, I think a single symmetric > not-equal constraint would suffice. > > n=: 81 > d=: 9 > > ] C=: a: , < (i.d) ~:/ (i.d) > ++-----------------+ > ||0 1 1 1 1 1 1 1 1| > ||1 0 1 1 1 1 1 1 1| > ||1 1 0 1 1 1 1 1 1| > ||1 1 1 0 1 1 1 1 1| > ||1 1 1 1 0 1 1 1 1| > ||1 1 1 1 1 0 1 1 1| > ||1 1 1 1 1 1 0 1 1| > ||1 1 1 1 1 1 1 0 1| > ||1 1 1 1 1 1 1 1 0| > ++-----------------+ > > A is a little bit beyond me to define at the moment. It would be an 81x81 > matrix. For a variable x, it would be 1 for all variables on the same row, > column and box as x and 0 otherwise.
Here's a brute force implementation of A for sudoku: C=: |: R=: ,9#,:i.9 NB. identity within columns (C) and rows (R) B=: ,3#3#"1 i.3 3 NB. identity within boxes A=: ((2*>/~i.81)+</~i.81) * (+. |:) (C =/ R) +. (C =/B ) +. (R =/ B) I left the extraneous right-most set of parenthesis in place because I liked the rhythm. > Side note: as you can see, not-equal is not a very strong constraint. > Interleaving AC with search would probably be necessary to solve harder > sudoku instances. > > Would changing: > > NB. a single constraint (note: constraints are not symmetric, for example > x<y). > > to > > NB. a single constraint (note: constraints may be asymmetric, for example > x<y). > > resolve the confusion? No, that was not my problem. I think I understood the implicit "may". My problem is that I do not know how to look at results from this computation and determine if they are correct, nor do I have an illustrative set of test cases. This means that I do not understand what you are talking about. I think I understand the words, but I obviously do not understand the plot. Reading over your notes, one of my problems is that I do not understand what "arc consistent state" means. Also, in the context of sudoku, I am not sure what D would be.... I'm going to guess though that it would be an 81 row 9 column bit matrix, with rows being "all 1s" for blanks in the sudoku puzzle, and being a single "1" for digits in the sudoku puzzle. Also, if a solver returned any rows that were all zero, that would mean that that sudoku puzzle has no solution. Does this sound right? If that is the case, how would this work, for a sudoku puzzle which has multiple solutions? Roger at one point mentioned a puzzle with 1905 solutions http://www.jsoftware.com/pipermail/programming/2005-December/000303.html If D were instead a list of 81 by 9 bits, with extra copies of D being introduced as necessary, the "multiple answer" case could be addressed by having an extra item in D for every valid solution. Here, the initial D would have shape 1 81 9 and a final D would have shape n,81 9 where n is a (hopefully small) non-negative integer. But that's not what you are doing here? -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
