The New Sudoku Players' Forum

[udosuk]

Archangel,

Your program fails to discover that there is a "hidden single" in block 5 (r4c6 is the only cell holding a 2 in that box)... So you might like to review your codes and see if there is a hole somewhere...

ab, his method is not backdoor singles, but what's call "Ruby proposition" by gurth... Basically, you assume r1c3<>6 and proceed to a contradiction, therefore you can prove that r1c3=6 must be true... It's a perfectly valid logical "trial-and-error" technique, but is not guesswork...

This thread contains a more detailed description of "Ruby" as well as other terms of "gems"...

[daj95376]

udosuk and ab,

There are backdoor cells, which is a term used by gsf and others. I won't try to define it here.

Early on (for me), I coined the term backdoor single: a candidate and cell combination that results in the remainder of the puzzle being solved by singles. I do not know if anyone else is using this term, or even if I'm the first.

It is not a method. It is simply an observation made while searching chains.

If a person is looking to resolve a complex puzzle using a limited number of chains, then knowing where backdoor singles exist can be beneficial.

It appears that Archangel stumbled upon a backdoor single early in his attempt to solve the puzzle.

[udosuk]

It appears that Archangel stumbled upon a backdoor single early in his attempt to solve the puzzle.

He stumbled on a Ruby cell, which happened to be a backdoor single/backdoor cell leading to the grid being solved with singles...

He assumed r1c3<>6, i.e. r1c3=9, and got to a contradiction...
Therefore he concluded r1c3<>9, i.e. r1c3=6, and solved the puzzle using singles...

That wasn't a guess, but just a simple forcing chain (with singles), although it's a pretty long one...

BTW we don't need forcing chains to solve that particular puzzle, only pairs/triples/box-line interactions...

[daj95376]

It appears that Archangel stumbled upon a backdoor single early in his attempt to solve the puzzle.

He stumbled on a Ruby cell, which happened to be a backdoor single/backdoor cell leading to the grid being solved with singles...

He assumed r1c3<>6, i.e. r1c3=9, and got to a contradiction...
Therefore he concluded r1c3<>9, i.e. r1c3=6, and solved the puzzle using singles...

That wasn't a guess, but just a simple forcing chain (with singles), although it's a pretty long one...

BTW we don't need forcing chains to solve that particular puzzle, only pairs/triples/box-line interactions...

Well, I feel up for a good argument!!! Where shall we start.

First: My definition of a backdoor single preceeds the definition in you link by a long time.

Second: Here's the definition of a Ruby Cell from your link.

RUBY :

A Ruby is, strictly speaking, a non-conjugate candidate x in a sudoku, whose removal from a cell at the very start of the solution leads to a contradiction and whose placement leads to solution, both processes requiring no more techniques than SSTS, and preferably even a simpler set of techniques.

The simpler the techniques required, the greater the Ruby.

Non-conjugacy requires that there be more than 2 candidates in the Ruby Cell, and that the Ruby not be a member of a conjugate pair of x in row, column or box.

If you notice closely, it says that a Ruby Cell must contain more that two candidates. If you check the cell used by Archangel, you'll notice that it's a bi-value cell.

Anything further?

[gsf]

There are backdoor cells, which is a term used by gsf and others. I won't try to define it here.

Early on (for me), I coined the term backdoor single: a candidate and cell combination that results in the remainder of the puzzle being solved by singles. I do not know if anyone else is using this term, or even if I'm the first.

backdoor is taken from the constraint satisfaction literature

for sudoku a backdoor is defined to be a minimal set of cells that when solved
(set to the respective solution candidate values) results in a solution using a
given set of constraints

backdoors must always be qualified by the constraints in scope
so a "singles backdoor of size 1" means one cell that when
solved leads to a solution using singles only

all known 9x9 sudoku have singles backdoor size <= 2
aka the sudoku backdoor conjecture

the backdoor conjecture should provide info for solution techniques,
something similar to uniqeness, but that hasn't been exploited yet

[Archangel]

Archangel,

Your program fails to discover that there is a "hidden single" in block 5 (r4c6 is the only cell holding a 2 in that box)... So you might like to review your codes and see if there is a hole somewhere...

No bug. Sorry, I did not report correctly the intermediate result: at r4c4 the combination found by my program should be 23469, so there are two 2 in the central block.

Anyway the discussion about backdoor singles is promising (as soon as I understand the matter...: "a backdoor is defined to be a minimal set of cells that when solved (set to the respective solution candidate values) results in a solution using a given set of constraints " is not that clear. I think I have to apply myself more...)

[Archangel]

