The New Sudoku Players' Forum

[MadOverlord]

I think the conjugate rule will have to be tightened up a bit, unless I'm very mistaken. I was running through Dukuso's Top1465 when I ran into a puzzle, #1394, that generates a bad bug reduction. At the point where the BUG can be found, the puzzle and BUG are:

Code: Select all

+----------------+----------------+----------------+
| 69   35   49   | 4569 1    2    | 34   7    8    |
| 269  38   2489 | 469  7    49   | 34   5    1    |
| 7    45   1    | 3    8    45   | 2    9    6    |
+----------------+----------------+----------------+
| 8    6    59   | 7    23   35   | 1    4    29   |
| 4    2    7    | 8    9    1    | 6    3    5    |
| 59   1    3    | 245  24   6    | 7    8    29   |
+----------------+----------------+----------------+
| 3    9    6    | 1    5    7    | 8    2    4    |
| 25   7    245  | 24   6    8    | 9    1    3    |
| 1    48   248  | 249  234  349  | 5    6    7    |
+----------------+----------------+----------------+

+----------+----------+----------+
| 69 35 49 | 56 1  2  | 34 7  8  |
| 26 38 28 | 69 7  49 | 34 5  1  |
| 7  45 1  | 3  8  45 | 2  9  6  |
+----------+----------+----------+
| 8  6  59 | 7  23 35 | 1  4  29 |
| 4  2  7  | 8  9  1  | 6  3  5  |
| 59 1  3  | 45 24 6  | 7  8  29 |
+----------+----------+----------+
| 3  9  6  | 1  5  7  | 8  2  4  |
| 25 7  45 | 24 6  8  | 9  1  3  |
| 1  48 28 | 29 34 39 | 5  6  7  |
+----------+----------+----------+

And the Susser reports:

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

R9C6=<39>, R9C5=<34>, R9C4=<29>, R9C3=<28>, R8C3=<45>, R6C4=<45>, R2C3=<28>, R2C1=<26>, R1C4=<56> and R2C4=<69>.

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.

R9C4 - removing <2> from <249> leaving <49>.
R9C3 - removing <2> from <248> leaving <48>.

Well, it turns out R9C3=2 in the final solution, so the conjugate rule has a problem.

Looking at the puzzle, you'll note that there are multiple blocks that contain more then 2 BUG squares. I am wondering if there is a limitation that needs to be enforced.

I can think of a couple, but have no idea if they are theoretically sound. One would be no more than 2 BUG squares in any group, but there are other BUG patterns in top1465 that break this rule but solve ok (this might just be luck, though)

I do note one feature, though: the conjugate being removed from R9C3 (2) is only present in BUG squares in C3. Could that be the restriction that is needed?

There were 3 puzzles in Top1465 that had 8-square BUGs, so I looked at them.

Consider Top1465 #1329, which gets to this state:

Code: Select all

+----------------+----------------+----------------+
| 7    3    9    | 18   18   2    | 5    6    4    |
| 68   16   18   | 5    4    7    | 2    3    9    |
| 2    5    4    | 6    9    3    | 8    1    7    |
+----------------+----------------+----------------+
| 456  67   23   | 47   23   9    | 1    8    56   |
| 56   679  123  | 27   123  8    | 369  4    2356 |
| 48   19   1238 | 124  5    6    | 39   7    23   |
+----------------+----------------+----------------+
| 1    2    6    | 3    7    5    | 4    9    8    |
| 39   4    5    | 89   68   1    | 7    2    36   |
| 39   8    7    | 29   26   4    | 36   5    1    |
+----------------+----------------+----------------+

+----------+----------+----------+
| 7  3  9  | 18 18 2  | 5  6  4  |
| 68 16 18 | 5  4  7  | 2  3  9  |
| 2  5  4  | 6  9  3  | 8  1  7  |
+----------+----------+----------+
| 45 67 23 | 47 23 9  | 1  8  56 |
| 56 79 13 | 27 13 8  | 69 4  25 |
| 48 19 28 | 14 5  6  | 39 7  23 |
+----------+----------+----------+
| 1  2  6  | 3  7  5  | 4  9  8  |
| 39 4  5  | 89 68 1  | 7  2  36 |
| 39 8  7  | 29 26 4  | 36 5  1  |
+----------+----------+----------+

Here we have 5 BUG squares in R5, but the reduction of 2 from R6C3 works, and only one other square in each of its r/c/b are BUG squares.

Ditto Top1465 #75

Code: Select all

