Sudoku Players' Forum (clone)

[Edited] Dropped because I had a misconception about backdoor single!

daj95376 wrote:B) Claim that [r9c9]=8 occurred because of a forcing chain/net on [r5c5].

... is the correct answer. That r5c5=5 is a backdoor single is "irrelevant" IMO.

ronk, good choice! I'm currently using (A) but would like to switch to (B). I even have an example. Unfortunately, it isn't critical to solving the puzzle.

(B), sure.

Considering the whole solution space by following each candidate in a "start" cell/row/column by forcing chains/nets, a conclusion can either be

a)concludent invalidation of the "goal" candidate, i.e. exclusion of the candidate for each forcing chain/net, or

b)concludent validation of the "goal" candidate, i.e. exclusion of the other candidates for each forcing chain/net.

Even the "nice loops" have the same logic, i.e. assuming that r4c4=1 implies with a forcing chain/net that r4c4!=1 is the special case of such a forcing chain/net, "start" cell being all candidates of r4c4, "goal" being the candidate r4c4=1, and trivially is r4c4!=1 if you consider the other candidates:

r4c4=1 > r4c4!=1
r4c4=2 > r4c4!=1 etc., so r4c4!=1

The backdoor is irrelevant, because the backdoor itself would be an entirely different consideration, in which r9c9 would be the "start" cell.

Regards, Maria

maria45: I've updated my original post so that [r5c5] is more clearly shown to have the backdoor single ... not [r9c9]. I'm sorry for the confusion!

===== ===== ===== ===== =====

I've upgraded my solver from using (A) to using (B) for FCNs. However, I have this nagging feeling that (C) should be the correct choice. Here's my reasoning.

I) I've never encountered a puzzle that wasn't solved with Naked/Hidden Singles for the final flourish. So, I view every other technique as just a means of exposing a backdoor single that will result in this flourish.

II) Now, if I'm already at a point where I must rely on performing an FCN on a cell, then it should be okay to recognize a backdoor single and take advantage of it. Why would I want to throw away information on solving the puzzle?

An example puzzle (from Eioru) with an Achilles Heal.

Code: Select all

..........4..8..5...3..1..8...9..5...9..6..2...1..8..4...3..7...6..2..9...5..7..1

r6c7    =  9     Hidden Single
    b6  -  367   Naked  Triple
r39     -  9     X-Wing
r258    -  1     Swordfish

*-----------------------------------------------------------------------------*
| 25678   1+2578  26789   | 24567   3457    234569  | 2346    1+3467  23679   |
| 1+267   4       2679    | 267     8       2369    | 1+236   5       23679   |
| 25679   257     3       | 24567   4579    1       | 246     467     8       |
|-------------------------+-------------------------+-------------------------|
| 234678  2378    24678   | 9       1+347   234     | 5       1+8     367     |
| 34578   9       478     | 1+457    6      345     | 1+8     2       37      |
| 23567   2357    1       | 257     357     8       | 9       367     4       |
|-------------------------+-------------------------+-------------------------|
| 248     1+28    2489    | 3       1+45    4569    | 7       468     256     |
| 1+3478  6       478     | 1+458    2      45      | 348     9       35      |
| 23489   238     5       | 468     49      7       | 23468   3468    1       |
*-----------------------------------------------------------------------------*


At this point, two observations can be made:

1) Only strong links remain for <1>, and
2) [b6] has a naked pair in <18>

Now, if you perform a standard Forcing Chain/Net on [r4c8] or [r5c7], then you will get [r8c3]=7 and 16 eliminations elsewhere. This still leaves you far from a solution. However, each cell also has a backdoor single that will solve the puzzle immediately.

Can anyone tell me what a backdoor single is?

A backdoor single is a inaccurate phrase that I've been using to describe when a cell assignment leads to a cascade of singles that solve the puzzle. I'm sorry for the confusion this has caused!!!

Oh, actually I think your definition of backdoor single makes good sense... I've renamed my term as backdoor cell... Where is the original source of that term anyway!?

udosuk wrote:Oh, actually I think your definition of backdoor single makes good sense... I've renamed my term as backdoor cell... Where is the original source of that term anyway!?

I've been tracing my posts and trying to eliminate the phrase backdoor single. During this process, I also searched for backdoor and magic cell (set). From what I can tell, gsf coined these terms in the Sudoku Programmers Forum awhile back. I misunderstood his usage and mistakenly condensed it to the phrase above!!!

daj95376 wrote:

udosuk wrote:Oh, actually I think your definition of backdoor single makes good sense... I've renamed my term as backdoor cell... Where is the original source of that term anyway!?

I've been tracing my posts and trying to eliminate the phrase backdoor single. During this process, I also searched for backdoor and magic cell (set). From what I can tell, gsf coined these terms in the Sudoku Programmers Forum awhile back. I misunderstood his usage and mistakenly condensed it to the phrase above!!!

I originally used the term magic cell(s) here
("magic cell" was coined by Vegard Hanssen in a private communication)
(edit: to attribute the coining to Vegard)
and then dukosu pointed me to the constraint satisfaction literature
and they used the term backdoor so I switched to that to avoid
gratuitous differences for the same concept

if you dig into Gomes and related papers they define a function that is applied
to each level of a search -- this would be the equivalent of the sudoku constraints in scope
and then backdoors are defined (and named) in terms of the function

for sudoku I restricted backdoor to a minimal set of cells and then
gave a general notation for puzzles w.r.t. constraints and backdoor size
"C-N-constrained"

so, for example, with C = naked + hidden singles (FN), FN-0-constrained puzzles
are solved by naked and hidden singles alone, FN-1-constrained puzzles
have at least one FN backdoor of size 1 containing a cell, that when solved,
allows a solution with naked and hidden singles, and FN-2-constrained puzzles
have no FN backdoors of size 1 and have at least one FN backdoor of
size 2 containing 2 cells, that when solved, allows a solution with naked and hidden singles

for ocean's hardest posts (55 puzzles in all), 49 are FN-2-constrained and
6 are FN-1-constrained

my conjecture is that there is no FN-i-constrained 9x9 sudoku, i>2

this is an amazing concept when you consider some of the spaghetti-like
solutions proposed on the forums, all of them are at most 2 cells
away from a naked/hidden singles constrained solution