Minimal Unavoidable Set with 49 permutations

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

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

Postby Serg » Sun Nov 18, 2012 1:14 pm

Hi, dobrichev!
dobrichev wrote:Your formalism sounds reasonable to me, but let see what others will say.

I am waiting for replies too, because I feel my proof is too simple, so I can be wrong.
dobrichev wrote: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.

If I undersood you correctly, you say about twin puzzles. Please, clarify - in what way puzzle's minimality could be changed by permuting UA set formed by givens (clues)? I'd say UA is fully isolated subgrids. I think UA set can be fully explored without solution grid knowlege. (Maybe I am wrong.)
dobrichev wrote:
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.

It would be nice to get proof of m-digit n-valent (m > n) strongly minimal UA sets non-existence. In that case we would know all strongly minimal UA sets are bivalent. But I cannot extend my proof yet to this case :?.

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

twin puzzles minimality

Postby dobrichev » Sun Nov 18, 2012 2:23 pm

Serg wrote:Please, clarify - in what way puzzle's minimality could be changed by permuting UA set formed by givens (clues)?

Here is an example
Code: Select all
.................1..1..234......1.3...4.2.51..6.4..2.7..32..15..8..13...9...5.... minimal
..........................................R|................||................... UA4
.................1..1..234......1.3...4.2.15..6.4..2.7..32..51..8..13...9...5.... non-minimal
.................1..1..234......1.3...4.2..5..6.4..2.7..32..51..8..13...9...5.... minimal

In 2D
Code: Select all
.........
........1
..1..234.
.....1.3.
..4.2.51.
.6.4..2.7
..32..15.
.8..13...
9...5.... minimal

.........
.........
.........
.........
......RX.
.........
......XX.
.........
......... UA4 with R redundant when 1

.........
........1
..1..234.
.....1.3.
..4.2.15.
.6.4..2.7
..32..51.
.8..13...
9...5.... non-minimal, "1" at r5c7 is redundant
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

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

Postby Red Ed » Sun Nov 25, 2012 10:20 pm

Serg wrote:I've found a proof of n-digit n-valent strongly minimal UA sets (n > 2) impossibility.

Yep, conceptually that is straight from The Book. Well done.
Red Ed
 
Posts: 633
Joined: 06 June 2005

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

Postby Serg » Mon Nov 26, 2012 11:05 am

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

Yep, conceptually that is straight from The Book. Well done.

Thanks. What Book do you mean?

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

Re: Minimal Unavoidable Set with 49 permutations

Postby dobrichev » Mon Nov 26, 2012 1:48 pm

it depends of religion, i think
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Minimal Unavoidable Set with 49 permutations

Postby Red Ed » Mon Nov 26, 2012 8:12 pm

"The Book", per Erdős; we'd all like a copy.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Minimal Unavoidable Set with 49 permutations

Postby Serg » Tue Nov 27, 2012 10:10 pm

Hi, Red Ed!
Red Ed wrote:"The Book", per Erdős; we'd all like a copy.

I am confused but I've never heard before about Pál Erdős - famous hungarian mathematician (see http://en.wikipedia.org/wiki/Paul_Erd%C5%91s). Because of your post I got to know his biography. Words "that is straight from The Book" is the most honorary praise that one mathematician can expect to hear from another. But of course you're joking.
In any way thank you for interesting link.

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

Re: Minimal Unavoidable Set with 49 permutations

Postby Red Ed » Thu Nov 29, 2012 11:05 pm

My point is: your proof is quite clearly the one & only one "right" way to solve this. Thus, "from the book". Well done (again).
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Minimal Unavoidable Set with 49 permutations

Postby m_b_metcalf » Fri Nov 30, 2012 10:18 am

Red Ed wrote:My point is: your proof is quite clearly the one & only one "right" way to solve this. Thus, "from the book". Well done (again).

This reminds me of an attempt I made in 2008 to get all this sort of informtion into a real printed book, where it might be more accessible and certainly better organized that it is here, spread over two fora and many threads. At the time I had a major publisher wanting to publish such a book but I found no-one willing to write it. Are there any takers now? If so, I'd be willing to approach the publisher again. In the meantime, a book on the mathematics of sudoku has been published (look here), but is not as comprhensive as I imagine such a book should be -- written by mathematicians for mathematicians, rather than for a general audience . (I'm not a mathematician, just a concerned bystander.).

One solution would be to have multiple authors working under an overall editor. The sort of topics it might cover I list below (not exhaustive). If ever the Programmers' and the Players' Fora disappear, huge amounts of work and knowledge might be lost forever.

Please feel free to contact me by PM if necessesary.

Regards,

Mike Metcalf

Code: Select all
1. Introduction: origins and spread

2. Properties of the solution grid: number, isomorphisms, ...

3. Properties of (minimal) puzzles: Minimum and maximum number of clues, relative frequencies,
                          distributions of number of values, r/c/b population,
                          symmetry of clues, symmetry of values, ...

4. Properties of pseudo-puzzles: unavoidable sets, megaclues, ...

5. Logical solution techniques: from singles up to fancy loops, chains, whips, braids etc.

6. Programming techniques to solve puzzles: DLX and other (inferior) methods.

7. Programming techniques to generate puzzles: bottom up, top down, templates, ...

8. Programming techniques to generate solution grids: complete set (gsf), unbiased and biased subsets

9. Patterns: legal and illegal patterns, 9plus12 etc.

10. Rating puzzles

11. The Patterns Game

12. Variations: samurai, massive, ...

User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8418
Joined: 15 May 2006
Location: Berlin

Re: Minimal Unavoidable Set with 49 permutations

Postby Serg » Wed Dec 05, 2012 7:26 am

Hi, Mike!
To my mind your idea to publish a book containing both fora "knowlege base" is not implementable - too many people were involved, too many topics were discussed, too many different approaches to the same problems were demonstrated. Maybe a little bit more realistic could be an idea to publish periodically articles on selected topics. Chief editor (I think your person is ideally suited for this work) should periodically select a theme and author for article. These articles can be published in a separate division of this forum, for example. If chief editor is not sure - what theme should be selected - he can manage fora members poll concerning possible (interesting) article themes.

I am not sure this thread is proper place for discussions about the topic concerned. Maybe it is worth opening separate thread.

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

Previous

Return to General