The New Sudoku Players' Forum

[dobrichev]

Old discussion - are relabellings or VPTs kinds of UA sets?

I see no reason to distinguish them. Else we have a 16-clue valid puzzle. From some perspective they are less interesting, but let exploit their simplicity in attempt to generalize UA properties and prove the non-existence of strongly minimal UA with > 2 permutations.

Difficult questions.

Too bad. I expected a fast answer like "Impossible since each part must occupy 3 boxes in a row and there is no room for the other part". This is an obstacle to me too.
Fortunately there are only 259272 3-templates to investigate and after depersonalization of the individual values they fit in 92048 3-rookeries.
Next question is what to do with them in order to prove the non-existence of strongly minimal UA with 3 permutations and 3 digits involved?

[dobrichev]

6 beauties

Code: Select all

........1..2.13.4.15.6..7.........3..31..4..87..35.9........5...8.1.5..63.5.9..2.       27      145
........1..2.13.4..156..7.........3..8.35.6..1.3..9..2......5..53..4..8.7..1.5..9       27      145
........1..2.13.4..156..7.........3..7.35.8..1.3.4...9......5..53...8.2.9..1.5..6       27      145
........1..2.13.4..156..7.........3..7.35.8..1.3..4..9......5..53..8..2.9..1.5..6       27      145
........1..2.13.4..15.6.7.........3..7.35.8..1.3..4..9......5..53.8...2.9..1.5..6       27      145
........1..2.13.4..15..67.........3..7.35.8..1.34....9......5..53..8..2.9..1.5..6       27      145


[Red Ed]

Here's an attempt at the nonexistence of 3-digit strongly minimal unavoidables that have valency 3.

Suppose one exists and is made up of digits 1,2,3. Index the three permutations of the unavoidable with t=1,2,3 as well (as if the permutations were evolving over time). Say the 1s fill a pattern P at time t=1; then at time t=2, P will be filled with 2s (in position A, a subset of P) and/or 3s (in position B, i.e. P\A); then at time t=3, we must have A occupied by 3s and B by 2s (because at each "tick", all the digits must move). Pictorially:

Code: Select all

    |  1s |  2s |  3s |
----+-----+-----+-----+
t=1 | A+B |     |     |
t=2 |     | A   | B   |
t=3 |     | B   | A   |

The same argument goes for the evolution of 2s and 3s through the permutations, so in general the solution must look like this, where A,B,C,D,E,F are pairwise disjoint:

Code: Select all

    |  1s |  2s |  3s |
----+-----+-----+-----+
t=1 | A+B | C+D | E+F |
t=2 | D+E | A+F | B+C |
t=3 | C+F | B+E | A+D |

Now let πA be the footprint of A, i.e. the list of rows, columns and boxes it is incident with. The footprint of 1s must not change over time, so in particular we have πA+πB = πD+πE [1] where + is disjoint union of sets. But πA and πD are disjoint (look at the 3s at t=3), so [1] implies we must have πA=πE and πB=πD. But if (for example) πA=πE then we several another valid permutations of the big unavoidable set ...

Code: Select all

t=4 | E+B | C+D | A+F |
t=5 | D+A | E+F | B+C |
t=6 | C+F | B+A | E+D |

... which unfortunately clash with those at t=1,2,3 (e.g. the "A" 1s at t=1 are still there at t=5), breaking the strong minimality requirement that no permutations have any (cell,value) pair in common. So there cannot exist any 3-digit valency 3 strongly minimal unavoidables after all.

[Serg]

Hi, Red Ed!
Your posts are usually "brain food" for me, but your last post is even puzzle .

Now let πA be the footprint of A, i.e. the list of rows, columns and boxes it is incident with.

Sudopedia defines term "footprint" in another way. Let me cite that sudopedia page, because it runs unstable.

Code: Select all

The footprint of a pattern of solved cells is a list of 27 sets, where:
  * set 1 = values in row 1 of the pattern
  * set 2 = values in row 2 of the pattern
  * ...
  * set 9 = values in row 9 of the pattern
  * sets 10-18 = values in columns 1-9 of the pattern
  * sets 19-27 = values in boxes 1-9 of the pattern
A solution to a given footprint is any assignment of values to cells that has the prescribed row/column/box memberships.

A pattern whose footprint has more than one solution is {unavoidable} (and conversely).

Example

The unavoidable set ...
1  .  .  |  2  .  .  |  .  .  .
2  .  .  |  3  .  .  |  .  .  .
3  .  .  |  1  .  .  |  .  .  .
---------+-----------+---------
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
---------+-----------+---------
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
... has footprint
  * {1,2} in row 1
  * {2,3} in row 2
  * {1,3} in row 3
  * {1,2,3} in column 1
  * {1,2,3} in column 4
  * {1,2,3} in box 1
  * {1,2,3} in box 2
  * (all other rows, columns and boxes empty).


It seems to me you mean "footprint" of a pattern (subset of grid) is a set of rows, columns and boxes, which contain pattern's cells. Right? Let's treat "footprint" in this way.

The footprint of 1s must not change over time, so in particular we have πA+πB = πD+πE [1] where + is disjoint union of sets. But πA and πD are disjoint (look at the 3s at t=3) ...

Why should footprint(A) and footprint(D) be disjoint (i.e. they must not share rows, columns and boxes)? Please, clarify it.

Serg

[Red Ed]

Hi Serg.

Serg> Why should footprint(A) and footprint(D) be disjoint (i.e. they must not share rows, columns and boxes)? Please, clarify it.

At t=3, the 3s occupy the set of cells A+D. You can't have two 3s in the same row, column or box, so there can be no row, column or box of set A in common with the rows, columns and boxes of set D.

Ed.

[Serg]

