The New Sudoku Players' Forum

by **Jeff** » Tue Nov 29, 2005 10:52 am

Nick70 wrote:.......It's a theorem following from the BUG principle (which has been proven by Nick67).

Thank you, Nick 67 for your contribution.

by **Nick67** » Tue Nov 29, 2005 11:24 am

Thanks Jeff! A great job by you, tso, Nick70, and Myth Jellies
on this whole set of ideas.

by **MadOverlord** » Wed Nov 30, 2005 12:05 am

Nick70 wrote:Here is an application of the BUG principle with three quadrivalue cells:
Code: Select all
7 2 69 | 5 3 69 | 8 1 4 89 4689 5 | 1 2 48 | 3 69 7 1 3 48 | 69 7 48 | 5 69 2 -------------------+--------------------+------------------- 6 1 2 | 8 4 5 | 9 7 3 5 47 47 | 3 9 1 | 6 2 8 3 89 89 | 7 6 2 | 1 4 5 -------------------+--------------------+------------------- 89 6789 6789 | 4 1 3 | 2 5 69 4 69 3 | 2 5 69 | 7 8 1 2 5 1 | 69 8 7 | 4 3 69

I am trying to wrap my head around BUG in order to implement it in the Susser (I go fight robots for a weekend and see what you guys come up with... OTOH, my kids repeated as national champs!).

I've been thinking about algorithms and come up with a preliminary idea that ought to be workable and similar to how a human might do it, as follows:

* For any Sudoku grid, the squares are either 1-possibility (solved), 2-possibility, or n-possibility (n>2)

* For each n-possibility square, select a row/column/block that is not touched by any of the other UNPROCESSED n-possibility squares. In Nick's example, we could select R2C2 and row 2 or block 1, but not column 2 since that is shared with R7C2. We do the BUG reduction.

* We continue on with the other squares. We can now, for example, do R7C2 and column 2, since we've already processed R2C2.

* If we cannot find an unblocked reduction, we cannot create a BUG; fail.

* If we reduce all the n-possibility squares, then we have created a BUG pattern.

Code: Select all: Questions: is there only one possible BUG for any puzzle? Or if there are more than one, are they equivalently useful in solving, or will they be found eventually after multiple BUG hunts?

* Subtracting the BUG possibilities from the original puzzle state gives us the possible BUG-killer reductions. As Nick explains:

The BUG principle allows us to say that either r2c2=89 or r7c2=69 or r7c3=89.

Now, if there's only one reduction square, then it's easy - just apply the reduction, since there's only one possible move.

What I'm trying to wrap my head around is how to merge multiple reductions together. Nick says:

Putting those together, we can say that r2c2=489, r7c2=679 and r7c3=789

but this is the step I don't quite suss yet.

Looking at Nick's puzzle, I do note one feature, however. R2C2 starts as 4689, we prove the BUG value for it is 46, so we know it may be 89. If we leave it at that, then B1,R2 and C2 will only have one possible 4 and one possible 6. So far, nothing important (or is it?)

But R2C2 shares C2 with another n-possibility square, R7C2. If we apply a rule that: "you can only do a reduction that creates a conjugate pair in all groups it shares with any other n-possibility squares" then we find:

* we know R2C2 must be 89 + one or both of 46. Removing 6 creates a conjugate pair (on 6, of course) R7C2:R8C2. But removing 4 creates a pin. So we get 489.

* R7C2 must be 69 + one or both of 78. Removing 8 creates a CP on 8 in C2, a CP on 8 in C7, and a CP in 8 in B6. So R2C7 becomes 679.

* R7C3 must be 89 + one or both of 67. Removing 6 creates a CP on 6 in R7 and B6.

Now the question is: is this the rule, or just a lucky accident? Lets look at another Nick example:

Nick70 wrote:Here is the first example of a BUG application with a cell containing more than 3 candidates:

