The New Sudoku Players' Forum

[dukuso]

Tso, am wondering how you managed to find my bumblebeagle site. Not that I was trying to hide it but I'm wondering how you happened to come across it.

Can't remember.

probably mathpuzzle.

And yes, infinite means ... not finite ;-)
You can extend the pattern from n to n+1 or to n+2 or to 2*n or to
2^n or to n^2 or whatever.

Well, you can maybe replace any cell by a complete puzzle
using clues a*9-9+1,..a*9-9+9 where a is the symbol in that cell.

does it work ? I'll have to check.

[gfroyle]

Tso, am wondering how you managed to find my bumblebeagle site. Not that I was trying to hide it but I'm wondering how you happened to come across it.

Although I am not Tso, you may like to know that I was told about bumblebeagle by Ed Pegg (who writes the MathPuzzle column that included the recent extensive survey of Sudoku variants).. in connection with my general interest in minimum number of clues required for Sudoku-like puzzles...

Gordon

[kjellfp]

Maybe of some help:

I'm currently working on a program for finding one representative for each sudoku T-class and S-class, to reconfirm those numbers. This could also be used to for example finding the grid with fewest symmetric 2x2 sub-squares (or most such squares for that matter). This migth be interresting when looking for a 16-clue.

...or anything else. Just give me suggestions on what I should check for each class.

But still, I don't promise anything. Must write the code first, and see if it takes 1 hour or 7 days to run

[Moschopulus]

When you say symmetric 2x2 sub-square, I assume you mean things like this:

12.......
.........
.........
21.......
.........etc

We have been calling sets like this unavoidable (or exchangeable) sets.
An unavoidable set is any set of clues in a completed grid where some permutation of the digits in those cells results in another valid grid.
Any puzzle arising from this grid must have at least one clue from any unavoidable set.

The smallest number of unavoidable sets of size 4 you can have is 0. The grid
x, x+3, x+6, x+1, x+4, x+7, x+2, x+5, x+8, where x is any top row and arithmetic done mod 9, has no unavoidable sets of size 4. e.g. the one posted by dukuso
123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678
which was used in the NP-completeness paper.

The SF grid has just 2 unavoidable sets of size 4.

Here's a grid with just 1 unavoidable set of size 4.
172945386
854361279
963278451
531682947
628794135
749513862
317826594
286459713
495137628

The largest number you can have, I don't know. The grid on this thread http://forum.enjoysudoku.com/viewtopic.php?t=1527&start=0 has 20.

What would be useful in searching for a 16 is a program to find all unavoidable sets in a grid. This may be too much, so also finding all unavoidable sets of size <= k would be very useful, where k is about 15 or 20. This would combine with something I have been working on.

[dukuso]

I found one grid in Gordon's collection without
unavoidables with 2 or 3 different digits

.......1..2..5.....4.......8..1.9.........2.....3......6..7.5.23.....4..1...8....


I'm running this for 20hours now to search for 17s.
3 so far, all already in Gordon's list.


I fixed these cells :

Code: Select all

.......1.
.2..5....
.........
...1.....
......2..
.........
....7.5.2
......4..
1........


[Moschopulus]

Nice. Why don't you search it for a 16?

[dukuso]

Nice. Why don't you search it for a 16?

I did.
Took 3 hours.
none found, of course.

[Moschopulus]

Nice. Why don't you search it for a 16?

I did.
Took 3 hours.
none found, of course.

You mean with those 10 clues fixed?
The grid could still have a 16 ....

[dukuso]

Nice. Why don't you search it for a 16?

I did.
Took 3 hours.
none found, of course.

You mean with those 10 clues fixed?
The grid could still have a 16 ....

yes.
I see.. you want me to do that backward-statistics as with sf

well, it's a bit tedious, not yet automized

[coloin]

I found one grid in Gordon's collection without
unavoidables with 2 or 3 different digits

.......1..2..5.....4.......8..1.9.........2.....3......6..7.5.23.....4..1...8....


I'm running this for 20hours now to search for 17s.
3 so far, all already in Gordon's list.

I have been trying to find more 17s in similarly in some of Gordons list.
There were no other 17s in the two I tried - numbers 1127 and 1144 in his list.

I am still trying in the SF......

I have also been trying different grids - but the number of unavoidables makes it improbable to get a low minimum clue.

So how do you get a grid with low unavoidables....... ?

Your grid above with no 2 or 3 number unavoidables would seem to be useful - but only 3 17s in it.

How many of Gfroyles list come from the same grid ?
SF - 29
16er with 2 solutions - 18
no unavoidables above - 3

I have been thinking about other grids with minimal unavoidables...

I think there are no unavoidables in this grid...yet

------568
------279
------431
---396---
---724---
---581---
674------
235------
891------

this has 108558 sols - the lowest I got with 20 random tries - almost certainly
you can do better than this ....but I suspect there will be less unavoidables in some of the 108558 solutions to this.
[there are no extra clues generated to give you a false low].

Are there better ways to pick these grids ?

[dukuso]

here is the statistics for sudokus per grid for Gordon's 24620 17s:
1:21297 times
2:1115 times
3:171 times
4:67 times
5:13 times
6:17 times
7:6 times
8:1 times
9:1 times
11:1 times
12:1 times
14:1 times
20:1 times
29:1 times


and here are the grids with more than four 17s found in them:



