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@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."