Arc consistency by itself will only be able to solve easy sudoku puzzles. To solve any puzzle, the search component is needed which does not currently exist.
Ok, but I am still stuck on making sure I understand what "arc > consistent" means. > http://en.wikipedia.org/wiki/Local_consistency#Arc_consistency > My guess, since you are using a universal quantifier, is that since > these solutions are inconsistent with each other, that some sudoku > puzzles which have multiple solution would not have an arc consistent > representation. So I think that you would have "all 0s" for some of > your rows in D in that case. > > Does that sound right? > Not quite, though I'm not sure I understand. As soon as a 'D' has a row with 'all 0s' the game is up. In general 'D' will correspond to a specific sudoku instance you are solving. It will not span across many different instances. What enforcing arc consistency does is reduce the possible values for some cell of the sudoku (ie. reduce the domain of some variable). Not having an arc consistent representation means that the given sudoku instance 'D' does not have a solution. For sudokus with at least one solution, not having an arc consistent representation could only be reached by making a bad guess in our (non-existant) backtracking search. > > That said, I think I tried your algorithm on the empty sudoku case and > it returned (i. 0);81 9$1 > Right, there is no filtering that can be done here. We need to make an initial guess for some unassigned variable. > > Here's the specific values I used: > n=:81 > d=:9 > D=: 81 9 $ 1 > c1=: ~:/~ i. 9 > > COL=: , |: 9#,:i.9 > ROW=: ,9#,:i.9 > BOX=: ,3#3#"1 i.3 3 > A=: ((2*>/~i.81)+</~i.81) * (+. |:) (COL =/ ROW) +. (COL =/BOX ) +. (ROW > =/ BOX) > > So consistent, here, does not mean what I expected -- I was expecting > (i.0);81 9 $ 0 > (i.0);81 9 $ 0 Would mean that the blank sudoku puzzle has no solution which is wrong. > 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. > > I am beginning to think you mean > > for all w in Dy there exists a v in Dx such that the relationship v > compare w is true. > > Does this sound right? > > Yes, that sounds right so long as compare implies looking up the values in the correct constraint table. Your formulation also sounds consistent with what I said before signalling that something has been lost in translation! consistent = compatible = relationship is true Cheers, Mike ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
