The New Sudoku Players' Forum

[RW]

I've noticed that in some solutiongrids numberpairs and triplets can be more entwined than in others. The digits can be paired in 36 different ways, and the pairs can form 1-4 different deadly patterns each. If digits a-b form 4 deadly patterns, then removing all digits a and b would cause 16 solutions (2^4). If a-b form only one deadly pattern, then removing all digits a and b would cause 2 solutions. I will call such a pair "fully entwined".

If a pair, a-b, is fully entwined then you can remove all digits 'a' and all but one of digit 'b' and still maintain an unique solution. If a triplet a-b-c is fully entwined, then you can remove all digits 'a' and all but one of both digits 'b' and 'c' and maintain an unique solution.

The solution to the "toughest known":

Code: Select all

 *-----------*
 |798|635|421|
 |126|974|583|
 |453|218|679|
 |---+---+---|
 |972|586|314|
 |564|123|897|
 |381|497|256|
 |---+---+---|
 |617|352|948|
 |835|749|162|
 |249|861|735|
 *-----------*

Out of the 36 numberpairs 20 are fully entwined (1-5, 1-6, 1-7, 1-8, 1-9, 2-3, 2-4, 2-5, 2-7, 3-4, 3-6, 3-7, 3-9, 4-6, 4-8, 5-7, 5-9, 6-8, 6-9, 8-9), two form three deadly patterns (1-2, 3-8) and one forms four deadly patterns (7-9). The rest form two.

There's also 7 triplets that are fully entwined (1-5-7, 1-6-9, 2-3-4, 2-3-7, 2-5-7, 3-6-9, 4-6-8). Removing all digits of any of these triplets would cause only 6 solutions. To compare, if you chose to remove all digits of the triplet 4-7-9, that would cause 360 solutions.

Has this field ever been researched? What's the maximum/minimum number of fully entwined pairs/triplets in a grid? What would be the average for a random grid? Can there be fully entwined quads? Does the amount of fully entwined pairs/triplets have any effect on the puzzles that can be constructed from the grid (more hard puzzles or low clue puzzles)?

I made one manual attempt to construct a grid with fewer fully entwined pairs and got 14 fully entwined pairs and 4 fully entwined triplets. I'm sure the number can be pressed down a lot from there, so I won't even bother posting the puzzle. But it seems to me the ratio would be quite high in the toughest known.

Or am I just wasting your time as there is another thread discussing this somewhere?

RW

[Ocean]

Has this field ever been researched?
RW

The sets you describe are also called unavoidable sets - originally called exchangeable sets.

For one specific grid (the so-called sf-grid which contains 29 sudokus with 17 clues), gfroyle collected 240000 unavoidable sets, available in the file sf-big.

The programs unavoid and checker (see this site) are written to find unavoidable sets in a grid, and use unavoidable sets to search a given grid for puzzles.

In the pseudo thread you can find statistics on the 'small' minimal unavoidable sets (counted by Red Ed). Also all possible types of minimal unavoidable sets of size 4 (one type), size 6 (four types), size 8 (nine types) and size 9 (three types) are listed explicitely.

Some thoughts about the number of solutions to a multisolution grid and n-permutable sets are discussed in the Max number of clues thread.

As this field is not fully explored, we will be more than happy if you find new insight. The connection with 'unique rectangles' (UR) is of course obvious, as it's exactly the same subject, viewed from different perspectives. Maybe a 'join of theories' could be in order?

[RW]

The sets you describe are also called unavoidable sets - originally called exchangeable sets.

To set the terminology straight (I don't have the "Oxford Sudoku Dictionary")

Unavoidable set - A set of n clues that if removed can be solved in multiple ways
Deadly pattern - A set of n cells that can be solved in multiple ways

Is this correct? I've seen both used in both ways and never seen a clear definition. If this is correct then yes, I should have used the term unavoidable sets instead of deadly patterns in my first post. I'm aware that unavoidable sets have been discussed before, but what I was looking for was a slightly different approach. I'll rephrase my question:

-Is there a completed grid from which removing all instances of any two digits 'a' and 'b' would give exactly two solutions?
-Is there a grid from which removing all instances of any two digits 'a' and 'b' would always give at least 4 solutions?
-If not, what's the closest we can get to these extremes?
-And most importantly, is there a reason why we should care? Does it affect the puzzles that can be constructed from the grid?

The connection with 'unique rectangles' (UR) is of course obvious, as it's exactly the same subject, viewed from different perspectives. Maybe a 'join of theories' could be in order?

I'm not sure what you mean, I thought the theories already were joined... As you said, URs (and BUG-lites) are essentially the same viewed from a different perspective (the deadly pattern perspective). What parts of the unavoidable set theories have not yet been used for uniqueness technique?

RW

[Ocean]

-Is there a completed grid from which removing all instances of any two digits 'a' and 'b' would give exactly two solutions?

Clipped from a post by coloin (found in one of the references above):

Code: Select all

+---+---+---+
|562|3..|471|
|.4.|716|253|
|137|425|..6|
+---+---+---+
|35.|1.4|627|
|.74|263|1.5|
|216|.57|34.|
+---+---+---+
|6.1|542|73.|
|725|63.|.14|
|4.3|.71|562|
+---+---+---+  18 clue completion per each of 2 grid solutions.


-Is there a grid from which removing all instances of any two digits 'a' and 'b' would always give at least 4 solutions?

The question can be rephrased: Is there a grid with the specific 4-permutable set of size 18 consisting of only two different digits. Or: Is there a grid containing two minimal unavoidable sets of size A and 18-A respectively, where both sets contain the same two digits. I guess the answer is Yes, but don't have an example ready.

-And most importantly, is there a reason why we should care? Does it affect the puzzles that can be constructed from the grid?

From the grid shown above 29 sudokus with 17 clues can be constructed. So it's certainly not an average grid.

I've seen both used in both ways and never seen a clear definition.

I also asked for definitions once, and got these two (found in the previous references):

An unavoidable set is a collection of cells in a sudoku grid such that any valid puzzle for that grid must contain at least one of those cells. A minimal unavoidable is one that does not strictly contain any other unavoidables.

For an alternative definition, let Z be a particular collection of (cell,value) pairs, i.e. something you think might be an unavoidable set. Let Constraints(Z) be the 27 statements of the form "box B contains values {...}", "row R contains values {...}" and "column C contains values {...}", with the "..." parts depending on Z. By definition Z satisfies Constraints(Z); iff any other Z' also satisfy Constraints(Z), and Z itself can be embedded in a valid sudoku grid, then Z (and its friends Z') are unavoidables. Z is then minimal iff all none of the Z' (including Z itself) satisfying Constraints(Z) have any (cell,value) pairs in common. The point of this alternative definition is just to formalise the notion that unavoidables are subsets of grids that you can change (carefully) without affecting the validity of the parent grid.

I'll give another definition. An unavoidable set in a completed grid is a set of cells such that some permutation of those cells results in another valid completed grid.

A minimal unavoidable set is an unavoidable set with the property that no subset is an unavoidable set, except itself.

I thought the theories already were joined... () What parts of the unavoidable set theories have not yet been used for uniqueness technique?

The two perspectives have been discussed separately, and completely different terminology has developed. It's rather obvious that not everything is covered both places. It's natural to focus on different aspects. I was (loosely) thinking in the direction of establishing some kind of 'formal correspondence' between the two.

[RW]

I'll try to adapt your terminology to explain my questions once more. Any set of size 18 consisting of only two different digits will always be 2-, 4-, 8- or 16-permutable. In any solutiongrid there is always 36 such sets. The solution to the "toughest known" I examined has twenty 2-permutable such sets, thirteen 4-permutable sets, two 8-permutable sets and one 16-permutable set. In my first post I called the 2-permutable sets "fully entwined", as the two digits of such a set are all affecting each other, you cannot divide them into separate unavoidable sets.

The grid you clipped from a post from coloin:

Code: Select all

+---+---+---+
|562|389|471|
|849|716|253|
|137|425|896|
+---+---+---+
|358|194|627|
|974|263|185|
|216|857|349|
+---+---+---+
|691|542|738|
|725|638|914|
|483|971|562|
+---+---+---+

Has 28 2-permutable and eight 4-permutable. That's 8 more fully entwined pairs than in the grid I showed! But not yet a grid where ALL pairs a-b would be fully entwined. The pairs that are not fully entwined are 1-6, 2-8, 3-4, 3-6, 4-7, 5-7, 4-8, 7-9.

-Is there a grid from which removing all instances of any two digits 'a' and 'b' would always give at least 4 solutions?

The question can be rephrased: Is there a grid with the specific 4-permutable set of size 18 consisting of only two different digits. (..) I guess the answer is Yes, but don't have an example ready.

The grid you posted has 8 such sets (the pairs that are not fully entwined). The question was: Is there a puzzle where ALL pairs a-b are at least 4-permutable (no fully entwined pairs)?

From the grid shown above 29 sudokus with 17 clues can be constructed. So it's certainly not an average grid.

Apparently it then might make a difference and this could provide an approach to finding grids with low/high clue puzzles. First construct grids with high/low numbers of fully entwined pairs, then scan those grids for puzzles. I'm also wondering if the entwined grid would make it more likely for extremely difficult puzzles to appear. I tried applying the diagonal pattern to the grid you posted and this is how close I got:

Code: Select all

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

Seems quite hard, maybe ravel can tell me how it compares to the other hard ones. If this isn't hard enough, I'm quite sure you can find a harder diagonal puzzle from the grid as this was my first (manual) try.

RW

[Ocean]

But not yet a grid where ALL pairs a-b would be fully entwined.

Sorry, it seems I misunderstood. Didn't catch the proper meaning of the words 'any'/'all'. So my 'answers' must seem silly, as they 'answered' questions not asked...

[gsf]

Code: Select all

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

this puzzle has one FN-constrained backdoor [24]=7
its maddening how one assignment can make a hard puzzles crumble in a cascade of singles
is there anything special about [24] w.r.t. the unavoidables?

