10 posts
• Page **1** of **1**

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

Last edited by daj95376 on Wed Sep 13, 2006 5:52 am, edited 2 times in total.

- daj95376
- 2014 Supporter
**Posts:**2624**Joined:**15 May 2006

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
- 2012 Supporter
**Posts:**4764**Joined:**02 November 2005**Location:**Southeastern USA

(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

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
**Posts:**54**Joined:**23 October 2005

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.

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.

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

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.

- daj95376
- 2014 Supporter
**Posts:**2624**Joined:**15 May 2006

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
- 2014 Supporter
**Posts:**2624**Joined:**15 May 2006

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

- gsf
- 2014 Supporter
**Posts:**7306**Joined:**21 September 2005**Location:**NJ USA

10 posts
• Page **1** of **1**