+----------------+----------------+----------------+
| 9    6    8    | 24   7    24   | 3    5    1    |
| 57   3    4    | 8    1    56   | 9    2    67   |
| 57   1    2    | 56   3    9    | 4    67   8    |
+----------------+----------------+----------------+
| 13   28   9    | 247  248  1247 | 6    38   5    |
| 4    7    56   | 3    89   56   | 28   1    29   |
| 13   28   56   | 56   289  12   | 7    389  4    |
+----------------+----------------+----------------+
| 2    59   1    | 79   6    38   | 58   4    37   |
| 8    59   3    | 1    24   247  | 25   67   2679 |
| 6    4    7    | 29   5    38   | 1    89   239  |
+----------------+----------------+----------------+

+----------+----------+----------+
| 9  6  8  | 24 7  24 | 3  5  1  |
| 57 3  4  | 8  1  56 | 9  2  67 |
| 57 1  2  | 56 3  9  | 4  67 8  |
+----------+----------+----------+
| 13 28 9  | 47 24 17 | 6  38 5  |
| 4  7  56 | 3  89 56 | 28 1  29 |
| 13 28 56 | 56 89 12 | 7  39 4  |
+----------+----------+----------+
| 2  59 1  | 79 6  38 | 58 4  37 |
| 8  59 3  | 1  24 47 | 25 67 69 |
| 6  4  7  | 29 5  38 | 1  89 23 |
+----------+----------+----------+

Reducing the 8 from R6C5 only hits one BUG and one non-BUG in the r/c/b

And finally, #1265...

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  |
+----------------+----------------+----------------+

+----------+----------+----------+
| 7  49 6  | 5  1  3  | 48 89 2  |
| 14 13 2  | 8  6  49 | 7  5  39 |
| 5  39 8  | 7  49 2  | 34 1  6  |
+----------+----------+----------+
| 3  6  7  | 9  2  5  | 18 48 14 |
| 9  2  5  | 4  8  1  | 36 67 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  37 47 |
+----------+----------+----------+

Reducing the 3 from R9C8 and the 4 from R9C9 also just hit one BUG and non-BUG.

I think this may be the restriction, it sounds reasonable to me, but I don't have the theoretical knowledge to say for sure.

[dukuso]

seems to me, that the "BUG" relies on the fact that there is a unique solution. It won't work when there are 2 or more solutions ?

[MadOverlord]

Well, the puzzle has only one solution, and it has a valid "BUG" reduction. It's just that the inferences one can make from the BUG are apparently slightly more limited than thought.

In your Top1465 puzzles, useful BUGs crop up 20 times -- one of which is a "bad" reduction that I'm trying to find a patch for.

[dukuso]

I wouldn't like to rate by any techniques which relies on the
fact that there is a unique solution, though.

This would be _too_ sudoku specific, while I like to
see sudokus as a subclass -and related to- other
constraint problems.

It could be just a temporary fashion that people enjoy
sudokus with one solution this season, while maybe
next year they will prefer sudokus with 7 solutions ?

[Myth Jellies]

dukuso,

The BUG principle definitely relies on the uniqueness of the puzzle solution.

BUG and other multi-solution pattern avoidance techniques (uniqueness patterns) are usually easier to spot than naked triples; and often can lead to puzzle solutions without resorting to any further advanced techniques. I can't imagine why anyone would purposely avoid using them...or am I just missing the joke.

Seriously, seven-solution sudokus suck shaggy soursops.

[Nick70]

Well, the puzzle has only one solution, and it has a valid "BUG" reduction. It's just that the inferences one can make from the BUG are apparently slightly more limited than thought.

Just to clarify: the inferences, as outlined in the first post of this thread, are valid and proven.

What cannot be applied is the shortcut you proposed.

[Nick67]

I think the conjugate rule will have to be tightened up a bit,
unless I'm very mistaken. I was running through Dukuso's Top1465
when I ran into a puzzle, #1394, that generates a bad bug reduction.

MadOverlord,

The wording in your post leads me to think you
might not have seen the couple of posts just prior to yours.
These posts (at the end of page 2 of this thread) also suggest
that the conjugate rule is not quite right.

[MadOverlord]

MadOverlord,

The wording in your post leads me to think you
might not have seen the couple of posts just prior to yours.
These posts (at the end of page 2 of this thread) also suggest
that the conjugate rule is not quite right.