Code: Select all
1 28 3 | 4 5 6 | 7 289 89 4 5 7 | 3 89 29 | 12 6 18 6 28 9 | 7 18 12 | 4 5 3 ----------------+-----------------+---------------- 9 7 4 | 5 3 8 | 12 12 6 5 3 6 | 19 2 19 | 8 4 7 8 1 2 | 6 4 7 | 9 3 5 ----------------+-----------------+---------------- 27 9 1 | 28 6 3 | 5 78 4 27 6 5 | 28 19 4 | 3 1789 189 3 4 8 | 19 7 5 | 6 19 2

However we can also apply the BUG principle to say that r1c8=8, r8c8=19, r8c9=8 (each one of the three forces the other two through cells r7c8 and r9c8).

Okay, generating the BUG makes R1C8=29, then R8C8=78, then R8C9=19. So this tells us R1C8=8+29 or R8C8=19+78 or R9C8=8+19 (where the +XY are the digits that we may or may not be able to remove).

Now we have to do our conjugate pair analysis.

Removing 2 from R1C8 does not create a conjugate in C8 (shared with R8C8). Removing 9 does. So R1C8 becomes 89. This by itself is enough to crack the puzzle.

Removing 7 from R8C8 does not create a conjugate in R8 (shared with R8C9). Removing 8 creates conjugates in R8, B9 (shared with R8C9) and R7 (shared with R1C8). So R8C8 can become 179. This by itself does not lead to a crack.

Removing 1 from R8C9 creates conjugates in R8 and B9. Removing 9 from R8C9 creates conjugates in them too. So both can go; R8C9=8 - which is a crack.

Finally, here's Nick's "clean" simple trivalue puzzle:

Code: Select all: 4 78 6 | 3 9 5 | 78 2 1 37 9 25 | 8 1 26 | 57 36 4 38 1 25 | 7 4 26 | 58 9 36 -------------------+--------------------+------------------- 2 36 14 | 14 5 8 | 36 7 9 16 78 378 | 16 2 9 | 4 5 38 9 5 48 | 46 3 7 | 2 1 68 -------------------+--------------------+------------------- 78 2 78 | 9 6 3 | 1 4 5 5 4 9 | 2 8 1 | 36 36 7 16 36 13 | 5 7 4 | 9 8 2

Generating the BUG makes R5C3=37. So we know it's 8+37. But in this case, since there's nothing to compare it against, it just has to be 8.

So, have I gotten this right? If so, BUG-hunting (gotta love the name) may be useful in solving some puzzles with a lot of n-possibility squares.

Best
R

by **Jeff** » Wed Nov 30, 2005 10:16 am

MadOverlord wrote:Questions: is there only one possible BUG for any puzzle? Or if there are more than one, are they equivalently useful in solving, or will they be found eventually after multiple BUG hunts?

For grids with more unsolved poly-valued cells, multi-BUGs are possible. Consider the following example:

Starting grid:

Code: Select all: 2 7 3 | 6 8 4 | 19 5 19 9 1 4 | 5 7 3 | 8 2 6 58 6 58 | 9 1 2 | 34 7 34 --------------+---------------+---------------- 6 38 7 | 4 5 1 | 2 389 389 48 2 9 | 3 6 7 | 5 148 148 45 35 1 | 8 2 9 | 6 34 7 --------------+---------------+---------------- 1 58 258 | 7 3 6 | 49 489 2489 7 9 6 | 2 4 8 | 13 13 5 3 4 28 | 1 9 5 | 7 6 28

This grid can be reduced into 2 BUG grids:

Code: Select all: 2 7 3 | 6 8 4 | 19 5 19 9 1 4 | 5 7 3 | 8 2 6 58 6 58 | 9 1 2 | 34 7 34 --------------+---------------+---------------- 6 38 7 | 4 5 1 | 2 89 39 48 2 9 | 3 6 7 | 5 14 18 45 35 1 | 8 2 9 | 6 34 7 --------------+---------------+---------------- 1 58 25 | 7 3 6 | 49 89 24 7 9 6 | 2 4 8 | 13 13 5 3 4 28 | 1 9 5 | 7 6 28