Hi, Red Ed!
I accepted your proof. Impressive work!

Serg

[Serg]

Hi, dobrichev!

6 beauties

Code: Select all

........1..2.13.4.15.6..7.........3..31..4..87..35.9........5...8.1.5..63.5.9..2.       27      145
........1..2.13.4..156..7.........3..8.35.6..1.3..9..2......5..53..4..8.7..1.5..9       27      145
........1..2.13.4..156..7.........3..7.35.8..1.3.4...9......5..53...8.2.9..1.5..6       27      145
........1..2.13.4..156..7.........3..7.35.8..1.3..4..9......5..53..8..2.9..1.5..6       27      145
........1..2.13.4..15.6.7.........3..7.35.8..1.3..4..9......5..53.8...2.9..1.5..6       27      145
........1..2.13.4..15..67.........3..7.35.8..1.34....9......5..53..8..2.9..1.5..6       27      145


Fantastic result ! I was forced to change code of my cross-checking tool to verify your results (my tool had limitation of 100 permutations per UA set).
Now I confirm your discovery of 6 weakly minimal UA54 having 145 permutations each. Well done!

Serg

[coloin]

if it simplifies or contributes anything, here are the 6 pseudopuzzles - remorphed wrt the first one.
Showing 22 common clues

Code: Select all

........1..2.13.4.15.6..7.........3..31..4..87..35.9........5...8.1.5..63.5.9..2.
........1..2.13.4.15...67.........3..314....87..35.9........5...8.1.5..63.5.9..2.
........1.2..13.4.15.6..7.........3..31.4...87..35.9........5....81.5..63.5..9.2.
........1.2..13.4.15.6..7.........3..31..4..87..35.9........5....81.5..63.5.9..2.
........1.2..13.4.15..6.7.........3..31..4..87..35.9........5....81.5..63.59...2.
........1.2..13.4.15...67.........3..314....87..35.9........5....81.5..63.5.9..2.

[dobrichev]

... So there cannot exist any 3-digit valency 3 strongly minimal unavoidables after all.

I accepted your proof. Impressive work!

Excellent!
I can't follow the proof, but does the nonexistence of 3-digit valency 3 strongly minimal unavoidables formally prove also the non-existence of any larger one?

[dobrichev]

Now I confirm your discovery of 6 weakly minimal UA54 having 145 permutations each.

Thank you!

[dobrichev]

if it simplifies or contributes anything, here are the 6 pseudopuzzles - remorphed wrt the first one.
Showing 22 common clues

Thank you for the interest, Coloin.

Maybe it would be attractive to show the 18 UA6 from their decompositions in some symmetrical way?

The command I am using for listing the UA for a given pseudo-puzzle is

Code: Select all

gridchecker --unav --verbose < pp_list.txt

where pp_list.txt is the list of the pseudo-puzzles as shown in the above posts - either in mine or in coloin's.

[Red Ed]

I can't follow the proof, but does the nonexistence of 3-digit valency 3 strongly minimal unavoidables formally prove also the non-existence of any larger one?

Sadly, I doubt it. With k>3 digits, the proof technique requires k! variables (not just A to F) but I suspect you don't get enough new constraints on their footprints to yield a contradiction. If I can face checking properly, I'll let you know.

[dobrichev]

Hi,

I stopped the generation of UA with high number of permutations.
The record so far is 145.
A list of weakly minimal unavoidable sets with 35+ permutations is available here.
The columns are
- generating pseudo-puzzle = a puzzle with #solutions=valency, and for one (and only one) of the solutions the puzzle non-givens form a minimal unavoidable set.
- number of givens = 81- the size of the weakly minimal UA.
- number of solutions = the valency of the weakly minimal UA.

I have a larger file with UA of valency 16+ along with additional seed info. If somebody is interested I will make these files downloadable too.

Cheers,
MD

[Serg]

Hi, all!
I've found a proof of n-digit n-valent strongly minimal UA sets (n > 2) impossibility.

Proof.
Suppose n-digit n-valent strongly minimal UA sets (n > 2) exist. Let's consider sample n-digit n-valent strongly minimal UA set. I'll treat this UA set containing digits {1, ..., n}.
Each cell of the UA set must change its digit when we move from one UA set's permutation to another, so UA set's row containing this cell must have exactly n cells containing digits 1,2, ..., n. The same can be said about UA set's columns and boxes. So, footprint of UA set considered must look in this way - some rows, columns and boxes must contain {1, ..., n}, the rest must contain nothing.

Let's consider UA set's cells relabelling transformation, which relabels UA set's cells only. Let this transformation don't change digit "1" and cyclically replace remaining digits:
1 -> 1, 2 -> 3, ..., n-1 -> n, n -> 2
By means of this transformation we can produce another valid UA set's permutation p' starting from permutation p (one of the n minimal UA set's permutations). Permutation p' is valid because it has the same footprint as each minimal UA set's permutations. But permutation p' has the same digits "1" in the same cells as permutation p. So, both permutations are not minimal. This technique can be applied to each minimal permutation of the UA set considered. So, given UA set has no minimal permutations. This contradicts with statement that given UA set is n-digit n-valent strongly minimal. So, n-digit n-valent strongly minimal UA sets don't exist.

Serg

[Edited: I corrected typos.]

[dobrichev]

Hi Serg,

Your formalism sounds reasonable to me, but let see what others will say.

There are examples with puzzles that cover entire UA with givens. Permuting the givens within the UA always results in a valid puzzle, but minimality could change. So I have in mind that UA are partially isolated subgrids, being prepared for surprises of any kind in this area.

Let's consider sample n-digit n-valent strongly minimal UA set.

What about extension of your proof to n+m digits in n-valent strongly minimal UA set? For n=2 we know such exist.