I also applied (manually or by software, it's just a difference in time) to the best ranked of the superior puzzles, the #74 by Vidarino.
Hard indeed. After a first pass I stuck at:

Code: Select all

 3458 35789 3489 |    1   458    6 | 5789 2789   2789
 4568  5678    1 |  245     9 2458 |    3  278   2678
  568     2  689 |    7    58    3 | 5689    4      1
-----------------------------------------------------
    7   368    2 |   69  1368   89 |    4  189      5
    1     4   38 |  259  3578 2589 |  789    6    789
    9    68    5 |   46 14678   48 |    2  178      3
-----------------------------------------------------
 2346     1 3469 |    8    46    7 |   69    5   2469
 4568  5689    7 | 4569     2  459 |    1    3   4689
24568  5689 4689 |    3   456    1 | 6789 2789 246789
 

Far from being solved, and with a lot of couples to test.
But I noticed that in the central block the 4 couples are connected, i.e. they admit only 2 solutions.
So I found that r4c4=6 is correct, r4c4=9 is not
With r4c4=6 the resulting scheme was:

Code: Select all

 
 3458 35789 3489 |  1 458   6 | 5789 2789   2789
 4568   578    1 | 25   9 245 |    3  278   2678
  568     2  689 |  7  58   3 | 5689    4      1
----------------------------------------------------
    7    38    2 |  6  13   9 |    4   18      5
    1     4   38 | 25 357  25 |  789    6    789
    9     6    5 |  4  17   8 |    2   17      3
----------------------------------------------------
 2346     1 3469 |  8  46   7 |   69    5   2469
 4568    58    7 |  9   2  45 |    1    3    468
24568   589 4689 |  3 456   1 | 6789 2789 246789   


(forget the first 2 vertical lines, introduced by the code)

Again, I had to choose, and my software confirmed that for r5c2 the right solution was a 3. Result:

Code: Select all

 
 3458 5789  349 |  1 458   6 | 5789 279   2789
 4568  578    1 | 25   9 245 |    3  27   2678
  568    2   69 |  7  58   3 | 5689   4      1
---------------------------------------------------
    7    3    2 |  6   1   9 |    4   8      5
    1    4    8 | 25   3  25 |   79   6     79
    9    6    5 |  4   7   8 |    2   1      3
---------------------------------------------------
 2346    1 3469 |  8  46   7 |   69   5   2469
 4568   58    7 |  9   2  45 |    1   3    468
24568  589  469 |  3 456   1 | 6789 279 246789   


Finally, I noticed that in the upper center block 2 is present only in the second row, so it can be eliminated from the same row of the two side blocks. In particular r2c8=7, what allows to proceed up to solution.

Code: Select all

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

By the way, when I operate manually I always follow that purging strategy, and the same for triplets of numbers forming three groups in a block or along a row or a column (those numbers can be eliminated from the other positions of the block, row or column). Sorry for my bad way of exposition.

My way of preceeding is rather rough and it must be supported by a simple software to test between alternate double solutions in an acceptable time. But I showed that even hard schemes can be solved in a short time.

[udosuk]

Well, I feel up for a good argument!!! Where shall we start.

...

Anything further?

Okay Danny, I was wrong in overlooking the non-conjugate requirement for a Ruby cell... I concede that the cell shouldn't be called a "Ruby cell"... But there should be a name for a cell that if we eliminate a value from it would lead to a contradiction...

But what I wanted to stress was that the process taken by Archangel wasn't just assuming the backdoor cell to be a certain value and then proceeding to the solution, instead he eliminated the value from that cell and found that it lead to a contradiction, therefore he concluded the cell must contain that value... To me it wasn't guessing at all...

Whether the cell was a backdoor or not is irrelevant to the process... If he got stuck after placing the value in that cell the move was still a perfectly valid one...

[StrmCkr]

the move is considered logic as its
an if then else statement that looks for an error - which technically is still logic just takes x amount of more time to find the single corect result.
when compared to a solution that says pattern results in n being removed ...repeat till puzzle solves..

[ronk]

But there should be a name for a cell that if we eliminate a value from it would lead to a contradiction...

We've all seen elimination-by-contradiction (EBC) quite frequently, so ...

placement-by-contradiction (PBC)
OR
assignment-by-contradiction (ABC)

... make sense to me.

If we use the vowels -- ABC and EBC -- maybe we can work our way up to UBC, for undecided-by-contradiction. (Sorry, just couldn't resist.)

[daj95376]

Well, I feel up for a good argument!!! Where shall we start.

...

Anything further?

Okay Danny, I was wrong in overlooking the non-conjugate requirement for a Ruby cell... I concede that the cell shouldn't be called a "Ruby cell"... But there should be a name for a cell that if we eliminate a value from it would lead to a contradiction...

But what I wanted to stress was that the process taken by Archangel wasn't just assuming the backdoor cell to be a certain value and then proceeding to the solution, instead he eliminated the value from that cell and found that it lead to a contradiction, therefore he concluded the cell must contain that value... To me it wasn't guessing at all...

Whether the cell was a backdoor or not is irrelevant to the process... If he got stuck after placing the value in that cell the move was still a perfectly valid one...

Yes, udosuk, and I was very wrong to take it personally -- especially after I discovered that almost all of my posts regarding backdoor singles are gone. I agree with you that Archangel's approach is frowned upon -- especially when other, fundamental techniques are available.

This discussion has gone in several directions at once. I suspect because Archangel stated that his solver was able to solve the puzzle after setting [r1c3]<>6.

ab thought he meant [r1c3]=6 and went on to discuss it as an assignment .. and that's what backdoor singles is about -- making an assignment and having the puzzle solve in a cascade of singles. A good example is what happens in BUG+1.

This discussion has also diverted to what happens if Archangel had meant [r1c3]<>9 ... and that can be described in several ways. Like ronk, I use EBC to define this type of elimination.

Finally, I probably shouldn't have mentioned chains in my message above. It has nothing to do with Archangel's puzzle. I was simply trying to give an example of when using information about a backdoor single might be acceptable.

[tarek]

Some new posts seem to revive this thread, maybe there si an interest in some more .............

I wonder if a new (Superior thread 2) where a new 100 superior puzzles (with some new more strict rules to insure quality) would be of interest to anyone ?

tarek

[ab]

I'm sure you'd get some takers Tarek. Also several new people who generate puzzles have joined the forum since this thread subsided.

[tarek]

great, expect something to materialise in the next week or so.....

tarek

[Pat]

...1..4.....8.3.1.....26..968.....4...1...5...7.....867..36.....1.5.9.....2..7...

Code: Select all


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




{ and re-posted on another forum }