Code: Select all: 2 7 3 | 6 8 4 | 19 5 19 9 1 4 | 5 7 3 | 8 2 6 58 6 58 | 9 1 2 | 34 7 34 --------------+---------------+---------------- 6 38 7 | 4 5 1 | 2 89 39 48 2 9 | 3 6 7 | 5 18 14 45 35 1 | 8 2 9 | 6 34 7 --------------+---------------+---------------- 1 58 25 | 7 3 6 | 49 49 28 7 9 6 | 2 4 8 | 13 13 5 3 4 28 | 1 9 5 | 7 6 28

MadOverlord wrote:................If we apply a rule that: "you can only do a reduction that creates a conjugate pair in all groups it shares with any other n-possibility squares" ..................Now the question is: is this the rule, or just a lucky accident?

This seems to be a logical move, but I know Nick70 won't put his thumbs up unless it is proven beyond reasonable doubt. Clever people like Nick67 might like to take up this challenge. My question is, what would happen if a reduction creates another naked subset other than a naked pair?

by **MadOverlord** » Wed Nov 30, 2005 4:21 pm

Jeff wrote:For grids with more unsolved poly-valued cells, multi-BUGs are possible. Consider the following example:

Starting grid:
Code: Select all
2 7 3 | 6 8 4 | 19 5 19 9 1 4 | 5 7 3 | 8 2 6 58 6 58 | 9 1 2 | 34 7 34 --------------+---------------+---------------- 6 38 7 | 4 5 1 | 2 389 389 48 2 9 | 3 6 7 | 5 148 148 45 35 1 | 8 2 9 | 6 34 7 --------------+---------------+---------------- 1 58 258 | 7 3 6 | 49 489 2489 7 9 6 | 2 4 8 | 13 13 5 3 4 28 | 1 9 5 | 7 6 28

This grid can be reduced into 2 BUG grids:

Note that the above grid would not be found by my proposed algorithm, since after dealing with R7C3, there is no n-possibility square that is a singleton in a row, column or block. It may be that this restriction is needed in order to ensure only a single reduction; if so, let's call them Unique BUGs.

But let us continue with your BUGs:

I have adjusted your grids to use the +xy notation to indicate the BUG possibilities.

Code: Select all: 2 7 3 | 6 8 4 | 19 5 19 9 1 4 | 5 7 3 | 8 2 6 58 6 58 | 9 1 2 | 34 7 34 --------------+---------------+---------------- 6 38 7 | 4 5 1 | 2 3+89 8+39 48 2 9 | 3 6 7 | 5 8+14 4+18 45 35 1 | 8 2 9 | 6 34 7 --------------+---------------+---------------- 1 58 8+25| 7 3 6 | 49 4+89 89+24 7 9 6 | 2 4 8 | 13 13 5 3 4 28 | 1 9 5 | 7 6 28

R4C8: 8 cannot be removed; removing it generates conjugates in R4 and C8, but not B6. Ditto 9; no conjugates formed in any of the blocks.
R4C9: No conjugate formed for 3 in C9; None for 9, same as R4C8
R5C8: No conjugate for 1 in C8; conjugates for 4 in R5,C8 and B6!
R5C9: No conjugate for 1 in C8; no conjugate for 8 in B6 (we get a triple)
R7C3: No conjugate for 2 in R7; ditto on 5.
R7C8: No conjugate for 8 (triple in R7). No conjugate for 9 in C8.
R7C9: No conjugate for 2 in R7. Conjugate for 4 in R7,C9 and B9!

This implies the following reductions: R5C8=18, R7C9=289; these reductions are correct.

Now lets look at your other example:

Code: Select all: 2 7 3 | 6 8 4 | 19 5 19 9 1 4 | 5 7 3 | 8 2 6 58 6 58 | 9 1 2 | 34 7 34 --------------+---------------+---------------- 6 38 7 | 4 5 1 | 2 3+89 8+39 48 2 9 | 3 6 7 | 5 4+18 8+14 45 35 1 | 8 2 9 | 6 34 7 --------------+---------------+---------------- 1 58 8+25| 7 3 6 | 49 8+49 49+28 7 9 6 | 2 4 8 | 13 13 5 3 4 28 | 1 9 5 | 7 6 28

