The New Sudoku Players' Forum

[Mathimagics]

Hi Mladen,

That was entertaining - lots of footprints all over this topic, not to mention footprints IN it … I was a little late arriving at this forum so I missed all the fun

Meanwhile, I'm getting absolutely nowhere coming to grips with of your suggestion for an improved method finding UA's, particularly larger ones.

Could you put some more flesh on that description, please?

Cheers
MM

[blue]

Are minimal UA's of higher degree just unions of degree 1 UA's?

I'm assuming (...) that by "minimal" and "of higher degree", you mean that removing any cell from U (or equivalently, adding any clue from U, to P), would reduce its degree ... reducing it by one (and no more), necessarily.

The answer is "yes", and in fact, U would be a union of minimal UA's of degree 1.

Assuming the definition of "minimal" from above, it follows from the fact that for a puzzle, Q, to have S as its unique solution, it is necessary and sufficient for Q to "hit" every minimal UA for S.

With that in mind, if U is any unavoidable set of S, and P is S - U, as before, then since P already hits the unavoidable sets that are not subsets of U, the "degree of U" would be the size of the smallest hitting set for the minimal UA's that are wholy contained in U.

If U is "minimal", in the sense that removing any cell from U, reduces its degree, then every cell in U, must "hit" at least one minimal UA that is contained in U -- or else the size of the smallest hitting set for those UA, would go unchanged, and the (correspondingly) smaller U, would have the same degree as the original.

In the end then, if U is minimal in the sense above, then every cell of U is contained in at least one minimal UA that is a subset of U, and so U itself, must be a union of minimal UA's.

Cheers.

@Dobrichev: Hi. I vaguely remember the UA's thread.
A few friendly arguments, for a while, I recall ... but I don't remember much else.
It would/will(?) be nice to see what Red Ed and JPF settled on, for "final" definitions.

Someone else might be interested in the "Grids with minimal UA18s for all 2-row,2-col,2-digit UA sets".
I remember being a useless curiosity, in the end. No 16's in them, and a long time checking them for 17's

[Serg]

Hi, blue!

Let's call solutions of P unavoidable set permutations (in accordance with Red Ed's terminology). If every cell of unavoidable set's permutation contains unique value (comparing it with all other permutations of considered unavoidable set), this permutation is called minimal. If an unavoidable set contains at least one minimal permutation, such unavoidable set called minimal. If all unavoidable set's permutations are minimal, unavoidable set is strongly minimal, otherwise unavoidable set is weakly minimal.

Everything seems correct, except the part that I underlined.

I was wrong. Weakly minimal UA sets is rather complicated theme. I corrected my post.

In the example(s) with valency 3, if S = (P + U), S2 = (P + V), and S3 = (P + W) are the 3 solutions to P, then V and W are unavoidable sets in S2 and S3 (respectfully). Neither one is a minimal UA for its respective grid, though, since each of them contains a (smaller) U4.

On the other hand, {U,V,W} is the set of permutations for U, and for V and W as well, and that set includes U, which is minimal.
The "contains at least one minimal permutation" concept, then ... as applied to V, for example ... isn't a guarantee that V itself, is minimal (in the usual sense).

You are right.

BTW: You do understand (please, I hope) ... that above, {U,V,W} is a just set of permutations (of a single "seed", in principle) ... and that only U,V or W, individually, could be an "unavoidable set" ... minimal, strong, weak, or otherwise ?

Yes, U,V and W are unavoidable sets each, defined for its own solution grids (S, S2, S3). Property "minimal" characterizes individual unavoidable set, but properties "strong" and "weak" characterize set {U,{V,W}}

You use, twice, phrases like "contains a minimal permutation", where "has a minimal permuation" should appear instead.
For example: "Usually weakly minimal unavoidable set contains 1 minimal permutation only".
It should be: "Usually [a] weakly minimal unavoidable set has 1 minimal permutation only" ... that being the set itself.

I agree with you. Corrected.

Serg

[dobrichev]

It would/will(?) be nice to see what Red Ed and JPF settled on, for "final" definitions.

It would be. They are lost.

The startup JPF's definition from the context seems to be this from 22 Nov 2008 03:29, pointed by Pat.

I am not really satisfied with my definition of unavoidables:

Let G be a solution-grid, and U and V be two subsets of G defined as follow:

Code: Select all

   G................U................V           
 *-----------*    *-----------*    *-----------*
 |123|456|789|    |1..|4..|...|    |1..|4..|7..|
 |457|189|236|    |4..|1..|...|    |4..|1..|2..|
 |689|327|415|    |...|...|...|    |...|...|...|
 |---+---+---|    *-----------*    *-----------*
 |216|534|978|     
 |394|871|562|     
 |578|962|143|     
 |---+---+---|     
 |765|213|894|     
 |841|695|327|     
 |932|748|651|     
 *-----------*      

Using my definition U and V are considered as UA of G.
If I understand correctly, it's the same thing when using Red Ed-1's and Moschopulus's ones.
With all those definitions U is minimal, V is not.

I would prefer to add that G-U or (G-V) has to be maximal*, which will exclude V but not this one:

Code: Select all

 *-----------*
 |1..|4.6|..9|
 |4..|1.9|..6|
 |...|...|...|
 *-----------*

*a subgrid A of G is maximal if its solutions S1,S2,...,Sp are such that: A=S1 ∩ S2 ∩ ... ∩ Sp

JPF

Unanswered criticism follows...

Red Ed's definitions discussion is more complicated and I can't represent it.

In addition

Maybe this link will provide some additional insight.

In light of Red Ed's post I've extended the <Sudopedia entry> slightly with some non-contentious stuff.

The extension seems to be lost, looking at the last modification date in the survived mirror of the respective sudopedia page.

All other posts are from me, Blue, and Serg.

[dobrichev]

Meanwhile, I'm getting absolutely nowhere coming to grips with of your suggestion for an improved method finding UA's, particularly larger ones.

Could you put some more flesh on that description, please?

Maybe I underestimated the complexity of UA minimization process.
Nevertheless, assume you have a fast and sufficiently random generator of valid solution grids. (@Blue, can you point the one provided by Red Ed?)
Assume you are not greedy. (actually all we are greedy in wanting the faster algorithms)

Scenario 0:

Code: Select all

take the chosen grid G
while (! ctrl-C) {
  generate a random grid T
  compare all cells of G to the respective cells of T and compose the possibly non-minimal unavoidable set U
  if U has 65+ cells then discard T and go to next random grid generation
  compose a subgrid X that matches G outside U and is empty inside U
  for each cell position P in U {
    add G[P] as given to X
    call solver and test X for a second solution
    if 2+ solutions are found then discard T and go to next random grid generation
    reset X[P] as non-given
  }
  add U to your list
}

Doing so, almost 100% of the UA sets will be identified as non-minimal after few solver calls.
If the random grid generation is the bottleneck, then

Scenario 1

Code: Select all

take the chosen grid G and add it to grid list GG
apply some VPT on G, remember the transformations, and add the grids to GG
while (! ctrl^C) {
  generate a random grid T
  for each G in GG apply the same logic as in Scenario 0
  on success, apply the respective reverse VPT on U and add it to your list
}

Scenario 2+
Being greedy, see what happens and do more optimizations

Adding a counter for detected non-minimals will give an estimation for the proportion of minimals / non-minimals, and we know the number of minimals + non-minimals.

[blue]

Nevertheless, assume you have a fast and sufficiently random generator of valid solution grids. (@Blue, can you point the one provided by Red Ed?)

I've finally got round to posting my generator:
http://forum.enjoysudoku.com/unbiased-grid-generation-b2347-method-t31236.html

