Right, that's the rule I was trying to state, and pointing out that when k = 1 and k = 8 it amounts to the "if there's only one possibility for a cell" and "if there's only one cell where the digit can go" rules ... --Joshua On 6/30/06, Mike Speciner <speciner@ll.mit.edu> wrote:
What about this rule:
If the set of candidate digits for some set of k positions in a row/column/block has cardinality k, then those digits can be eliminated from the rest of that row/column/block.
Is that implied by your level 1 or level 2?
--ms
Henry Baker wrote:
I've since extended my program to what I call "level 2" -- propagating forcing constraints a bit further:
If a digit in a _row_ can only appear in 2 or 3 positions within the same 3x3 block, then that digit is eliminated from the rest of the block. If the digit can appear in multiple blocks, then we can't eliminate it.
Ditto for columns.
For blocks, the rule is more complicated. If a digit can only appear within a single row or column within a block, then it can be eliminated from the rest of the row or column, respectively.
These new rules, together with the previous set of forcing rules, appears sufficient to solve the LATimes Sudoku's called "Moderate", while the previous set of rules were sufficient for those called "Gentle".
However, my "level 2" is not sufficient for LATimes "Diabolical", nor for the Sudoku's in "Sudoku Genius".
It would appear that the LATimes _does_ have a precise definition of what it means to be "Gentle" (~ level 1), "Moderate" (~ level 2), and "Diabolical".
Since "level 2" appears to be exhausting the notion of what can be done with only local rules & "force fields" (the information propagating on rows, columns & blocks), I would suggest that level 2 captures the notion of "non-backtracking".
---
BTW, I mentioned that my bit representation produced "surprises" in that some squares "accidentally" produced singleton sets. However, because these singletons were "accidental", they didn't get a chance to propagate their "first-class" status and suppress the same digit in rows, columns and blocks. While this problem is automatically fixed by level 2, this constraint really belongs to level 1, and so my level 1 program has to have an extra check just for this constraint. "The representation giveth, and the representation taketh away."
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun