Possibly a new Hidden UR?

Advanced methods and approaches for solving Sudoku puzzles

Possibly a new Hidden UR?

Postby sos440 » Mon Nov 28, 2022 1:04 pm

Updates:
  • (Nov 30, 2022) Replaced figures, examples and added Proposition 2 that helps locate the configuration.

Hello everyone,

This is my first posting on this forum, so please advise me if I am not following the rules. Anyway, I would like to ask if the following strategy has been known or discussed before.

Consider the following UR pattern for candidates a and b:

Code: Select all
.-------.-----------.-------.
| . . . | .   . .   | . . . |
| . . . | .   . .   | . . . |
| . . . | ab* . ab* | . . . |
.-------.-----------.-------.
| . . . | .   . .   | . . . |
| . . . | .   . .   | . . . |
| . . . | .   . .   | . . . |
.-------.-----------.-------.
| . . . | ab* . ab* | . . . |
| . . . | .   . .   | . . . |
| . . . | .   . .   | . . . |
.-------.-----------.-------.

. = any candidates
* = any additional candidates

Given this, let's ask the following question:

What (possibly minimal) conditions would lead to a deadly pattern, and what would we need in order to avoid this from happening?


For each chosen candidate of the eight noted ones participating in the UR pattern, the three other candidates that, together with the chosen candidate, form a deadly pattern will be called deadly friends of the chosen one. For example, if the candidate a in the top left UR cell in the figure above is choen, then its three deadly friends will be:

  • the candidate b in the top right UR cell;
  • the candidate b in the bottom left UR cell;
  • the candidate a in the bottom right UR cell;
Below demonstrates the deadly pattern containing the chosen candidate a and its three deadly friends:

Code: Select all
.-------.---------.-------.
| . . . | .  . .  | . . . |
| . . . | .  . .  | . . . |
| . . . | a* . b* | . . . |
.-------.---------.-------.
| . . . | .  . .  | . . . |
| . . . | .  . .  | . . . |
| . . . | .  . .  | . . . |
.-------.---------.-------.
| . . . | b* . a* | . . . |
| . . . | .  . .  | . . . |
| . . . | .  . .  | . . . |
.-------.-----------.-------.

By definition, the chosen candidate a and its three deadly friends would have formed a deadly pattern if all those four were present in a solution. Thus, if it is the case that the three deadly friends all become true when the chosen candidate is assumed true, then we may erase the chosen candidate assuming the uniqueness of solution.

So far so good, and perhaps this is something you are already well aware of. Now I claim:

Proposition 1. Let a be one of those 8 candidates that participate in a UR pattern. Suppose the following condition holds:

  1. Each of the three deadly friends is strongly linked to another candidate in the UR pattern.
  2. Not all three strong links in Item 1 meet at a single candidate. (Note: It is allowed that two of them meet.)
Then we can erase the chosen candidate a from the puzzle.


A brute-force proof would go by first noting that there are total 3^3 - 1 = 26 possible configurations of strong links appearing in Item 1. (There are 3 possible choices for strong link touching each of the deadly friends, resulting 3^3 = 27 possible set of choices. In one of them, all three strong links meet, leaving 26 valid configurations of strong links.) Then showing that assuming the chosen candidate true makes all three deadly friends true as well. (A more clever proof makes use of the fact that the question is equivalent to finding certain types of spanning trees in a hamming cube, which essentially leaves much fewer possible configurations to check.)

A slightly different version of Proposition 1 helps spot the configuration described in that proposition:

Proposition 2. In a UR pattern, suppose the following holds:

  1. There are three strong links, say L1, L2, L3, connecting UR candidates;
  2. Not all three of L1, L2, L3 are connected together. (I.e., at least one of them are disconnected from the rest.)
Then at least one of the UR candidates, not lying in any of those 3 strong links L1, L2, L3, must satisfy the condition of Proposition 1 and hence can be removed.


In the remaining part, we will actually examine all those 26 possible configurations and classify them according to the known strategies:



Group 1. Configurations belonging to this group is either UR Type 1 or reduces to this type. There are total 3 of them, listed below. (Here, thick blue lines represent strong links.)

Image

In each case, four gray cells represent UR cells. The candidate a in the top left UR cell with arrows annotated is the chosen one that can be erased from the puzzle. Indeed, assuming this is true and propagating the truth values through strong/weak links shows that the chosen one along with all three deadly friends all become true, contradicting the uniqueness assumption.

Of course, it is easy to see that these three cases are UR Type 1.

  • In the 1st case in the figure, the three UR cells containing deadly friends are bivalued, a perfect setting for UR Type 1.
  • In the 2nd and 3rd case in the figure, the two parallel strong links across the two UR cells form a hidden pair. This induces two new strong links that makes the configuration UR Type 1.


Group 2. Configurations in this group reduces to UR Type 4.

Image

In each of these case, two parallel strong links form a naked/hidden pair, making the two involved UR cells together form a floor. Then with the remaining strong link in the opposite side, we can invoke UR Type 4.



Group 3. Configurations in this group reduces to Hidden UR Type 1 in SudokuWiki or simply Hidden UR in Hodoku.

Image





Group 4. Configurations in this group reduces to Hidden UR Type 2 in SudokuWiki.

Image



Group 5. Configurations in this group reduces to instances of continuous AIC (a.k.a. AIC Nice Loop Rule 1). So, this case actually holds even without the uniqueness assumption.

Image



Group 6. An finally, here is something I believe is not widely known in the community.

Image

Some of the configurations belonging to this group can be regarded as a half version of UR Type 6 in Hodoku or UR Type 5 in SudokuWiki. However, some are truly "hidden" in the sense that all the four UR cells are allowed to have additional candidates.

Below is an example that I found while playing Jason Linhart's Enjoy Sudoku.

Image

  • 1 in E3 and J3 are eliminated using either UR Type 4 or HUR Type 2 in green-colored UR.
  • 9 in E1 is eliminated using Group 6 rule using blue-colored UR.
  • 8 in A4 is eliminated using Group 6 rule using orange-colored UR.



Anyway, that's it. :D Thank you for reading this, and I would be happy to hear feedback!
sos440
 
Posts: 1
Joined: 28 November 2022

Postby Pat-Moderator » Wed Nov 30, 2022 11:10 am

{ post has been updated }
User avatar
Pat-Moderator
Moderator
 
Posts: 54
Joined: 18 July 2005


Return to Advanced solving techniques