[ravel]

Seems quite hard, maybe ravel can tell me how it compares to the other hard ones.

My program stopped with 2 steps (r1c8<>3, r6c5<>9), but this thread looks promising. Maybe i was wrong that looking for special grids would not be effective for finding hard or low/high clue puzzles.
I hope its not too effective, otherwise i will not be able to check all the hard puzzles, that come out of it

[RW]

is there anything special about [24] w.r.t. the unavoidables?

Yes, it seems to be covering a lot of unavoidable sets. Adding clues to the other cells mostly makes 0 or 1 earlier clue redundant (+the added clue of course. Adding 7 in r2c4 makes the following 7(!) clues redundant:

[edit: typo corrected]

Code: Select all

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

This means that r2c4 covers unavoidable sets that earlier where covered only by one or more of the cells marked with stars. I've noticed this relationship between singles backdoors and unavoidable sets earlier also. They tend to cause lots of redundant clues. No direct relationship to the fully entwined pairs, other that the digit 7 appears in three of the eight 4-permutable sets, meaning there is a total of 12 (3*2+6*1) different 2-digit unavoidable sets with digit 7 in the solution.

Didn't catch the proper meaning of the words 'any'/'all'.

No problem, I know I'm not very good at expressing myself clearly in written English. But I hope I can improve my skills.

RW

[RW]

Thanks ravel for the rating. I guess the easiest way to tell how these fully entwined pairs/triplets relate to hard or low/high clue puzzles would be to test the solutiongrids of the puzzles in your "toughest"-list and the known 17s/33s. A computer could easily do this in no time, but I'm still doing everything manually so I'm afraid I can't do it myself...

RW

[gsf]

Adding 7 in r3c4 makes the following 7(!) clues redundant:

redundant how? adding the # clue and dropping the *'d clues results in 56516 solutions

[ronk]

Adding 7 in r3c4 makes the following 7(!) clues redundant:

redundant how?

One clue at a time may be removed. The greater the number of such clues, the more extensive the "entwinement" ... but that's just a guess.

[RW]

redundant how? adding the # clue and dropping the *'d clues results in 56516 solutions

Code: Select all

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

It is a 26 clue puzzle with 8 redundant clues. This of course doesn't mean that you can remove all of them, remove one and some of the others might not be redundant anymore. Here's 4 different minimal puzzles that show how each of the seven clues can be removed individually:

Code: Select all

5.2.........71..5.1.....8....8..4..7.7..6....2..8..3....1..2..8....3....4....156.
5.2..9......71..5.1..4..8....8..4....7..6....2..8..3....1..2..8.......1.4....156.
5.2..9......71..5.1..4..8....8..4....7..6....2..8..3.......2..8....3..1.4....156.
5.2.........71..5.1..4..8....8..4..7.7..6.......8..3....1..2..8....3..1.4....156.


RW

[daj95376]

Is there a typo where RW wrote r3c4 instead of r2c4 ???

You guys may be arguing apples and oranges !!!

[gsf]

It is a 26 clue puzzle with 8 redundant clues. This of course doesn't mean that you can remove all of them, remove one and some of the others might not be redundant anymore. Here's 4 different minimal puzzles that show how each of the seven clues can be removed individually:

Code: Select all

5.2.........71..5.1.....8....8..4..7.7..6....2..8..3....1..2..8....3....4....156.
5.2..9......71..5.1..4..8....8..4....7..6....2..8..3....1..2..8.......1.4....156.
5.2..9......71..5.1..4..8....8..4....7..6....2..8..3.......2..8....3..1.4....156.
5.2.........71..5.1..4..8....8..4..7.7..6.......8..3....1..2..8....3..1.4....156.


thanks for the clarification
add [24]=7 and then minimize
the clues dropped in each of the minimizations is labeled "redundant"
I get these 6 non-isomorphic minimal puzzles when [24]=7
(one of which drops [24] to get the original puzzle -- sanity check)

Code: Select all

5.2.........71..5.1.....8....8..4..7.7..6....2..8..3....1..2..8....3....4....156.
5.2.........71..5.1..4..8....8..4..7.7..6.......8..3....1..2..8....3..1.4....156.
5.2..9.......1..5.1..4..8....8..4..7.7..6....2..8..3....1..2..8....3..1.4....156.
5.2..9......71..5.1..4..8....8..4....7..6....2..8..3.......2..8....3..1.4....156.
5.2..9......71..5.1..4..8....8..4....7..6....2..8..3....1..2..8.......1.4....156.
5.2..9......71..5.1..4..8....8..4....7..6....2..8..3....1..2..8....3....4....156.


the clues that change among the minimal puzzles are

Code: Select all

[16] [24] [34] [49] [61] [73] [85] [88]


which matches your *'d and #'d cells
now I get redundancy -- thanks
btw, this pipeline, using my command line solver on the original 25 clue puzzle,
produces the redundant clue list:

Code: Select all

sudoku -m -f%v r05.dat 24=7 |
sort |
sudoku -C |
sed 's/.* \(.*\) .*/\1/' |
sort -u