The New Sudoku Players' Forum

[Roy McCoy]

Code: Select all

5 6 7 | 2 4 . | . 8 1
8 . . | 6 1 . | 4 5 7
. . 4 | 5 7 8 | . 6 2
------+-------+------
. 8 . | 1 2 . | 7 3 6
2 7 3 | 9 8 6 | 5 1 4
6 . . | 7 3 . | 8 2 9
------+-------+------
3 5 6 | 4 9 2 | 1 7 8
7 9 8 | 3 6 1 | 2 4 5
. . . | 8 5 7 | 6 9 3

Both my Bosnian lady colleague and I got stuck at this same point today, her in her head and me with notes. Where do we go from here? For me this is a classic point where I plunk in a guess with a pencil and then erase if I'm wrong. Thanks.

[JasonLion]

That is a BUG+1, see http://www.sudopedia.org/wiki/Bivalue_Universal_Grave for details. Their description isn't all that readable, so feel free to ask for clarification if you need it.

[Roy McCoy]

You're right. I thought I would understand it but I don't.

Maybe I would have if I hadn't been initially confused by "the result is a placement". I would have been less confused, or not at all, if there had been a link on "placement", or if it had said, more suggestively, "an immediate placement".

More confusing, however, and perhaps what you were thinking of, was "If r1c5 is not 9, then we obtain the BUG pattern." But the BUG was just described as the situation in which "each unsolved cell has two candidates, and in each row, column and box constraint, each candidate value occurs exactly twice." If r1c5 is 5 or 7, I don't see how a BUG results from this. If it is 5, for example, either you stop right there and there's no immediately visible BUG (at least as far as I can see), or you make r1c4 a 9, r1c3 a 1, etc. I'm not worried about fully understanding precisely why no BUG can exist in a valid sudoku (why does the wiki capitalize "Sudoku", by the way?) - right now I just don't see the BUG.

Thanks.

[JasonLion]

First, a quick reminder. There are BUGs and there are BUG+1s. A BUG can't actually occur in a valid puzzle, a BUG+1 can.

"the result is a placement" isn't the clearest bit of writing. What that means is that as soon as you discover that you have a BUG+1 you know that you can place the extra candidate as a digit in the cell that has three candidates. The digit which goes there is the one that occurs as a candidate an odd number of times in each house it is in.

In the BUG+1 example at Sudopedia, the 9 in R1C5 is the extra candidate. If that cell couldn't contain a 9, for some unknown reason, there would be a BUG (think of the puzzle before anything else is actually entered into the cell, just with the candidate 9 removed). In your puzzle, the candidate/pencil mark 1 in R9C2 is the extra candidate. If that 1 was somehow not allowed you would be left with a BUG. Since the other two candidates in R9C2 are part of the BUG, and BUGs can't occur, and none of the other cells can contain anything that would invalidate the BUG, we can immediately place a 1 in R9C2, because that is the only way to avoid the BUG.

Deadly patterns do get a little confusing sometimes. If, in the Sudopedia puzzle, we were to place a 5 in R1C5 as a clue the puzzle would only have one solution, because clues can't be swapped out for another digit. As long as none of the cells in the BUG are clues, the BUG still lurks in the puzzle and forces there to be two solutions, even if some of the digits have been placed. If you have done all of your solving up to that point correctly, none of those digits will have been placed. To place a digit in a true BUG, you would have to pick between the two solutions. Since both solutions are valid you shouldn't have picked between them unless you made a mistake.''

One simple way to think about this is to work with a simpler example. Consider a unique rectangle, which is the simplest possible kind of deadly pattern (and fairly BUG like). A UR has four cells in two row, two columns, and two boxes that share two candidates. For example:

Code: Select all

12 . . | 12 . . | . . .
12 . . | 12 . . | . . .
 . . . |  . . . | . . .
-------|--------|------
 . . . |  . . . | . . .
 . . . |  . . . | . . .
 . . . |  . . . | . . .
-------|--------|------
 . . . |  . . . | . . .
 . . . |  . . . | . . .
 . . . |  . . . | . . .

R12C14 can contain:

Code: Select all

1 . . 2
2 . . 1

or it can contain:

Code: Select all

2 . . 1
1 . . 2

