I've now implemented k=1 & k=8 (level 1) and k=2 & k=7 (level 2). I
implemented k=2/k=7 in such a way that the two cells are never the same cell.
Nevertheless, it appears that k=2&k=7 completely _subsume_ the k=1&k=8 cases.
If I implemented k=2/k=7 in a way that allowed the cells to be the same,
then this would trivially follow, but I included a check to make sure that
I was never inadvertently operating on the same cell in two different roles.
I.e., if the cells (i1,j1), (i2,j2) were the two cells, it is never the case
that i1=i2 and j1=j2 at the same time.
I should attempt to prove that if you do the level 2 checks, you should never
have to do level 1 checks.
LATimes "Moderate" appears to approximate my "level 2" (k=2/k=7).
LATimes "Tough" and "Diabolical" are not routinely solved by my level 2, although
the "Tough" ones come very close. Perhaps Tough = level 3 (k=3/k=6) ?
Only a very few of "Sudoku Genius" sudoku's succumbed to level 2.
-------
I implemented the k=1 & k=8 rules, and this is "level 1".
Interestingly, these 2 rules are somewhat dual to one another -- perhaps someone
else has better insight on this?
The k=1 rule says that there's only one possibility for a cell (singleton set),
so _broadcast_ this information to the rest of the row, column and block. The
information flows out from the cell -- i.e., the cell itself doesn't change, but
it potentially changes the rest of the row, column and block.
The k=8 rule extracts information from the row, column and block to constrain
what goes into the cell. All of the information goes _into_ the cell -- i.e.,
the only thing that changes is the cell itself.
So level one is a series of waves of information alternating out & in. When
there's no new information to be processed, the puzzle is either solved, or
isn't crackable via level 1.
"Level 1" seems to be a very natural level. Unfortunately, it isn't particularly
powerful -- it can only handle the LATimes "Gentle" sudokus.
"Level 2" would seem to be similar to level 1, except also handling k=2 and k=7.
I haven't fully implemented this version of "Level 2", as of yet.
At 10:02 AM 6/30/2006, Joshua Zucker wrote:
>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(a)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."