WARNING: it doesn't do the last step of picking a random validity-preserving transform to "spin" the grid. That makes no difference, though, for the algorithms discussed here.

The missing "last step" that he mentioned, would be important in this case.

[Mathimagics]

Thanks, Mladen!

I will explore the method and report back.

Meanwhile, I have looked at your valency 145 examples and found them rather astounding, "beauties" indeed!

The 6 examples all define (minimal) UA's of size 54. Did you find any correlation between high valency and UA size? Might higher valency UAs be found by looking at the biggest known minimal UA's, eg 62's?

Cheers
MM

[dobrichev]

@Blue, thank you for the link.

Did you find any correlation between high valency and UA size? Might higher valency UAs be found by looking at the biggest known minimal UA's, eg 62's?

The weakly minimal UA portion trend to be larger for the larger UA, at least due to the more room open for exotic permutations.
But in general large UA and high-valency UA preach different religions and mixed marriages are rare.

[Mathimagics]

Ok, my initial report on Mladen's suggestion for an alternative approach to the "Find minimal UA's" problem.

Problem: Given solution grid S, find as many minimal UA's as possible

Method A: ("reduction ad infinitum")

• Reduce S, by randomly removing clues until the result G has multiple solutions

• Extract the UA implied by G (my fsss2 solver has a function to do this, but it can be done manually by comparing the solutions)

• Repeat

Pros: always identifies a minimal UA
Cons: heavy bias towards UA's of smaller size, so there are many duplicates, and the great majority of minimal UA's (sz > 20, say) are hard to find

Method B: (Mladen's suggestion)

• Take random grid G, set U = cell difference of (S, G)

• Test U for minimality

• Repeat

Minimality testing:

• P = S - U has multiple solutions

• for every cell position u in U, P + S[u] has 1 solution

(Optional variant BX: test each G against all isomorphisms of S)

Pros: appears to solve the bias problem of method A
Cons: minimal UA's very rarely encountered

I have had both a FindUA-B and a FindUA-BX running for well over an hour, BX has turned up two UA's (a 44 and a 47), nothing yet for B.

[dobrichev]

Then sorry for the misleading.
Lost in the big numbers.

"All isomorphisms of S" sounds quite big to be practical. Unless you forget the relabelling.

How many non-minimals produced those two minimals in BX method?

[Mathimagics]

No apology necessary, it was worth a try, and at least tells us something about the real difficulty of this exercise …

(BTW: I meant just the VPT's (3359232), that should have read "All isomorphisms except relabelling …")

B remains silent, it has tried 450 million random G's so far.

But BX has found a 3rd MUA, size 48. Yippee!! (Elapsed time now 3h 40m )

For BX method, the number of U's considered is 3359232 per G, one for each T = VPT(S). If the intersection (T, G) has 17 or more cells, then U = T - G has 64 or less, and so we proceed to actually test it. This happens only about 2% of the time.

The random grid counts for BX at the time of finding each minimal UA: 3367, 5159, 13839

[dobrichev]

2% discarded being of size 65+, or 98% discarded?

You can consider the exercise statistically meaningful and stop processing after finding the first UA0

[Mathimagics]

2% discarded being of size 65+, or 98% discarded?

98% discarded, of course. If the reverse was true it might find a hell of a lot more minimal UA's !! (And pigs might fly …. )

Anyway, I can't stop it just now, it has just found a FOURTH one (a 50) !!!! Ring the bells …

It's just getting warmed up!

[dobrichev]

OEIS Search: seq:44,47,48,50 gives 51 results.
From the first page, I liked

A235035 Numbers n for which A234742(n) = n: numbers n whose binary representation encodes a GF(2)[X]-polynomial such that when its irreducible factors are multiplied together as ordinary integers (with carry-bits), the result is n.

[Mathimagics]

Wonderful!

You seem to have time on your hands, why aren't you busy thinking about a better UA finder???

The 5th UA is coming soon, I can smell it …