I neglected to reply to that posting (the one about finding a reduction that the conjugate rule doesn't find).

I agree that it is entirely possible -- probably certain -- that there will be some possible BUG reductions that the conjugate rule doesn't catch. But the problem with the difficult reductions like the one in the post you mention is that they get into long logical chains; they are in effect forcing chains or tabling.

This is all fine and good, but not IMHO all that helpful. The nice thing about the conjugate rule is that it is easy to execute. It's something that's reasonable for a human to actually do when solving the puzzle. That's why I'm interested in it as a basic way of exploiting BUGs.

Just to clarify: the inferences, as outlined in the first post of this thread, are valid and proven.

What cannot be applied is the shortcut you proposed.

Well, clearly, since a counter-example has been found. But that does not answer the question: is there a simple provably-correct patch that can "fix" the conjugate rule?

Are there extensions to it that will include more of the possible BUG reductions?

[Nick67]

MadOverlord,

Thanks very much for your reply. You bring up
excellent points, and I hope that you do find a
good fix (or alternative) for the conjugate rule.

[Myth Jellies]

MadOverlord,

While I think that the BUG ORing scheme can be pretty much eyeballed for 3 or less poly-valued cells; that degenerates rapidly as you add more. I fully agree with you that we need a scheme such as yours for cases with a large number of choices. I have no problem with such a scheme missing some otherwise easy to spot reductions, so long as it is always correct when it does come up with one.

That being said, I think I am a bit confused by your rule. When you first introduced it, you only appeared to apply it to rows, columns, or boxes that contained another poly-valued cell. This allowed you to apply your reductions to cells which only shared a house with one other poly-valued cell. Later on, you codified it as follows...

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.

Which in effect, prevented you from successfully removing a BUG possibility unless a poly-valued cell shared a row, column, and box with other poly-valued cells (i.e. at least two other poly-valued cells).

So, first, I am curious about that change. Second, I am wondering if you have any thoughts as regards to the reason why you would expect your rule to work. Is there any theory germinating, or was this rule the result of a bunch of empirical data? If we have an idea to work from, it might be easier to come up with a fix.

[MadOverlord]

MadOverlord,

While I think that the BUG ORing scheme can be pretty much eyeballed for 3 or less poly-valued cells; that degenerates rapidly as you add more. I fully agree with you that we need a scheme such as yours for cases with a large number of choices. I have no problem with such a scheme missing some otherwise easy to spot reductions, so long as it is always correct when it does come up with one.

Thanks

That being said, I think I am a bit confused by your rule. When you first introduced it, you only appeared to apply it to rows, columns, or boxes that contained another poly-valued cell. This allowed you to apply your reductions to cells which only shared a house with one other poly-valued cell. Later on, you codified it as follows...

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.

Which in effect, prevented you from successfully removing a BUG possibility unless a poly-valued cell shared a row, column, and box with other poly-valued cells (i.e. at least two other poly-valued cells).

Although I didn't realize it at the time, this is indeed the effect. This leads me to believe there may be several "subrules" you can use for elimination.

Defining a BUG possibility as a possibility in a polysquare that remains when it is reduce to a BUG, then I originally had 2 matching rules.

* If there was only one polysquare, eliminate all the BUG possibilities from it.

* If more than one, then you can remove each BUG possibility that, when removed, left the row/col/block conjugate in that possibility.

So, first, I am curious about that change. Second, I am wondering if you have any thoughts as regards to the reason why you would expect your rule to work. Is there any theory germinating, or was this rule the result of a bunch of empirical data? If we have an idea to work from, it might be easier to come up with a fix.

I am not a theoretical person, I'm much more the experimentalist. I have a lot of trouble with the logical theory behind these rules. What I do have a knack for is (1) that, once I understand them, I can express them simply (both to myself, and usually to other people) and (2) in the process of coming to understand them, I often ask "the right questions" that lead to other people coming up with improved insights.

In this case, once I'd understood about how to do BUG reductions, I started looking for easy ways to draw inferences from the BUG. The "since one of the non-bug possibility sets must be true, anything true of all of them must be true" didn't strike me as super-helpful, since they you're often into chains and doing tabling-style verities and veracities. I wanted something simpler that people could actually use.

As a side note, the description of BUG construction in the first post is, I believe, overly restrictive; it seems to say that you can only do a LBM if the square has no buddies (row/col/block) that are polysquares, but AFAICT it is quite possible to create them as long as you can find a row/col/block that contains only one polysquare (though you often find no moves that keep the BUG'ness and can thus quit). Maybe I'm missing something, but anyway.

By looking at a bunch of puzzles, I came up with the conjugate rule, which I then ran through a bunch of puzzles without it screwing up. But then, later on, run dusoku's 1465 list through found one screwup, which I posted. So clearly there is either an additional restriction to the conjugate rule (for example:only one other polysquare in the row/col/block), or it is itself a flawed-subset of a more comprehensive rule.

I am currently investigating some possibilities. One that comes to mind is that perhaps there is a superset rule to the effect that "the bug possibility must appear in n+1 squares in its row/col/block, where n is the number of other polysquares in the row/col/block"

This would be a superset of both of the rules above, and would catch the "conjugate in 2 other polysquares" glitch. It would also permit removing the all BUG possibilities in multiple squares that didn't share a row/col/block.

Will it work? No idea until I run it through a sieve of puzzles. Even then, not sure, which is why I turn to the theoretician/logicians. In previous discussions (such as on Unique Rectangles) I've gotten a lot of great "that won't work, and this is why" feedback. I'm hoping for some here.

best
R

[Jeff]

As a side note, the description of BUG construction in the first post is, I believe, overly restrictive; it seems to say that you can only do a LBM if the square has no buddies (row/col/block) that are polysquares, but AFAICT it is quite possible to create them as long as you can find a row/col/block that contains only one polysquare (though you often find no moves that keep the BUG'ness and can thus quit). Maybe I'm missing something, but anyway.

Thanks MadOverlord, now that you have mentioned it, I can't agree more that the description needs to be updated. Unfortunately, I am the only one who can edit the first post. Worse still, I am not a theoretical person nor capable of expressing things simply especially when it comes to rules and definitions. Nevertheless, I am a technical person who likes to put things correctly and in the right place. Hence, I am heavily relying on input from you or anyone to add or correct any statements as appropriate. Appended herewith is the current statement or are there any others. Please don't hesitate to offer your opinion, everyone, and I thank you in anticipation.

A Local Bivalue Move or Localized BUG Move (LBM) is the selection of two candidates from a poly-valued cell that cause the row, column, and box containing that cell to have all bivalue cells and to have all candidates in that row, column, or box show up exactly twice.

[MadOverlord]

Here is what I *think* it should say; a change of an and to an or:

A Local Bivalue Move or Localized BUG Move (LBM) is the selection of two candidates from a poly-valued cell that cause the row, column, or box containing that cell to have all bivalue cells and to have all candidates in that row, column, or box show up exactly twice.

In other words, you have to find a r/c/b that has a single poly-value in it, and reduce it to all-bivalues, all-conjugate (2-candidate) group.

However, I would not update the explanation until the Lords of Logic have given us their opinion.

For example, if you can construct a BUG where each move DOES consume a row, a column, or a block (in other words, each poly-valued cell has no "buddy" that is a poly-valued cell), then you may be able to make more inferences -- or make them more easily. That might, for example, be the general case of a single poly-value BUG, where you can eliminate both of the BUG possibilities immediately.

[Jeff]

MadOverlord, another thing, I don't know why you have ceased using the '+' notation for the BUG grid. Its is so useful and space saving.
My only comment is that the BUG candidates should be the prefix enabling the BUG to be more easily read. That is:

Code: Select all

+-----------------+------------------+----------------+
| 69   35   49    | 56+49 1     2    | 34   7    8    |
| 26+9 38   28+49 | 69+4  7     49   | 34   5    1    |
| 7    45   1     | 3     8     45   | 2    9    6    |
+-----------------+------------------+----------------+
| 8    6    59    | 7     23    35   | 1    4    29   |
| 4    2    7     | 8     9     1    | 6    3    5    |
| 59   1    3     | 45+2  24    6    | 7    8    29   |
+-----------------+------------------+----------------+
| 3    9    6     | 1     5     7    | 8    2    4    |
| 25   7    45+2  | 24    6     8    | 9    1    3    |
| 1    48   28+4  | 29+4  34+2  39+4 | 5    6    7    |
+-----------------+------------------+----------------+

Instead of

Code: Select all

+----------------+----------------+----------------+
| 69   35   49   | 4569 1    2    | 34   7    8    |
| 269  38   2489 | 469  7    49   | 34   5    1    |
| 7    45   1    | 3    8    45   | 2    9    6    |
+----------------+----------------+----------------+
| 8    6    59   | 7    23   35   | 1    4    29   |
| 4    2    7    | 8    9    1    | 6    3    5    |
| 59   1    3    | 245  24   6    | 7    8    29   |
+----------------+----------------+----------------+
| 3    9    6    | 1    5    7    | 8    2    4    |
| 25   7    245  | 24   6    8    | 9    1    3    |
| 1    48   248  | 249  234  349  | 5    6    7    |
+----------------+----------------+----------------+

+----------+----------+----------+
| 69 35 49 | 56 1  2  | 34 7  8  |
| 26 38 28 | 69 7  49 | 34 5  1  |
| 7  45 1  | 3  8  45 | 2  9  6  |
+----------+----------+----------+
| 8  6  59 | 7  23 35 | 1  4  29 |
| 4  2  7  | 8  9  1  | 6  3  5  |
| 59 1  3  | 45 24 6  | 7  8  29 |
+----------+----------+----------+
| 3  9  6  | 1  5  7  | 8  2  4  |
| 25 7  45 | 24 6  8  | 9  1  3  |
| 1  48 28 | 29 34 39 | 5  6  7  |
+----------+----------+----------+

[gaby]

I have added these terms to the online dictionary, but I'd appreciate somebody else casting an eye over them:

http://vanhegan.net/sudoku/dictionary.php?term=bivalue%20universal%20grave
http://vanhegan.net/sudoku/dictionary.php?term=local%20bivalue%20move

Gaby