High clue tamagotchis

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

#120

Postby dobrichev » Sun Sep 19, 2010 4:29 pm

One more 39
Code: Select all
.5718......3.56...6..3.....2.6518.7474526.1.8........23.2.45...578621..3.6483....
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: High clue tamagotchis

Postby eleven » Mon Sep 20, 2010 8:17 am

Ok, about half of the found 37's are in the big list of dobbed 37's, which i had not added to my known 37's. So its not that dramatic, what i can find with {-1+1} plus dobbing.
Over night i found about 200000 37's and 1200 38's (no 39) with this method. I guess, i can be through the dobbed list in 2,3 weeks. Lets see, what we get.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: High clue tamagotchis

Postby dobrichev » Mon Sep 20, 2010 3:39 pm

Here are two more 39s
Code: Select all
.5.1.9.36.9.......1.3..6.892..6...5.56..17.23.315.2.673.2.....8.8...1.9291.2.83.5
........669..73.141....678.2.........3..92871819.37.423.2.6.1.8..1.2..6.96.3.8.27


With them I finished the easy work in processing my collection of multi-solution 37s (=38-1) and 38s (=39-1) until closure.
    The seed consist of:
  • 122 valid minimal 39s
  • 59796 valid minimal 38s
  • 2243908 multi-solution 37s+38s obtained by the above

The collection originated from eleven's and havard's published list of 38s and 39s.
A simple clue relabeling (depth 3) was done on most of the puzzles, and permutation of values within totally covered unavoidable sets is done.

I will send the 38s to eleven to help his "production" gotchi. If somebody else is interested, let me know and I'll publish them somewhere.

MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

+2

Postby dobrichev » Wed Sep 22, 2010 10:22 am

two more 39s
Code: Select all
45..8.23.8.9.3..45.2..5...92.6....97.3....6.49.....32.39856.47257....96.6.2....53
.571.923612..567.9..973..15274.....3.................2.1...39.4.459.13279.2.7..61
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: High clue tamagotchis

Postby coloin » Wed Sep 22, 2010 10:42 am

Only you know how hard it is to find those puzzles !

Asuming that it is potentially possible to have a 40...... [but maybe unlikely]

:idea: Not totally sure on this but......
Can we assume that its theoretically impossible to have a minimal 41 [41 givens, 41 uniquely covered unavoidable sets - but only 40 empty cells] ?

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: High clue tamagotchis

Postby dobrichev » Wed Sep 22, 2010 12:16 pm

coloin wrote:Only you know how hard it is to find those puzzles !

Asuming that it is potentially possible to have a 40...... [but maybe unlikely]

:idea: Not totally sure on this but......
Can we assume that its theoretically impossible to have a minimal 41 [41 givens, 41 uniquely covered unavoidable sets - but only 40 empty cells] ?

C


ravel, havard, and eleven know how hard it is to find them. I am still growing their seed.

One of the latest 2 39s is (probably) a result of an error in my data synchronization. It should be raised before.
The other is a result of partial expansion of the search space to multi-solution 36s (=37-1 or 38-2 or 39-3).
I am still fixing bugs in the code and, in contrast to eleven, can't estimate the efficiency or the potentiality of the method.

About 40s and 41s - have no idea. I don't believe in miracles. But your question is reasonable - there must be some logical clue maximum with guaranteed redundancy above. One trivial maximum is "8 clues in a row/col + empty box" = 81-9-8-4 = 60 clues.

From low-clue puzzles we know there are solution grids with "avoidable" regions of size 64. "Avoidable" region is a region not covering any of the unavoidable sets. What is the minimum size? How to locate maximum clues inside and minimum outside? Maybe this is not the right way - there is no known 17 sharing solution grid with known 39. Also the grids most rich in U4 have no known 39s.

Edit: no ronk but ravel found first 38

MD
Last edited by dobrichev on Wed Sep 22, 2010 3:05 pm, edited 1 time in total.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: +2

Postby gsf » Wed Sep 22, 2010 1:00 pm

dobrichev wrote:two more 39s
Code: Select all
45..8.23.8.9.3..45.2..5...92.6....97.3....6.49.....32.39856.47257....96.6.2....53
.571.923612..567.9..973..15274.....3.................2.1...39.4.459.13279.2.7..61

can you post all of the known 39s
thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: +2

Postby ronk » Wed Sep 22, 2010 1:16 pm

gsf wrote:
dobrichev wrote:two more 39s
Code: Select all
45..8.23.8.9.3..45.2..5...92.6....97.3....6.49.....32.39856.47257....96.6.2....53
.571.923612..567.9..973..15274.....3.................2.1...39.4.459.13279.2.7..61

can you post all of the known 39s