There are again two conjugates generated: R5C9:4 and R7C8:4. Both of these reductions are correct! Note also that they are a "mirror" of the reductions found with the other BUG (R5C8:4 and R7C9:4)

With this demonstrated, I wondered what would happen if I applied BUG to the result of finding the first set of reductions. We start with:

Code: Select all: +-------------+-------------+-------------+ | 2 7 3 | 6 8 4 | 19 5 19 | | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+-------------+ | 6 38 7 | 4 5 1 | 2 389 389 | | 48 2 9 | 3 6 7 | 5 18 148 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+-------------+ | 1 58 258 | 7 3 6 | 49 489 289 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+-------------+

and can generate (showing the steps; I do this because I'm thinking about the algorithms that will be needed). We must set R7C3 to create the naked triple in C3.

Code: Select all: +-------------+-------------+-------------+ | 2 7 3 | 6 8 4 | 19 5 19 | | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+-------------+ | 6 38 7 | 4 5 1 | 2 389 389 | | 48 2 9 | 3 6 7 | 5 18 148 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+-------------+ | 1 58 8+25| 7 3 6 | 49 489 289 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+-------------+

and we can also work on R5.

Code: Select all: +-------------+-------------+---------------+ | 2 7 3 | 6 8 4 | 19 5 19 | | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+---------------+ | 6 38 7 | 4 5 1 | 2 389 389 | | 48 2 9 | 3 6 7 | 5 18 8+14 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+---------------+ | 1 58 8+25| 7 3 6 | 49 489 289 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+---------------+

At this point, we have no singleton blocks, so we have to bifurcate the puzzle. In R7, we have 2 ways to go.

Code: Select all: +-------------+-------------+---------------+ Call this | 2 7 3 | 6 8 4 | 19 5 19 | R7A | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+---------------+ | 6 38 7 | 4 5 1 | 2 389 389 | | 48 2 9 | 3 6 7 | 5 18 8+14 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+---------------+ | 1 58 8+25| 7 3 6 | 49 8+49 9+28 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+---------------+

and

Code: Select all: +-------------+-------------+---------------+ And this | 2 7 3 | 6 8 4 | 19 5 19 | R7B | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+---------------+ | 6 38 7 | 4 5 1 | 2 389 389 | | 48 2 9 | 3 6 7 | 5 18 8+14 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+---------------+ | 1 58 8+25| 7 3 6 | 49 9+48 8+29 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+---------------+

...pick R7A and do row 4; at this point, there are two possible ways to create the locked set, but only one of them creates the locked set in the columns...

Code: Select all: +-------------+-------------+---------------+ R7A | 2 7 3 | 6 8 4 | 19 5 19 | | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+---------------+ | 6 38 7 | 4 5 1 | 2 8+39 3+89 | | 48 2 9 | 3 6 7 | 5 18 8+14 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+---------------+ | 1 58 8+25| 7 3 6 | 49 8+49 9+28 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+---------------+

...we can't use the above, because for example, there are 3 3's in C8. And
we can't check for this problem earlier in the sequence (when we first bifurcated)

Code: Select all: +-------------+-------------+---------------+ R7A | 2 7 3 | 6 8 4 | 19 5 19 | | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+---------------+ | 6 38 7 | 4 5 1 | 2 3+89 8+39 | | 48 2 9 | 3 6 7 | 5 18 8+14 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+---------------+ | 1 58 8+25| 7 3 6 | 49 8+49 9+28 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+---------------+

...but the other possibility IS a BUG pattern. Now doing our conjugate analysis on it, we find none, so this BUG doesn't help us AFAICT.

Going back to R7B and working on R4, AFAICT there are no BUG patterns that can be made because a 9 possibility has to be in R5C7, and it will be a singleton 9 in C7 (which is, btw, the solution to that square, i have no idea if this is significant)

Code: Select all: +-------------+-------------+---------------+ R7B | 2 7 3 | 6 8 4 | 19 5 19 | | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+---------------+ | 6 38 7 | 4 5 1 | 2 8+39 3+89 | no 9 in col 7 | 48 2 9 | 3 6 7 | 5 18 8+14 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+---------------+ | 1 58 8+25| 7 3 6 | 49 9+48 8+29 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+---------------+

I may be missing something along the way, but this indicates that in a multi-BUG, you've got to follow all the paths in order to find all the reductions, because once you make the reduction for one multi-bug, you can't find the other ones.

I'm actually hoping someone finds a mistake above. What it is leading me to believe is that multi-bugging is just a fancy way of doing brute-force recursion.

by **Nick70** » Wed Nov 30, 2005 5:03 pm

MadOverlord wrote:What it is leading me to believe is that multi-bugging is just a fancy way of doing brute-force recursion.

The only thing I can say is: of course.

by **MadOverlord** » Thu Dec 01, 2005 2:48 am

Nick70 wrote:The only thing I can say is: of course.

Your economy of expression is to be admired.

Okay, I've implemented a rough version of Unique BUGs in the Susser and have been playing around with it. I've run about 200 of the Top870 puzzles through it and it's found a half-dozen or so BUGs, reducing them correctly.

One tweak to the algorithm I proposed is that it is possible during the BUG reduction process to get to a point where you can't reduce a group to the bivalue state; this should trigger a failure of the reduction.

Here is the biggest BUG I've found so far:

Code: Select all: +----------------+----------------+----------------+ | 7 49 6 | 5 1 3 | 48 489 2 | | 14 1349 2 | 8 6 49 | 7 5 349 | | 5 349 8 | 7 49 2 | 34 1 6 | +----------------+----------------+----------------+ | 3 6 7 | 9 2 5 | 148 48 14 | | 9 2 5 | 4 8 1 | 36 367 37 | | 48 48 1 | 6 3 7 | 9 2 5 | +----------------+----------------+----------------+ | 6 7 39 | 1 5 49 | 2 34 8 | | 2 5 4 | 3 7 8 | 16 69 19 | | 18 18 39 | 2 49 6 | 5 347 347 | +----------------+----------------+----------------+

The Susser's opinion is:

* The puzzle can be reduced to a Bivalue Universal Grave (BUG) pattern, by making these reductions:

R5C8=<67>, R4C7=<18>, R3C2=<39>, R2C2=<13>, R1C8=<89>, R9C8=<37>, R2C9=<39> and R9C9=<47>.

These are called the BUG possibilities. In a BUG pattern, in each row, column and block, each unsolved possibility appears exactly twice. Such a pattern either has 0 or 2 solutions, so it cannot be part of a valid Sudoku.

When a puzzle contains a BUG, and more than one square in the puzzle has more then 2 possibilities, then BUG possibilities can be removed from squares if, and only if, removing the possibility results in it appearing exactly twice in that square's row, twice in its column, and twice in its block.

R9C8 - removing <3> from <347> leaving <47>.
R9C9 - removing <4> from <347> leaving <37>.

by **Myth Jellies** » Thu Dec 01, 2005 4:57 am

I noticed that bennys's to rubylips thread contained an end state that had several interesting features.

rubylips wrote:
Code: Select all
2|8 2|9 1 | 4 5 6 | 7|9 7|8|9 3 5|6 5|9 4|6 | 3 7 8 | 2 1|4|9 1|4|9 7 3 4|8 | 1 9 2 | 5 4|8 6 --------------------+------------+------------------- 6|8 6|8 9 | 7 1 3 | 4 5 2 4 1 2 | 9 6 5 | 8 3 7 3|5 7 3|5 | 2 8 4 | 6 1|9 1|9 --------------------+------------+------------------- 1|2 4 6|8 | 6|8 3 9 | 1|7 2|7 5 1|2|3|5 2|5 3|5 | 6|8 4 7 | 1|9 2|6|9 8|9 9 6|8 7 | 5 2 1 | 3 4|6 4|8

Not only does it have a BUG grid (r1c8=78, r2c8=19, r2c9=49, r8c1=13, and r8c8=26), but it also has a uniqueness pattern for 1's and 9's in the upper right, and another uniqueness pattern for 3's and 5's in the lower left.

Either of the uniqueness grids will quickly solve the puzzle, but the BUG grid leads to nothing useful that I could see. Too many non-BUG choices, and only one of the non-BUG candidates (the 2 from r8c1) turns out to be part of the correct solution.

by **MadOverlord** » Thu Dec 01, 2005 5:12 am

Myth Jellies wrote:...the BUG grid leads to nothing useful that I could see.

The conjugate rule for determining what reductions can be made on a multiple polysquare BUG eliminates all possible reductions in this case. Just because there's a BUG doesn't mean you'll always find reductions.

Here's the BUG debug output from the Susser giving the details of how the BUG is constructed, but once it is, there are no reductions.

Code: Select all: PolySquare: R1C8=789 PolySquare: R2C8=149 PolySquare: R2C9=149 PolySquare: R8C1=1235 PolySquare: R8C8=269 Reduced R8C8 to 26: +----------------+----------------+----------------+ | 28 29 1 | 4 5 6 | 79 789 3 | | 56 59 46 | 3 7 8 | 2 149 149 | | 7 3 48 | 1 9 2 | 5 48 6 | +----------------+----------------+----------------+ | 68 68 9 | 7 1 3 | 4 5 2 | | 4 1 2 | 9 6 5 | 8 3 7 | | 35 7 35 | 2 8 4 | 6 19 19 | +----------------+----------------+----------------+ | 12 4 68 | 68 3 9 | 17 27 5 | | 1235 25 35 | 68 4 7 | 19 26 89 | | 9 68 7 | 5 2 1 | 3 46 48 | +----------------+----------------+----------------+ Reduced R8C1 to 13: +-------------+-------------+-------------+ | 28 29 1 | 4 5 6 | 79 789 3 | | 56 59 46 | 3 7 8 | 2 149 149 | | 7 3 48 | 1 9 2 | 5 48 6 | +-------------+-------------+-------------+ | 68 68 9 | 7 1 3 | 4 5 2 | | 4 1 2 | 9 6 5 | 8 3 7 | | 35 7 35 | 2 8 4 | 6 19 19 | +-------------+-------------+-------------+ | 12 4 68 | 68 3 9 | 17 27 5 | | 13 25 35 | 68 4 7 | 19 26 89 | | 9 68 7 | 5 2 1 | 3 46 48 | +-------------+-------------+-------------+ Reduced R2C9 to 14: +-------------+-------------+-------------+ | 28 29 1 | 4 5 6 | 79 789 3 | | 56 59 46 | 3 7 8 | 2 149 14 | | 7 3 48 | 1 9 2 | 5 48 6 | +-------------+-------------+-------------+ | 68 68 9 | 7 1 3 | 4 5 2 | | 4 1 2 | 9 6 5 | 8 3 7 | | 35 7 35 | 2 8 4 | 6 19 19 | +-------------+-------------+-------------+ | 12 4 68 | 68 3 9 | 17 27 5 | | 13 25 35 | 68 4 7 | 19 26 89 | | 9 68 7 | 5 2 1 | 3 46 48 | +-------------+-------------+-------------+ Reduced R2C8 to 19: +-------------+-------------+-------------+ | 28 29 1 | 4 5 6 | 79 789 3 | | 56 59 46 | 3 7 8 | 2 19 14 | | 7 3 48 | 1 9 2 | 5 48 6 | +-------------+-------------+-------------+ | 68 68 9 | 7 1 3 | 4 5 2 | | 4 1 2 | 9 6 5 | 8 3 7 | | 35 7 35 | 2 8 4 | 6 19 19 | +-------------+-------------+-------------+ | 12 4 68 | 68 3 9 | 17 27 5 | | 13 25 35 | 68 4 7 | 19 26 89 | | 9 68 7 | 5 2 1 | 3 46 48 | +-------------+-------------+-------------+ Reduced R1C8 to 78: +----------+----------+----------+ | 28 29 1 | 4 5 6 | 79 78 3 | | 56 59 46 | 3 7 8 | 2 19 14 | | 7 3 48 | 1 9 2 | 5 48 6 | +----------+----------+----------+ | 68 68 9 | 7 1 3 | 4 5 2 | | 4 1 2 | 9 6 5 | 8 3 7 | | 35 7 35 | 2 8 4 | 6 19 19 | +----------+----------+----------+ | 12 4 68 | 68 3 9 | 17 27 5 | | 13 25 35 | 68 4 7 | 19 26 89 | | 9 68 7 | 5 2 1 | 3 46 48 | +----------+----------+----------+ Bug constructed. No reductions.

by **Jeff** » Thu Dec 01, 2005 6:03 am

MadOverlord wrote:At this point, we have no singleton blocks, so we have to bifurcate the puzzle. In R7, we have 2 ways to go.
Code: Select all
+-------------+-------------+---------------+ Call this | 2 7 3 | 6 8 4 | 19 5 19 | R7A | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+---------------+ | 6 38 7 | 4 5 1 | 2 389 389 | | 48 2 9 | 3 6 7 | 5 18 8+14 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+---------------+ | 1 58 8+25| 7 3 6 | 49 8+49 9+28 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+---------------+

and
Code: Select all
+-------------+-------------+---------------+ And this | 2 7 3 | 6 8 4 | 19 5 19 | R7B | 9 1 4 | 5 7 3 | 8 2 6 | | 58 6 58 | 9 1 2 | 34 7 34 | +-------------+-------------+---------------+ | 6 38 7 | 4 5 1 | 2 389 389 | | 48 2 9 | 3 6 7 | 5 18 8+14 | | 45 35 1 | 8 2 9 | 6 34 7 | +-------------+-------------+---------------+ | 1 58 8+25| 7 3 6 | 49 9+48 8+29 | | 7 9 6 | 2 4 8 | 13 13 5 | | 3 4 28 | 1 9 5 | 7 6 28 | +-------------+-------------+---------------+

2 more logical deductions are possible before this bifurcation step.

In a BUG, each candidate can only appear twice. Since both r6c8 and r8c8 have the candidate 3, therefore r4c8=3+89 and r4c9=8+39.

by **Jeff** » Thu Dec 01, 2005 6:15 am

MadOverlord wrote:When a puzzle contains a BUG, and more than one square in the puzzle has more then 2 possibilities, then BUG possibilities can be removed from squares if, and only if, removing the possibility results in it appearing exactly twice in that square's row, twice in its column, and twice in its block.

Are we confident enough to include this as a corollary in the description of the BUG principle?

by **Nick67** » Thu Dec 01, 2005 7:35 am

As I think Jeff may be hinting, it would be great if we could prove
MadOverlord's reduction rule:

When a puzzle contains a BUG, and more than one square in the puzzle has more then 2
possibilities, then BUG possibilities can be removed from squares if, and only if, removing the
possibility results in it appearing exactly twice in that square's row, twice in its column, and
twice in its block.

Towards that goal, I have a suggestion: let's look at a few cases, and
make reductions without using the rule. Maybe something
in the alternative analysis will give us an insight concerning the rule.

Let me rewind the thread and go back to 1 of Nick70's examples:

Nick70 wrote:Here is an application of the BUG principle with three quadrivalue cells:
Code: Select all
7 2 69 | 5 3 69 | 8 1 4 89 4689 5 | 1 2 48 | 3 69 7 1 3 48 | 69 7 48 | 5 69 2 -------------------+--------------------+------------------- 6 1 2 | 8 4 5 | 9 7 3 5 47 47 | 3 9 1 | 6 2 8 3 89 89 | 7 6 2 | 1 4 5 -------------------+--------------------+------------------- 89 6789 6789 | 4 1 3 | 2 5 69 4 69 3 | 2 5 69 | 7 8 1 2 5 1 | 69 8 7 | 4 3 69

The BUG principle allows us to say that either r2c2=89 or r7c2=69 or r7c3=89. Putting those
together, we can say that r2c2=489, r7c2=679 and r7c3=789. The triple in box 1 then solves the
puzzle.

Nick has already done all the analysis, but I just want to spell it out in full,
to see if it gives us any insights.

Let me start with Nick's statement that "The BUG principle allows us to say that either
r2c2=89 or r7c2=69 or r7c3=89."

From there:
If r2c2=89, then obviously r2c2 <> 6.
If r7c2=69, then r7c2 and r8c2 form a naked pair, and r2c2 <> 6.
If r7c3=89, then r7c1 and r7c3 form a naked pair, and so r8c2=6, and r2c2 <> 6.
So we can conclude that r2c2 <> 6.

Also:
If r2c2=89, then r2c2 and r6c2 form a naked pair, and so r7c2 <> 8.
If r7c2=69, then obviously r7c2 <> 8.
If r7c3=89, then r7c1 and r7c3 form a naked pair, and so r7c2 <> 8.
So we can conclude that r7c2 <> 8.

Finally:
If r2c2=89, then r2c1 and r2c2 form a naked pair, and r1c3=6, and r7c3 <> 6.
If r7c2=69, then r7c2 and r8c2 form a naked pair, and r7c3 <> 6.
If r7c3=89, then obviously r7c3 <> 6.
So we can conclude that r7c3 <> 6.

Does this alternative analysis explain at all why MadOverlord's rule works
for this same puzzle? [Edit: this is a misleading question, because
the rule actually does not seem to work for this puzzle. The rule
does not allow the eliminations described above for r2c2 and r7c3.]

by **Myth Jellies** » Thu Dec 01, 2005 9:02 am

First off, MadOverlord's rule can't be "if and only if". Why? Because MadOverlord's rule basicly requires at least 3 poly-valued cells to come up with any reductions, and there are plenty of ways to make reductions with only two poly-valued cells, as well as other ways to make reductions with 3 or more.

Applying MadOverlord's rule to the puzzle above, the only reduction that I can see is the 8 in r7c2. Am I missing something?

by **Nick67** » Thu Dec 01, 2005 9:39 am

Myth Jellies wrote:Applying MadOverlord's rule to the puzzle above, the only reduction that I can see is the 8 in r7c2. Am I missing something?

No, I believe you are correct. I didn't notice until
you pointed it out: the rule does not seem to work for
Nick70's puzzle above. The rule doesn't permit
the eliminations that Nick found for r2c2 and r7c3.

by **Jeff** » Thu Dec 01, 2005 12:27 pm

Here is another example:

Code: Select all: 1 36 2 | 58 38+5 9 | 7 4 56 4 36 9 | 7 35 2 | 68 58 1 8 7 5 | 6 1 4 | 2 9 3 --------------+---------------+--------------- 9 45 17 | 58 67 36 | 48 13 2 3 45 78 | 2 9 1 | 46+8 58 67+5 6 2 18+7 | 4 78+5 35 | 9 13 57 --------------+---------------+--------------- 7 1 6 | 3 4 8 | 5 2 9 5 9 4 | 1 2 7 | 3 6 8 2 8 3 | 9 56 56 | 1 7 4

r6c3=7 => r6c5=58
r1c5=5 => r1c9=6 => r2c7=8 => r2c8=5 => r5c8=8 => r5c3=7 => r5c9<>7 => r6c9=7 => r6c5=58
r5c7=8 => r5c3=7 => r5c9<>7 => r6c9=7 => r6c5=58
r5c9=5 => r6c9=7 => r6c5=58
Therefore 7 can be excluded from r6c5.

Applying the conjugate analysis to the puzzle above, no reduction is possible. Please tell me what I have done wrong.

The New Sudoku Players' Forum

The BUG (Bivalue Universal Grave) principle

Re: The BUG (Bivalue Universal Grave) principle