David P Bird wrote:My conjecture is that a digit placement arising from only elementary eliminations (naked and hidden singles and tuples, box/line reductions and simple fish) can never produce an AR threat.

[...]

I believe that to produce such a situation some more advanced elimination method must have been used beforehand. Your mission, if you choose to accept it, is to prove whether that is true or not.

Hi

David,

It's a nice challenge.

Your conjecture is correct.

It follows, after a bit of argument, from this ...

Given a scenario where these 8 candidates exist:

- Code: Select all
`+---------+--------+-------+`

| 12 . . | 12 . . | . . . |

| . . . | . . . | . . . |

| 12 . . | 12 . . | . . . |

+---------+--------+-------+

Statement (1): It is impossible for 1r1c1 to be eliminated using those techniques, without one of { 2r1c1, 1r1c4, 1r3c1 } also being eliminated.

This will be proved below.

A more refined form of the statement, would be that if 1r1c1 has been eliminated using one of those techniques, then either one of { 2r1c1, 1r1c4, 1r3c1 } was also eliminated, or an elimination has been missed, and is still available.

-----

I think the most general form of the AR argument is this:

Given a scenario like this:

- Code: Select all
`+--------+--------+-------+`

| 1A . . | 2B . . | . . . | None of the 4 cells were givens

| . . . | . . . | . . . | A, B, C are lists of candidates; empty lists are allowed

| 2C . . | 1 . . | . . . | Somehow, 1r3c4 has been (properly) deduced.

+--------+--------+-------+

Statement (AR):Any solution to the puzzle, unique or not, must contain a candidate from one of { A, B, C }.

A review of the proof for "

Statement (AR)": If the puzzle has no solutions, then the statement is true by default. On the other hand, if it had a solution with no candidate from any of { A, B, C }, then it would contain the values { 1r1c1, 2r1c4, 2r3c1, 1r3c4 }. Since none of the four cells were "givens", there would also be a second solution containing { 2r1c1, 1r1c4, 1r3c1, 2r3c4 } -- the standard UR claim. But since that solution contains 2r3c4, it would follow that 1r3c4 was not properly deduced. So if 1r3c4 has been properly deduced, then any solution must contain a candidate from one of { A, B, C }.

That statement can be generalized to apply to this scenario:

- Code: Select all
`+-----------+--------+-------+`

| 1[2]A . . | 2B . . | . . . | Same setup as above, where the 2r1c1 candidate is optional,

| . . . | . . . | . . . | and not considered as being part of A

| 2C . . | 1 . . | . . . |

+-----------+--------+-------+

... by noting that in the original "AR" statement, with A replaced by A u { 2r1c1 }: 1) if the solution doesn't contain a candidate from one of { B, C }, then it contains a candidate from the larger 'A'; 2) not containing anything from { B, C }, it would contain 2r1c4 and 2r3c1; and it could

not contain 2r1c1; and so 3) since the only thing left, is a candidate from the smaller 'A', it would follow that it contains a candidate from the smaller 'A'. Summarizing, if it doesn't contain a candidate from one of { B, C }, then it contains one from the smaller 'A', and so all in all, it must contain a candidate from one of { (the smaller A), B, C }.

-----

To prove your conjecture, we can use "

Statement (1)" to prove that using those techniques only, it is impossible to deduce that 1r3c4 is part of the solution (i.e. impossible to see it as a "single"), as long as candidates { 1r1c1, 2r1c4, 2r3c1 }, still exist. [ That is, assuming that when any of the techniques is used, all of the eliminations are taken. ]

In other words, this follows from

Statement (1) ...

In an initial scenario where these candidates still exist:

- Code: Select all
`+--------+--------+-------+`

| 12 . . | 12 . . | . . . |

| . . . | . . . | . . . |

| 12 . . | 12 . . | . . . |

+--------+--------+-------+

Statement (3): It will be impossible for 1r3c4 to be seen as a naked or hidden single, using the indicated techniques, until one of { 1r1c1, 2r1c4, 2r3c1 } is eliminated.

A more refined form of the statement, would be that if 1r3c4 can ever be seen as a single, then either one of { 1r1c1, 2r1c4, 2r3c1 } will have been eliminated, or an elimination for one of them, will have been missed, and would still exist.

-----

To prove

Statement (3) using

Statement (1):

1) There are 3 versions of

Statement (1), that follow from the symmetry of the situation:

- It is impossible to eliminate 2r3c4, without also eliminating one of { 1r3c4, 2r1c4, 2r3c1 }
- It is impossible to eliminate 1r1c4, without also eliminating one of { 2r1c4, 1r1c1, 1r3c4 }
- It is impossible to eliminate 1r3c1, without also eliminating one of { 2r3c1, 1r1c1, 1r3c4 }

2) Taken together, they imply this:

- It is impossible to eliminate one of { 2r3c4, 1r1c4, 1r3c1 }, without also eliminating one of { 1r1c1, 2r1c4, 2r3c1, 1r3c4 }.

3) For 1r3c4 to be seen as a single, one of { 2r3c4, 1r1c4, 1r3c1 }

must be eliminated:

- To be seen as a naked single in r3c4, 2r3c4 would need to be eliminated
- To be seen as a hidden single in r3, 1r3c1 would neeed to be eliminated.
- To be seen as a hidden single in b2 or c4, 1r1c4 would need to be eliminated.
- Those are the only options, and each involves one of { 2r3c4, 1r1c4, 1r3c1 } being eliminated.