regardless of what the other cells contain. Both of those patterns provide a 1 and a 2 in each row, column, and box involved with those two cells. So it doesn't really matter if we have already placed some of those 1s and 2s, we could still erase them and put back the alternate pattern and the puzzle would still be valid in every way except that it would have two solutions. A BUG is just like that, except it usually has more cells and more digits involved in it.

Hopefully that helps a little.

Sudoku is a name. Names are typically capitalized.

[Roy McCoy]

First, a quick reminder. There are BUGs and there are BUG+1s. A BUG can't actually occur in a valid puzzle, a BUG+1 can.

Yes, I got that.

"the result is a placement" isn't the clearest bit of writing. What that means is that as soon as you discover that you have a BUG+1 you know that you can place the extra candidate as a digit in the cell that has three candidates.

Got that too. That's why I thought it should say immediate placement.

In the BUG+1 example at Sudopedia, the 9 in R1C5 is the extra candidate. If that cell couldn't contain a 9, for some unknown reason, there would be a BUG (think of the puzzle before anything else is actually entered into the cell, just with the candidate 9 removed).

Yes, of course. Another senior moment for me, I'm afraid. It simply didn't occur to me to try that, or I would of course have seen. I just mentally plunked the 5 or 7 in, willy-nilly.

If, in the Sudopedia puzzle, we were to place a 5 in R1C5 as a clue the puzzle would only have one solution, because clues can't be swapped out for another digit. As long as none of the cells in the BUG are clues, the BUG still lurks in the puzzle and forces there to be two solutions, even if some of the digits have been placed.

You lost me there. I'd think there wouldn't be any solution if there were a 5 in R1C5 - i.e., it would be an erroneous clue.

This did help, thanks. But how is "Sudoku" a name more than "crossword puzzle" is, for example? If it were a registered trademark (like ®Scrabble) and had a bunch of lawyers protecting it or something, I would understand, but without such an understanding it looks about as generic as "anagram" or "acrostic" to me.

[JasonLion]

If, in the Sudopedia puzzle, we were to place a 5 in R1C5 as a clue the puzzle would only have one solution, because clues can't be swapped out for another digit. As long as none of the cells in the BUG are clues, the BUG still lurks in the puzzle and forces there to be two solutions, even if some of the digits have been placed.

You lost me there. I'd think there wouldn't be any solution if there were a 5 in R1C5 - i.e., it would be an erroneous clue.

Hum, that is true, though that doesn't really change the point of what I was trying to say. The point I was trying for was that you can fill in cells in the BUG with digits and the bug will still be there.

The part of that which relates to clues comes up when you are making puzzles out of filled in solution grids. One of the several ways that is done is to search for all of the unavoidable sets and make at least one of their cells a clue. BUGs are a kind of unavoidable set, a set of cells in a solved grid that must have at least one of cell from the set made a clue before you will have a valid puzzle. All of which is about BUGs but not about BUG+1s, so it looks like I slipped up despite my own reminder.

This did help, thanks. But how is "Sudoku" a name more than "crossword puzzle" is, for example? If it were a registered trademark (like ®Scrabble) and had a bunch of lawyers protecting it or something, I would understand, but without such an understanding it looks about as generic as "anagram" or "acrostic" to me.

Sudoku is a registered trademark in Japan for the name of a specific kind of puzzle from Nikoli. In the rest of the world it is well on it's way to becoming a generic term, like anagram. The line between trademarks and generic terms is often vague, with many things that started off being trademarks with leading capitals eventually becoming generic terms in all lowercase. Another well known case where that is happening is with Kleenex, the brand name, vs kleenex the generic term for tissues for blowing your nose, both of which are in common usage. For the moment both Kleenex and Sudoku are still close enough to their trademarked name status that they are generally capitalized, but close enough to generic term that you see them in lowercase often enough. For now the Sudoku community seems to capitalize Sudoku quite a bit more often than not. But that may well change in ten or twenty years.

[RW]

"the result is a placement" isn't the clearest bit of writing. What that means is that as soon as you discover that you have a BUG+1 you know that you can place the extra candidate as a digit in the cell that has three candidates.

Got that too. That's why I thought it should say immediate placement.

The sentence right before it in Sudopedia is a lot more important:

