DoubleBUG

Advanced methods and approaches for solving Sudoku puzzles

DoubleBUG

Postby JRL » Tue Jul 06, 2021 2:43 pm

I have just joined this blog and this is my first post. If I don't do this correctly please, somebody, let me know.

I have spent 6 months intensively studying BUG. My interest arose from a chance situation and I have developed the technique into something much more useful than just a final way of solving a small number of boards. I have called this DoubleBUG, and I now use it regularly after the first tidying of the board to where only advanced techniques will take you further. It certainly doesn't solve everything but where it can be applied it gives solutions in a rather different way.

Andrew Stuart has kindly included my study and some preamble on his SudokuWiki site - and my PDF can be downloaded. It is fairly densly written and comes with 8 examples in detail. There are bound to be many errors still present, and readers may well want to fault aspects of my logic. It can be accessed directly at: https://www.sudokuwiki.org/Double_BUG

I look forward to the community studying this and commenting and discussing - and hopefully refining it a lot. It is written from the point of view of a pencil-and-paper (and eraser) player, which I am.

JRL
JRL
 
Posts: 7
Joined: 29 March 2021

Re: DoubleBUG

Postby JRL » Sun Aug 01, 2021 4:46 am

i was pleased quite a number of people had viewed my posting, though I can have no idea of how many downloaded the full document from the Andrew Stuart's site. I was hoping that at least one person would challenge me on this proposal - or even denounce it as fraud - or perhaps say they had managed to reproduce the technique I outlined. I think perhaps I made my document rather forbidding, giving the impression that the technique was very complicated, whereas in fact it is very simple to identify Bug Candidates, and fairly simple to resolve those to a solution of the board. Of course, by no means all boards allow this technique, in common with all advanced techniques.
I am certain there are holes in my logic, some of which I can see myself, but there are experienced Sudoku players on this Forum, some of whom have discussed aspects of BUG in a somewhat similar way. They would really be able to shed new light on what I propose. Just one person would do, and I would engage in full discussion to try to fully understand my technique, and improve it where it is faulty.

Here is a new example, taken from a board that was declared "Extreme", though was really just quite hard! The board below is after the basic steps 1-6 of the Andrew Stuart solver, though I did this easily myself with pencil/paper.

7....6..398..........2...71.2.3.8.571..4..2....5.7.......95....5...67.4..3.......

+--------------+--------------+--------------+
| 7 14 12 | 5 48 6 | 489 29 3 |
| 9 8 23(6) | 7 34 1 | 456 26 4(5) |
| 46 5 36 | 2 3(4)8 9 | 468 7 1 |
+--------------+--------------+--------------+
| 46 2 69 | 3 1 8 | 49 5 7 |
| 1 7 8 | 4 9 5 | 2 3 6 |
| 3 49 5 | 6 7 2 | 1 8 49 |
+--------------+--------------+--------------+
| 2 6 4 | 9 5 3 | 7 1 8 |
| 5 19 19 | 8 6 7 | 3 4 2 |
| 8 3 7 | 1 2 4 | 56(9) 69 59 |
+--------------+--------------+--------------+

I have highlighted the Bug Candidates (BC) with (). If someone can tell me how to put the board in with fixed width characters I should be pleased.
There are FOUR boxes with multi-values - 1, 2, 3, 9. My identification of the BCs follows the rules in my proposal and in each of these boxes there is just 1 number that appears most frequently -
Box 1 There are 3 6s so B3=6; Box 2 There are 3 4s so C5=4; Box 3 There are 4 4s so B9=5 (in this box one of the tri-values must be 4, so B9 can be designated 5); Box 9 There are 3 9s so J7=9. See the basic BC identification in my proposal.
There are probably several pathways to resolve these four BC values. One way is:
B9=5 to J9=9, along with J7=9, results in J8=6 ... B8=2 ... A8=9.
Then the other two BCs:
C5=4 ... C1=6 ... D1=4 ... D7=9 ... A7 not-equal 9 ... A8=9
B3=6 ...B8=2 ... A8=9.
Each BC resolves to A8=9. And the board resolves immediately.
For reference, the Andrew Stuart solver requires a Simple Colouring, followed by an XY-Chain to resolve from the above point.

