Minimal Unavoidable Set with 49 permutations

Everything about Sudoku that doesn't fit in one of the other sections

Re: Minimal Unavoidable Set with 49 permutations

Postby dobrichev » Mon Oct 22, 2012 5:20 am

Serg wrote: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.

Serg wrote: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
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

145

Postby dobrichev » Tue Oct 23, 2012 7:56 pm

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
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

No 3-digit valency 3 strongly minimal unavoidables

Postby Red Ed » Wed Oct 24, 2012 9:58 pm

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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: No 3-digit valency 3 strongly minimal unavoidables

Postby Serg » Thu Oct 25, 2012 5:15 pm

Hi, Red Ed!
Your posts are usually "brain food" for me, but your last post is even puzzle :) .
Red Ed wrote: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.
Red Ed wrote: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
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Minimal Unavoidable Set with 49 permutations

Postby Red Ed » Thu Oct 25, 2012 6:25 pm

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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Minimal Unavoidable Set with 49 permutations

Postby Serg » Thu Oct 25, 2012 7:52 pm

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

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: 145

Postby Serg » Thu Oct 25, 2012 8:04 pm

Hi, dobrichev!
dobrichev wrote: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 :shock: ! 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
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Minimal Unavoidable Set with 49 permutations

Postby coloin » Thu Oct 25, 2012 11:20 pm

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.
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: No 3-digit valency 3 strongly minimal unavoidables

Postby dobrichev » Sun Oct 28, 2012 8:18 am

Red Ed wrote:... So there cannot exist any 3-digit valency 3 strongly minimal unavoidables after all.

Serg wrote: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
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: 145

Postby dobrichev » Sun Oct 28, 2012 8:20 am

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


Thank you!
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

145s' symmetries

Postby dobrichev » Sun Oct 28, 2012 8:29 am

coloin wrote: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.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: No 3-digit valency 3 strongly minimal unavoidables

Postby Red Ed » Sun Oct 28, 2012 8:13 pm

dobrichev wrote: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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

The collection is available for downloading

Postby dobrichev » Fri Nov 16, 2012 12:30 pm

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
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

No n-digit n-valent strongly minimal UA sets

Postby Serg » Sun Nov 18, 2012 7:42 am

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.]
Last edited by Serg on Sun Nov 18, 2012 12:49 pm, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: No n-digit n-valent strongly minimal UA sets

Postby dobrichev » Sun Nov 18, 2012 12:10 pm

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.

Serg wrote: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.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

PreviousNext

Return to General