"The simplest form is BUG+1, where two BUG candidates may be immediately eliminated from the one cell with extra candidates.

This is what you actually do when you eliminate candidates using a BUG+1. It might well be that you have 2 extra candidates in the +1 cell, in that case there is no immediate placement.

If, in the Sudopedia puzzle, we were to place a 5 in R1C5 as a clue the puzzle would only have one solution, because clues can't be swapped out for another digit. As long as none of the cells in the BUG are clues, the BUG still lurks in the puzzle and forces there to be two solutions, even if some of the digits have been placed.

You lost me there. I'd think there wouldn't be any solution if there were a 5 in R1C5 - i.e., it would be an erroneous clue.

This is perhaps the most important thing to understand about uniqueness techniques. Whatever you do you cannot get a unique puzzle into a state with multiple solutions, because then it would have had multiple solutions from the start. Way too often uniqueness techniques are described as " if cell A was X, then you end up with multiple solutions". The correct description is "if A was X, then you cannot find a unique solution, you can only find 0 or multiple solutions". Since we know that a valid puzzle cannot have multiple solutions no matter what we do, we can rule out the second option and conlude that the puzzle cannot have a solution where cell A is X.

RW

[Roy McCoy]

Jason:

The point I was trying for was that you can fill in cells in the BUG with digits and the bug will still be there.

I get that, I think. But you shouldn't fill in the BUG cells, right? Except for the particular BUG+1 cell, I mean. I think I also get "unavoidable set", a curious shorthand expression for what you describe, and what a BUG is an example of.

Sudoku is a registered trademark [...]

Oh, okay. Didn't know that. They'd better have some scary lawyers if they want people to keep capitalizing it, though.

But that may well change in ten or twenty years.

I doubt it will be that long. I imagine it's already been happening, that the proportion of cases of lowercase "sudoku" have been increasing year by year and will continue to do so. I was going to check the number of instances of "Sudoku" vs. "sudoku" on a page of a hundred Google finds, but this was too complicated by names of books and lists, beginnings of sentences etc., so I abandoned the idea of checking in this way. Actually I could still do it. First Google find page, discounting cases such as those mentioned... I counted 58 "Sudoku" and 152 "sudoku". There were some dubious cases, where you didn't know if "Sudoku" was the name of a game program or not, but even allowing for different calculations it's still clear that the lowercase form is at least twice as common as the uppercase one. In some of the case of "Sudoku", "Crossword" is also capitalized - which is certainly unorthodox and may even be considered incorrect. I myself will ignore the trademark, which seems kind of bogus anyway since as I understand it the puzzle form didn't really originate in Japan anyway.

RW:

It might well be that you have 2 extra candidates in the +1 cell, in that case there is no immediate placement.

I don't suppose you could provide an example of that, could you? I don't succeed in imagining such a case.

The correct description is "if A was [even more correct: were :-] X, then you cannot find a unique solution, you can only find 0 or multiple solutions". Since we know that a valid puzzle cannot have multiple solutions no matter what we do, we can rule out the second option and conlude that the puzzle cannot have a solution where cell A is X.

But we have to rule out the first option also, so I'm thinking this should perhaps be more like "has to have a solution and cannot have more than one, we can rule out both options". Also, don't I remember that it's contested by some that a valid puzzle cannot have multiple solutions? I myself would say it couldn't, but I'm no sudoku authority so I don't suppose my opinion counts for much.


Thanks!

[docjohn]

There's an XY wing for the number 1 between r2c3 (pivot), r3c1, and r9c3. This allows you to elminate the number 1
in r9c1.

There's also a W wing (r6c2, r9c1 linked to r3c1, r3,2) that allows you to elimate the 4's in r4c1 and r9c2.

[JasonLion]

Yes indeed, the Uniqueness Controversy. Most people assume that all puzzles should have a single unique solution, but it is far from universally agreed. Common usage on this forum is that puzzles have a unique solution unless otherwise specified.

The rule for how Sudoku puzzles work goes back to Number Place puzzles, which were modern Sudoku puzzles in every way except for lacking symmetry (which is also not universally agreed to). The name "Sudoku" was created by Nikoli and trademarked right from the start. They have actively defended that trademark in Japan quite successfully. They didn't attempt to trademark it anywhere else in the world until after it had already entered common usage, and so were unable to get trademark protection anywhere else that I know of.