I believe eleven has been keeping the list up to date here. Judging by the edit date, these last two are not there.

dobrichev wrote:ronk, havard, and eleven know how hard it is to find them.

Thanks, but I've only been an interested observer. :)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: +2

Postby gsf » Wed Sep 22, 2010 1:50 pm

ronk wrote:I believe eleven has been keeping the list up to date here. Judging by the edit date, these last two are not there.

thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: +2

Postby dobrichev » Wed Sep 22, 2010 3:01 pm

ronk wrote:
dobrichev wrote:ronk, havard, and eleven know how hard it is to find them.

Thanks, but I've only been an interested observer. :)

oops, i meant ravel - for his first 38.
Thank you for motivation :)
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: High clue tamagotchis

Postby eleven » Sat Oct 02, 2010 3:15 pm

Expanding the 1.7 mio dobbed 37's is finished now. It brought 14 more 39's. I updated the list in the first post of this thread.

Now i have 6.75 mio 37's and 82456 38's. I uploaded the 38's to zippyshare sudoku38.zip. I never added havard's public 38s to the gotchi, because i wanted to know, if it finds them on her own. It did for about half of them, and one of the 2 39's.
It did not find 5 of dobrichev's 39's (and about 1000 38's in his list), so i hope, he will apply his clever method to my new 38's too.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: High clue tamagotchis

Postby dobrichev » Sat Oct 09, 2010 10:28 pm

eleven wrote:... It brought 14 more 39's.

Congratulations!

eleven wrote:... I never added havard's public 38s to the gotchi, because i wanted to know, if it finds them on her own. It did for about half of them, and one of the 2 39's.
It did not find 5 of dobrichev's 39's (and about 1000 38's in his list), so i hope, he will apply his clever method to my new 38's too.

Probably these 5 39s and 1000 38s came from Havard's 38s and unprocessed by you Havard's 39.

One potential difference in our methods is that while searching for twins (dobbing :)) I am processing literally ALL the solutions of the complementary puzzle. Most of them result in non-minimal puzzles, which after minimization become to 20...33 clue minimal puzzles. I am ignoring non-minimals. Rare a multi-solution dead-end puzzle is obtained - adding clues makes other clues redundant. I am ignoring these too.
I don't know whether this method differs from finding UA sets and permuting values within each separate UA.

I processed only 39s and 38s, removing clues down to multi-solution 37 then adding until minimal unique puzzle is found. Did the same for all new puzzles.

Finally I partially dig into top multi-solution 36s. These with empty row are at the top. No more than million of them are processed.

I kept all processed multi-solution puzzles in ordered list in RAM, this limiting the method to some total amount of puzzles.

My last attempt is to apply {-4} to known 124 39's. After removal of duplicates the list contains 10020143 multi-solution 35's.
Currently the efficiency of {+} is discouraging, and I have no time to play with possible further optimizations.
Nevertheless after ~24 hours all 124 39's have been reinvented. After 160 hours of CPU time 4016 puzzles are found (including 37's, s38's, and 124 39's). Waste of energy, I think.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

40-clue multi-solution minimal

Postby dobrichev » Thu Oct 14, 2010 12:49 am

This is a 40-clue multi-solution minimal puzzle.

Code: Select all
.4.....1.5...12.34.13.452.6....71....752...61.8156..72..43.6..7.37.5.62..5..27.43


It proves that it is possible 40 clues to coexist w/o redundancy.
Unfortunately adding more clues makes others redundant.
Isn't it a matter of chance that there are still uncovered unavoidable sets in this case?

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: High clue tamagotchis

Postby eleven » Thu Oct 14, 2010 8:29 am

Congratulations on finding the first minimal puzzle with 40 clues.

However it is no surprise, that you can get higher, when the uniqueness requirement is dropped. Maybe you can find more, when you take a high weighted 39 and remove a clue which leads to many solutions. If you are lucky, you can replace it by 2 more minimal clues.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: High clue tamagotchis

Postby AR4793 » Thu Oct 14, 2010 8:39 pm

eleven wrote:Congratulations on finding the first minimal puzzle with 40 clues.

However it is no surprise, that you can get higher, when the uniqueness requirement is dropped. Maybe you can find more, when you take a high weighted 39 and remove a clue which leads to many solutions. If you are lucky, you can replace it by 2 more minimal clues.


dobrichev didn't and didn't claim to have found a minimal 40 clue puzzle.

The puzzle he posted has 16 solutions. However all the clues are "minimal" in the sense removing anyone of them increases the number of solutions. He also pointed out that a clue can't be added to any position without making other clues redundant.

Regards,
Herb
AR4793
 
Posts: 13
Joined: 26 September 2010

PreviousNext

Return to General