> 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. >
Nice! I haven't gone through it yet. > 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. > Yes, this is unfortunate, but I can only do so much in J and inspecting randomly generated values was possible for me. > Reading over your notes, one of my problems is that I do not > understand what "arc consistent state" means. > Arc consistent means that for every pair of adjacent variables, x and y, every value in Dx is compatible with at least one value in Dy. Put another way, there is no value v in Dx such that the v is not consistent with any value w in Dy. > > 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? > Yes, that is exactly 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 > Harder sudokus, or sudokus with multiple solutions, will require interleaving the ac-filtering with search. The search consists of guessing a value for an unassigned variable and assigning that value to the variable. At that point you can run '... ac (x;D)' where x is the assigned variable and D is the domain with Dx assigned to a single value. If this produces a D for which isValid is false, we backtrack and try assigning another value for x. When we exhaust all values for x we backtrack to the previous variable we have guessed values for. The search is nowhere to be seen in the code, > > 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? > TODO ;-) Although this could potentially be dangerous. For example the completely empty sudoku puzzle has very many solutions and I doubt my computer would have the patience to go through them all. Mike ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