[RW]

It might well be that you have 2 extra candidates in the +1 cell, in that case there is no immediate placement.

I don't suppose you could provide an example of that, could you? I don't succeed in imagining such a case.

Here's one example:

Code: Select all

 *-----------------------------------------------------------*
 | 2     5     9     | 36    8     1     | 7     46    34    |
 | 3     8     7     | 56    4     9     | 12    15+26 26    |
 | 4     1     6     | 35    2     7     | 38    58    9     |
 |-------------------+-------------------+-------------------|
 | 7     2     4     | 1     6     3     | 5     9     8     |
 | 1     6     3     | 9     5     8     | 4     27    27    |
 | 5     9     8     | 2     7     4     | 13    16    36    |
 |-------------------+-------------------+-------------------|
 | 6     3     2     | 8     1     5     | 9     47    47    |
 | 8     4     1     | 7     9     2     | 6     3     5     |
 | 9     7     5     | 4     3     6     | 28    28    1     |
 *-----------------------------------------------------------*

The BUG candidates 1 and 5 can be eliminated. This leads to immediate placements, but not in the +1 cell.

The correct description is "if A was X, then you cannot find a unique solution, you can only find 0 or multiple solutions". Since we know that a valid puzzle cannot have multiple solutions no matter what we do, we can rule out the second option and conclude that the puzzle cannot have a solution where cell A is X.

But we have to rule out the first option also, so I'm thinking this should perhaps be more like "has to have a solution and cannot have more than one, we can rule out both options".

There is one difference between the first option and the second. No matter what you do (except removing given clues), you cannot get a unique puzzle into a state with multiple solutions, but you can get it into a state with 0 solutions by removing the wrong candidate or assigning a wrong digit. This is why the first option (0 solutions) is always true and the second (multiple solutions) is false when using uniqueness logic in a valid puzzle. The eliminated candidates would lead to a situation with 0 solutions, not a situation with multiple solutions. But of course, you are also right that the reason why we can do the elimination is that we know the puzzle must have a solution. But this reasoning is behind every single elimination or placement we make in a puzzle and I don't think it needs to be explained separately in a technique guide.

RW

[Roy McCoy]

docjohn:

There's an XY wing for the number 1 between r2c3 (pivot), r3c1, and r9c3. This allows you to elminate the number 1
in r9c1.
There's also a W wing (r6c2, r9c1 linked to r3c1, r3,2) that allows you to elimate the 4's in r4c1 and r9c2.

Great! These are both new to me, but I've read the explanations at Sudopedia and think I understand them. Whether I actually find any in the future is another question, but I hope I will.

Thanks, also to RW for his further explanations.

[Pat]

Way too often uniqueness techniques are described as

if cell A was X,
then you end up with multiple solutions

The correct description is

if A was X,
then you cannot find a unique solution,
you can only find 0 or multiple solutions

Since we know that a valid puzzle cannot have multiple solutions no matter what we do,
we can rule out the 2nd option
and conlude that the puzzle cannot have a solution where cell A is X.

or i may phrase it thus --

if {X},
then the number of answers is even ( 0,2,... )


we choose to assume that the puzzle has excatly 1 answer,
so we can rule out the even-number-of-answers
and conlude that the puzzle cannot have an answer where {X}.

[RW]

or i may phrase it thus --

if {X},
then the number of answers is even ( 0,2,... )


we choose to assume that the puzzle has excatly 1 answer,
so we can rule out the even-number-of-answers
and conlude that the puzzle cannot have an answer where {X}.

In case of a multisolution puzzle, it might very well have an odd number of solutions. Even some pretty common deadly patterns have an odd number of solutions, such as the overlapping UR's with 3 solutions:

Code: Select all

ab | ab
ab | abcY ac
---+---------
   | ac   ac

if abcY<>Y, then the pattern can be solved in 3 ways

RW

[Pat]

In case of a multisolution puzzle,
it might very well have an odd number of solutions.

right

we just had this discussion in the other forum

by assuming the number of answers is odd,
we exclude some possibilities

-- which for a puzzle with more than one answer,
may create the appearance of a 1-answer puzzle
and may create the appearance of a 0-answer puzzle