I hope I have made no typing error - and that some Forum members will be encouraged to study this example of the DoubleBUG technique
JRL
 
Posts: 7
Joined: 29 March 2021

Re: DoubleBUG

Postby Mathimagics » Sun Aug 01, 2021 8:45 am

You can use "code" tags to get a fixed-width font.
Code: Select all
+--------------+--------------+--------------+
| 7   14  12   | 5   48  6    | 489 29  3    |
| 9   8   23(6)| 7   34  1    | 456 26  4(5) |
| 46  5   36   | 2   3(4)8 9  | 468 7   1    |
+--------------+--------------+--------------+
| 46  2   69   | 3   1   8    | 49  5   7    |
| 1   7   8    | 4   9   5    | 2   3   6    |
| 3   49  5    | 6   7   2    | 1   8   49   |
+--------------+--------------+--------------+
| 2   6   4    | 9   5   3    | 7   1   8    |
| 5   19  19   | 8   6   7    | 3   4   2    |
| 8   3   7    | 1   2   4    | 56(9) 69  59 |
+--------------+--------------+--------------+
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: DoubleBUG

Postby marek stefanik » Sun Aug 01, 2021 8:49 am

Hi JRL,

I've had a look at the document and I have a few questions.

Firstly you only consider the most common digit in each box, instead of every digit with more then two occurrences in a house.
If I understand it properly, there is no proof that deleting all of your BUG candidates would actually produce a BUG, ie. a situation where each uresolved cell and digit in a house have exactly two candidates.

Secondly you first say:
We believe we know that at least ONE BC identified on a board will be valid, which means that some or even all of the others are invalid.
which is true (provided the BUG cadidates are chosen correctly), but then in example 5 you ignore four of the BUG candidates (1E1, 1E6, 3E9 and 1A6) with the explanation that:
E1[1] and E6[1] combine to E9[3]
A6[1] ... A9[3] pincer with E8[3] to eliminate E9[3]
How can the fact that these candidates contradict one another justify ignoring all of them if you only know that one of them is true?

I don't understand the justification for anything that happens from example 6 onwards. Since the puzzles are fairly simple (judging by the techniques you mentioned they should be about 7.0 SE at most), there is an explanation for why this might work:
Every false candidate is likely to chain to most other candidates, while the true candidates can only chain to other true candidates.
But this obviously never provides 100% certainty and will definitely fail from 8.0 SE upwards.

About the example:
If someone can tell me how to put the board in with fixed width characters I should be pleased.
You need to paste the grid into code tags or select the grid and then press the Code button.