grid, number of 17s found in it, nontrivial unavoidables with 2 digits, ..with3
369845271478612395251397846827569413543781962916234758184926537792153684635478129, 29 ,8,0
537612498894537261126984357341758629672149583985263714213876945768495132459321876, 20 ,16,0
326758491514293687978461325437915268259846713681372954862537149745129836193684572, 14 ,19,0
549832176378461295126597834867149352235786941914253768683914527791625483452378619, 12 ,8,0
189532746365874912427916853213657498946281537578493261634729185751348629892165374, 11 ,13,0
259834176378561294146297835867159342432786951915423768683915427791642583524378619, 9 ,5,0
459781236162539847387246915943867521815923764276415398538694172794152683621378459, 8 ,16,0
326758491514293687879461325437185269258946713691372854162537948745829136983614572, 7 ,16,0
538612497724539861196874352341257689659148273872963514213786945967425138485391726, 7 ,19,0
126437985954186372837952614489361257213579846765824139678243591592718463341695728, 7 ,14,0
874359612251648397963127854745986231328714965196532478417893526589261743632475189, 7 ,16,0
874359612251648397963127854745986231128734965396512478417893526589261743632475189, 7 ,19,0
526948317841732965793561842918254673435679128267183459374826591182495736659317284, 7 ,13,0
932856741451973862678124359769538124385241697214697583843762915197485236526319478, 6 ,13,0
298541637436297815715683249821374596673925184954816372587432961169758423342169758, 6 ,13,0
295817436643295178817346925528934617461782359739651842956423781174568293382179564, 6 ,16,1
937612458854937261126584397341758629672149583589263714213876945768495132495321876, 6 ,13,0
832914567954637812176852349598761234647328951213495786781243695365179428429586173, 6 ,11,0
832714569954632817167859342578961234649328751213475986781243695325196478496587123, 6 ,16,0
795328146382416759614597283478259361239681574156734892867142935541973628923865417, 6 ,15,0
179523684254867319638149752596371248713482965842956137987635421461298573325714896, 6 ,15,0
894137562173526894652984731581493276267851943439672158315269487926748315748315629, 6 ,7,1
874231965593846712162975348945687231731452896286319457627194583458763129319528674, 6 ,16,0
851749236279361548346852791684975123195283674732614859513428967968537412427196385, 6 ,13,0
463951827981273465527648913658317294342589176719426358176894532294735681835162749, 6 ,19,0
534761829819532476672984135493825761761349582258176943146297358325418697987653214, 6 ,14,0
976381452134256789285974316543197628627538941819462573351729864762843195498615237, 6 ,19,0
917542863425386197863179524786495312239861745541723689654938271398217456172654938, 6 ,8,0
179358462534296187628471953356147298912835746847629315763984521291563874485712639, 6 ,15,0
187359462543286197629471385756148239412937856938625714364892571271563948895714623, 6 ,16,0
937628451641795328852143697295384716763251984418967532189436275374512869526879143, 5 ,15,0
283654971567931428914827563758269314436518297192473856379145682821396745645782139, 5 ,17,0
652719438384652971197834562541263789729148653836975214215397846973486125468521397, 5 ,13,0
367912485584376291921485367192657834756834912438129756219543678645798123873261549, 5 ,12,0
748129536621345798395876142532491687469758213187263459814632975976584321253917864, 5 ,14,0
849126537521347869367985142732451698456879213198263475914532786685794321273618954, 5 ,12,1
749126538821345769356978142532481697468759213197263485914532876675894321283617954, 5 ,12,0
761254938524389671938671542847536129653912487219748365186497253475123896392865714, 5 ,13,0
795182346682534971314796825547613298268479513931258764459867132123945687876321459, 5 ,13,0
297354861543168927816927435671593248385742196429816573132689754754231689968475312, 5 ,9,0
679321548524689173381457692253746819148592367796138254937215486465873921812964735, 5 ,19,1
524718693391624875867395421973156284258437916416982537749861352185243769632579148, 5 ,18,0
431576829286493715795812463123758694679124358548369271964285137312947586857631942, 5 ,15,0

[/code]

[coloin]

Thankyou......
Although the SF is not so familiar !

Have you included this one ?

5-2---4--
---71---3
---------
-----46--
-7-2-----
-1-------
6----2---
----3--1-
4--------

There are 18 ways to add either the 8 or the 9 clue for a 17.
Quite possibly it is the grid with 20 17s.


Surely The SF has several non trivial 3 digit unavoidables ?
{24,25,64,65,74,75} is one. [As per Gfroyle's representation of the grid]

Any ideas how to make a grid without them ?

[dukuso]

Have you included this one ?

5-2---4--
---71---3
---------
-----46--
-7-2-----
-1-------
6----2---
----3--1-
4--------

There are 18 ways to add either the 8 or the 9 clue for a 17.
Quite possibly it is the grid with 20 17s.

a 16 with 2 solutions ? That's strangely familiar !

[coloin]

a 16 with 2 solutions ? That's strangely familiar !

Well...it is familiar. Posted by Gfroyle ages ago. So not even strange.
It is not quite the same grid otherwise the real SF would have more than 29 17s.
So where does it come in on your chart ? ! [the 20 ?]

Maybe this grid deserves a closer look.

C

[kjellfp]

Just a question:

When you all talk about unavoidable sets, are you restricting yourselves down to the minimal sets only?

An unavoidable is minimal if it contains no proper unavoidable.

Its easy to check if an unavoidable is minimal: It is minimal if and only if removing any element makes it avoidable (avoidable is of course the same as "not unavoidable"...). This process could also be used to finding at least one minimal subset.

It's (almost) only interresting looking at minimal sets when dealing with unavoidables. But maybe they are too many also? I haven't tried anything on computer yet, so I don't know.