4) With (3) and (2) together, it follows that 1r3c4 can't be seen as a single, unless one of { 1r1c1, 2r1c4, 2r3c1, 1r3c4 } has already been eliminated.

5) Since 1r3c4 itself, is "out", that leaves one of { 1r1c1, 2r1c4, 2r3c1 }, to have been eliminated, before 1r3c4 could be seen as a single (assuming all eliminations were taken, when any of the techniques were applied).

6) Summarizing:

- It will be impossible for 1r3c4 to be placed as a single, as long as the { 1r1c1, 2r1c4, 2r3c1 } candidates still exist.

A more refined statement, would be that if it was possible to place 1r3c4 as a single, then it would be possible to eliminate one of { 1r1c1, 2r1c4, 2r3c1 } as well, destroying the "AR threat".

-----

What remains is a detailed proof for

Statement (1).

1) Suppose 1r1c1 is eliminated as a naked set (n-tuple) elimination:

- Then it's a naked set in r1, in c1, or in b1
- Whichever house it is (r1,c1 or b1), it will contain (just) one of the 1r1c4, 1r3c1 cells/candidates
- The (n-tuple) cell set won't include r1c1, since naked set eliminations occur outside the cell set, and we're assuming that 1r1c1 is eliminated.
- Whichever of { 1r1c4, 1r3c1 } is in the same house as the naked set, if we assuming that that candidate is not *also* eliminated, then it would follow that the (n-tuple) cell set must include that cell (since 1's in cells outside the set, are being eliminated).
- But that cell (r1c4 or r3c1) also contains the '2' candidate (at that time), and with that cell in the set, and r1c1 ourside the set, the 2r1c1 candiadte would also eliminated.
- Summarizing: If neither of { 1r1c4, 1r3c1 } is (also) eliminated, then 2r1c1 is eliminated.

Hence: At least one of { 1r1c4, 1r3c1, 2r1c1 } would also be eliminated.

2) Suppose 1r1c1 is eliminated in a hidden set elimination.

- Then there's a naked set is present in the same house, that would cause the identical set of eliminations, and so from the argument above, one of { 1r1c4, 1r3c1, 2r1c1 } would also be eliminated.

3) Suppose 1r1c1 is eliminated in a basic fish elimination.

- Assume it's a row fish -- 'n' rows with the '1' candidates restricted to 'n' columns, with the 1's in those columns, but in other rows, being eliminated. The argument for a column fish, would follow from symmetry.
- If the 1r3c1 candidate is also eliminated, then that's fine ... it fits with the statement that one of { 1r1c4, 1r3c1, 2r1c1 } is also eliminated.
- Focusing on the situation where 1r3c1 is not (also) eliminated, then ...
- Since 1r3c1 is not eliminated, r3 must be in the row set for the fish.
- Since 1r1c1 is being eliminated, r1 cannot be in the row set.
- Finally, since the 1r3c4 candidate is also present at the time, and since r3 is in the row set, and r1 isn't in the row set, the 1r1c4 candidate would also be eliminated, and so again, one of { 1r1c4, 1r3c1, 2r1c1 } would also be eliminated.

4) Suppose 1r1c1 was eliminated in a line/box elimination. Cases that would cause that, and details for each, are listed below. In the cases that are relevant, one of { 1r1c4, 1r3c1 }, and hence one of { 1r1c4, 1r3c1, 2r1c1 }, is also eliminated.

- 1's in r2, are locked in b1 -- then 1r3c1 also would be eliminated
- 1's in r3, are locked in b1 -- impossible since 1r3c4 is still present
- 1's in c2, are locked in b1 -- then 1r3c1 also would be eliminated
- 1's in c3, are locked in b1 -- then 1r3c1 also would be eliminated
- 1's in b2 are locked in r1 -- impossible since 1r3c4 is still present
- 1's in b3 are locked in r1 -- then 1r1c4 also would be eliminated
- 1's in b4 are locked in c1 -- then 1r3c1 also would be eliminated
- 1's in b7 are locked in c1 -- then 1r3c1 also would be eliminated

5) Suppose 1r1c1 eliminated as a "same digit", line of sight elimination, after a '1' is placed in one of { r1, c1, b1 }.

- The '1' would need to be a naked or hidden single. It can't be a hidden single, though, since the { 1r1c4, 1r3c1 } candidates are still present. So, it could only be a naked single.
- That would mean that the single in a cell that is not one of { r1c4, r3c1 }, since those cells also contain the '2' candidate.
- With that, whichever of { r1c4, r3c1 } is in the same house as the single [ and one of them would be in the same house ], the corresponding candidate from { 1r1c4, 1r3c1 }, would also be eliminated.
- That fits with the statement that one of { 1r1c4, 1r3c1, 2r1c1 } is also eliminated.

6) The last option would be that 1r1c1 is eliminated since a digit other than '1' is being placed in r1c1, as as a hidden single.

- It can't be the '2', though, since 2r1c4 and 2r3c1 are still present.
- So it would be a digit other than '2' (being placed in r1c1), and the 2r1c1 candidate would also be eliminated.
- Again, that fits with the statement that one of { 1r1c4, 1r3c1, 2r1c1 } is also eliminated.

That completes the proof.

-----

Regards,

Blue.