Rather then choosing 5r2c9 as a BC it makes more sense to choose 4r12c7 instead. Obviously they lead to 5r2c9, but it makes it easier for others to see the BUG (if you delete the BCs with the 4s you reach a BUG, but if you delete them with the 5, you don't).

In general, you can get a much easier solution using other techniques and BUG is only useful in a handful of cases.
This puzzle, for example, can be solved with an XY Chain of length 6:
Code: Select all
   +---------------+---------------+---------------+
   | 7   c14  b12  | 5    48   6   | 489 a29   3   |
   | 9    8    236 | 7    34   1   | 456  26   45  |
   | 46   5    36  | 2    348  9   | 468  7    1   |
   +---------------+---------------+---------------+
   | 46   2    69  | 3    1    8   |f49   5    7   |
   | 1    7    8   | 4    9    5   | 2    3    6   |
   | 3   d49   5   | 6    7    2   | 1    8   e49  |
   +---------------+---------------+---------------+
   | 2    6    4   | 9    5    3   | 7    1    8   |
   | 5    19   19  | 8    6    7   | 3    4    2   |
   | 8    3    7   | 1    2    4   | 569  69   59  |
   +---------------+---------------+---------------+
(9=2)r1c8 - (2=1)r1c3 - (1=4)r1c2 - (4=9)r6c2 - (9=4)r6c9 - (4=9)r4c7 => -9r1c7, stte.
The combined length of your chains is 11, plus they don't follow single stream of reasoning and you first have to identify the BCs. Using the BUG here seems unnecessarily complicated.

Marek
marek stefanik
 
Posts: 353
Joined: 05 May 2021

Re: DoubleBUG

Postby JRL » Sun Aug 01, 2021 11:16 am

Thank you Mathimagics and marek stefanik for responding. I shall try to use the Code tag.

And to marek stefanik - you challenge me quite a bit (which is what I wanted). Some of your questions are hard to answer directly as I don't really understand how my DoubleBUG works - if you will allow me to claim for the moment that it does work!. If you are prepared to stay with this I am preparing a response. I should say that since I prepared my document quite a bit of time has elapsed and I have continued to try to solve using my technique. I have always been doubtful about one of my methods for establishing a Bug Candidate - and a recent board has convinced me that I am mistaken about another, though it shows up rarely. And I think I have a solution, but would rather not complicate things now.
In order to have a clear discussion, I will put up a board with candidates only as in Boxes 1, 2 and 9 (and not as in Box 3). These have a single multi-value cel containing the most commonly occuring number. Perhaps we may be able to agree there is a valid technique for assigning Bug Candidates. Or not! But it may be clear where there is a problem.
The second stage of DoubleBUG, after assigning a BC to each box not solely containing bi-values, is the resolution of a number of pincer values. I will study carefully what you say.
Please stay with this - at least a little bit - as I believe there is something here.
Whether other techniques are more efficient to solve my boards does not really concern me in trying to establish the technique. Though you could well be right.
Is my not using row and column nomenclature for cels a nuisance for you. I am used to the other system, though realise its limitations?

John
JRL
 
Posts: 7
Joined: 29 March 2021

Re: DoubleBUG

Postby marek stefanik » Mon Aug 02, 2021 1:52 am

Can you have a look at this puzzle? From my (limited) understanding of your technique I think it's a counterexample.
.2...754....4......4..1..86..9.2.....5...8.9..6.9.....7......6...653.9..2..8..45.
marek stefanik
 
Posts: 353
Joined: 05 May 2021

Re: DoubleBUG

Postby JRL » Mon Aug 02, 2021 8:54 am

Marek. Thanks for your post. I have the feeling this conversation is going the right way. Going back to basics.
I am in Bangkok - can I ask where you are, or what time zone?
The example you give the string looks like a perfect example of where DoubleBUG can be applied easily. And also to see if I can work out how to insert a board with fixed spacing:
Marek. Thanks for your post. I have the feeling this conversation is going the right way.
I am in Bangkok - can I ask where you are, or what time zone?
The example you give the string for appears to be a perfect example of where DoubleBUG can be applied very easily.
Code: Select all
+--------------+--------------+--------------+
| 9   2   13   | 6   8   7    | 5   4   13   |
| 6   13  8    | 4   5   23   | 7   12(3) 9    |
| 5   4   7    | 23  1   9    | 23  8   6    |
+--------------+--------------+--------------+
| 8   7   9    | 13  2   5    | 6   13  4    |
| 13  5   4    | 7   6   8    | 13  9   2    |
| 13  6   2    | 9   4   13   | 8   7   5    |
+--------------+--------------+--------------+
| 7   13  5    | 12  9   4    | (1)23 6 8    |
| 4   8   6    | 5   3   12   | 9   12  7    |
| 2   9   13   | 8   7   6    | 4   5   13   |
+--------------+--------------+--------------+

I don't have this right but is better. And if I highlight in colour I get codes as well. Ah well - not quite there.

As you undoubtedly know, neither of the BCs I would identify (3B8 and 1G7) are correct values, so resolving these values can give the wrong result as easily as the correct one. Well done, finding this. I think - at least for this configuration - the BC should appear 3 times in column, row and box - which neither do.
Long ago I read a small blog about False BUGs - and I cannot anymore find it. My recollection, though, is it referred to the case where the most common digit did not appear in the multi-value. This is not the case here. The question is whether this invalidates my concept, or whether this is a rare occurrence (or not?) and there is a test to validate or invalidate the BC.
Perhaps you have a thought.
John

PS Apart from the specific way in which I am defining BUG candidate - what for you does bug candidate mean, if anything? And if it has a meaning, how do you calculate it? I note in a previous post you said: "Rather then choosing 5r2c9 as a BC it makes more sense to choose 4r12c7 instead". How were you choosing the candidate that made it seem more sensible. I have also seen other posts on this Forum which talk of generating bug candidates in a solver ... don't know what to make of that.
JRL
 
Posts: 7
Joined: 29 March 2021

Re: DoubleBUG

Postby marek stefanik » Mon Aug 02, 2021 10:41 am

JRL wrote:can I ask where you are, or what time zone?
I live in Europe, but my sleep schedule has been a mess and so I basically post at random times.

JRL wrote:Long ago I read a small blog about False BUGs - and I cannot anymore find it. My recollection, though, is it referred to the case where the most common digit did not appear in the multi-value.
Quite possibly it only covered false BUG+1, in which case that's the only form, AFAIK.

JRL wrote:what for you does bug candidate mean, if anything?
For me a set of BCs is a set of candidates which, when all deleted, would give birth to a BUG.
In my counterexample if you were to delete your identified BCs, the grid would just collapse, giving a solution with singles.
If instead you did it in your example (with the BCs I would identify), you would reach a BUG:
Code: Select all
+------------------+------------------+------------------+
| 7     14    12   | 5     48    6    | 89+4  29    3    |
| 9     8     23+6 | 7     34    1    | 56+4  26    45   |
| 46    5     36   | 2     38+4  9    | 48+6  7     1    |
+------------------+------------------+------------------+
| 46    2     69   | 3     1     8    | 49    5     7    |
| 1     7     8    | 4     9     5    | 2     3     6    |
| 3     49    5    | 6     7     2    | 1     8     49   |
+------------------+------------------+------------------+
| 2     6     4    | 9     5     3    | 7     1     8    |
| 5     19    19   | 8     6     7    | 3     4     2    |
| 8     3     7    | 1     2     4    | 56+9  69    59   |
+------------------+------------------+------------------+
You can check for yourself that every unresolved cell and digit in a house have exactly two candidates left. Therefore at least one of the BCs must be true, assuming the puzzle has a unique solution. Obviously the 4s in b3 both lead to 5r2c9, but if you were to delete the 5 amongst other BCs, you would no longer reach the BUG, as the 5 is part of it.
marek stefanik
 
Posts: 353
Joined: 05 May 2021

Re: DoubleBUG

Postby JRL » Mon Aug 02, 2021 11:40 am

Marek. Very helpful. So for the board you sent this morning
.2...754....4......4..1..86..9.2.....5...8.9..6.9.....7......6...653.9..2..8..45.
What are your BCs?
John
JRL
 
Posts: 7
Joined: 29 March 2021

Re: DoubleBUG

Postby marek stefanik » Mon Aug 02, 2021 11:55 am

There is no way to ever reach a BUG from that state, so you cannot possibly get a set of BCs, similarly as in the false BUG situation you were referring to.
marek stefanik
 
Posts: 353
Joined: 05 May 2021

Re: DoubleBUG

Postby JRL » Mon Aug 02, 2021 12:28 pm

Mark. Are you able to tell me HOW you recognise that BUG is not possible from this board? I've no experience of this. John
JRL
 
Posts: 7
Joined: 29 March 2021

Re: DoubleBUG

Postby marek stefanik » Mon Aug 02, 2021 1:09 pm

If you delete any candidate from the two trivalue cells, it will create singles. As long as there is a multivalue cell without valid BCs (not reducible to a bivalue cell without creating singles), you cannot use BUG+n techniques and since in this puzzle there is no reducible cell, you are not going to be able to use them at all.

As you said:
the BC should appear 3 times in column, row and box
I would only add "at least" 3 times, for example 4b3 in your puzzle has 4 candidates left. With more additional candidates you have to make sure that you don't assign a digit as a BC too many times in a house and so there would always be two candidates left if you deleted all of the BCs.
marek stefanik
 
Posts: 353
Joined: 05 May 2021


Return to Advanced solving techniques