The New Sudoku Players' Forum

[Red Ed]

Hmm... I await your results

The lower bound for your strangely familiar grid has now leapt from 9 to ...(drum roll)... 10. Bah, rubbish.

Will think of more subsets to check and then report back. On the plus side, my program now computes these lower bounds within a few seconds rather than a few minutes. That's likely to be important when I chuck more chains into the mix ...

[Red Ed]

Hmm, looks like the sets we're interested in can be quite exotic. For example, in this nearly-completed grid ...

Code: Select all

639|241|785
284|765|193
5..|983|624
---+---|---
123|857|946
796|432|851
458|619|237
---+---+---
3.2|.78|.69
86.|.94|372
9..|326|.18

... you can have either of the following two ways of filling the gaps:

Code: Select all

...|...|...     ...|...|...
...|...|...     ...|...|...
.17|...|...     .71|...|...
---+---+---     ---+---+---
...|...|...     ...|...|...
...|...|...     ...|...|...
...|...|...     ...|...|...
---+---+---     ---+---+---
.4.|1..|5..     .1.|5..|4..
..1|5..|...     ..5|1..|...
.75|...|4..     .47|...|5..

Constructing sets like this is going to be a pain. Bleurrgghhh...

[coloin]

This is the 2nd 17 of the 29

xxx | 24x| 7xx
x8x | xxx| x9x
x1x | xxx| xxx
-----------------
xxx | 8xx| xx6
7xx | xxx| xxx
4xx | xxx| 2xx
-----------------
3xx | x7x| xxx
xxx | xxx| xx2
xxx | xx6| x18

If we calculated which number when removed gives the least possible combinations. Or better still if we calculated which group of say 3 numbers which when removed gives the least number of possible solutions - this maybe are the numbers to remove.

Then ......substitute the remaining possibilities of 2 numbers...perhaps 64*66 options....... to get a 16.

Maybe this is what Gfroyle is busy doing !

[coloin]

What about this option

The numbers that you dont remove first are the numbers which are necessary to start the puzzle off -

Letters down the side. Numbers across the top.

There are three start offs in no 2 "17".
2@C8 vital numbers are
xxx | 2xx| xxx
xxx | xxx| x9x
xxx | xxx| xxx
-----------------
xxx | xxx| xxx
xxx | xxx| xxx
xxx | xxx| 2xx
-----------------
xxx | xxx| xxx
xxx | xxx| xx2
xxx | xxx| xxx

7@F9 and H8 vital numbers are
xxx | xxx| 7xx
xxx | xxx| xxx
xxx | xxx| xxx
-----------------
xxx | xxx| xx6
7xx | xxx| xxx
xxx | xxx| 2xx
-----------------
xxx | x7x| xxx
xxx | xxx| xx2
xxx | xxx| x18

8@H1vital numbers are
xxx | xxx| xxx
x8x | xxx| xxx
xxx | xxx| xxx
-----------------
xxx | 8xx| xxx
7xx | xxx| xxx
4xx | xxx| xxx
-----------------
3xx | xxx| xxx
xxx | xxx| xxx
xxx | xxx| xx8


Combined the non - vital numbers are

xxx | x4x| xxx
xxx | xxx| xxx
x1x | xxx| xxx
-----------------
xxx | xxx| xxx
xxx | xxx| xxx
xxx | xxx| xxx
-----------------
xxx | xxx| xxx
xxx | xxx| xxx
xxx | xx6| xxx

The 1 is paired with a 3@C6,3@A1 and 1@A6.

So we only have those and one other number to play with. Not looking good then ! I think we need a grid without pairs - if there is one.
Perhaps we could start off with 2 out of the 3 "start offs"

[gfroyle]

Constructing sets like this is going to be a pain. Bleurrgghhh...

Actually I don't think it will be so bad... now I am getting excited at the prospect of actually PROVING something (even just for a single grid).

Here's the process... start off by listing all of the easy "exchangeable" sets - in other words, sets of cells whose entries can be permuted to get a new grid, for which we must therefore select at least one cell in our clue set.

Now find a 16-set of clues that hits all of those sets (this is an instance of the NP-complete problem called MINIMUM HITTING SET) and is hence a candidate for a critical set (this terminology "critical set" is the right term for a set of entries in a Latin square that permits a single completion, so we might as well adopt it for Sudoku sets as well).

Two things happen: we either have a 16-clue solution OR not. If not, then why not? Because there are two or more completions... but then this will IDENTIFY another exchangeable set, namely the set of positions in which the "second" grid differs from our target grid. So now add this to the collection (of course, deleting any supersets of the new one). Now find a new 16-clue hitting set (which will NOT be the original one) and repeat the process.

At the end of the day we either have a 16-clue solution or an instance of MINIMUM HITTING SET with no 16-element hitting sets...

The one thing I don't know as yet is how big the set of exchangeable sets will grow...

[Red Ed]

Here's the process...

I wondered about doing the search that way, but I was put off by the thought of winding up with quite large exhangeable sets (you can have millions of wrong completions of a 16-clue grid, some of which presumably differ from the target by a large amount). I'd be more tempted, at this early stage, to expand my search for exchangeable sets just by looking at the target grid. For example, you could get the (not particularly small) exchangeable set I showed above by searching for ways of manipulating digits {1,4,5,7}. Perhaps I'll add this onto my to-do list.

[dukuso]

gordon wrote:

>Red Ed wrote:
>
>>Constructing sets like this is going to be a pain.
>>Bleurrgghhh...

these sets are just the connected components in the
2^9 subgraphs of the "general sudoku graph"
determined by a subset of the symbols.
Well, this doesn't yet include 2 complete rows etc.

>Actually I don't think it will be so bad... now I am getting
>excited at the prospect of actually PROVING something (even
>just for a single grid).
>
>Here's the process... start off by listing all of the easy
>"exchangeable" sets - in other words, sets of cells whose
>entries can be permuted to get a new grid, for which we must
>therefore select at least one cell in our clue set.
>
>Now find a 16-set of clues that hits all of those sets (this
>is an instance of the NP-complete problem called MINIMUM
>HITTING SET)

usually you needn't find the MINIMUM hitting set, but just
a small one. One of size 16 to be precise.

>and is hence a candidate for a critical set (this
>terminology "critical set" is the right term for a set of
>entries in a Latin square that permits a single completion, so
>we might as well adopt it for Sudoku sets as well).

yes

>Two things happen: we either have a 16-clue solution OR not.
>If not, then why not? Because there are two or more
>completions... but then this will IDENTIFY another
>exchangeable set, namely the set of positions in which the
>"second" grid differs from our target grid.

this could be a pretty large set, though.
Large sets are not so useful here.

>So now add this to
>the collection (of course, deleting any supersets of the new
>one). Now find a new 16-clue hitting set (which will NOT be
>the original one) and repeat the process.
>
>At the end of the day we either have a 16-clue solution or an
>instance of MINIMUM HITTING SET with no 16-element hitting
>sets...
>
>The one thing I don't know as yet is how big the set of
>exchangeable sets will grow...

... and how long that day will be.
But you might get an idea of what is going on before the end of
the day and we will get a better "feeling" whether a 16-critical set
is possible or not.

[dukuso]

coloin wrote:

>A page from frazer's ste explains the 275 :
>http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html
>as well as the encompassing:
>http://www.shef.ac.uk/~pm1afj/sudoku/
>[Although I am still baffled by the nomenclature of the
>representitive groups -[ he did explain it on page 17 - one
>before your posts]].

Ah, I see (saw it earlier but forgot the number).
Conjugacy-classes. And I was wondering about the
strange factorization of 275...

>I still cant follow yours !
>dukuso wrote:
>must have explained it earlier
>
>
>That aside, in the quest for the 16, it would be interesting
>to see what group the 17 is in - and how many similar grids
>there are. Although it may be that each member of a particular
>group[whatever way you classify them] has the same minimal
>hint number. In which case we need to try a grid from a
>different group than this specific 17 is in.

we would have to examine the members of the 5e9-group here.
Reduced by those just differeing by swapping numbers in a cycle.

>I am convinced that we are not going to hit on the 16 randomly
>- although the 17 did eventually emerge after ? random
>generation.

I'm not convinced, but consider it unlikely meanwhile.
Maybe 30% probability ?

>I think your method of filling in 9[you only need 6] of 1
>number and then going on to a second number etc - if I
>understand it right is ambitious but perhaps "below the belt"
>If you have a program which can perform simultaneous analysis,
>with respect to all possible grids [or classes], but
>incrementally gives reducing data on each potential next
>placing - gradually comes up with an answer of only one grid
>which fits - then we could have a unique grid generated from a
>low number of hints.

I had to read this sentence several times, still not sure

>But if there is only one grid which fits
>then it should be provable with logical methods one way or
>another.
>
>Ah
>Not below the belt !


I was trying to generate 18-clue sudokus, 2 clues with each number.
Choose 2 good cells and k bad ones such that a unique
9-set out of the 46656 contains the good ones and no bad one.
Minimize k.
Best I could do was k=12:
Number of solutions: 5184,576,432,288,144,96,48,32,16,12,8,4,2,1.
This is when starting with the good ones and at each step minimizing
the number of compatible sets from the initially 46656
configurations of nonattacking sudoko-leapers.
So 2 good and 12 bad clues are sufficient to allow
us filling in all the 7 other good numbers,. But then we get stuck,
because the above selection of clues is not good to
proceed further - no matter what numbers we assign
to the 12 bad clues.


I hope, I made it clear enough, what I mean.

[gfroyle]

I wondered about doing the search that way, but I was put off by the thought of winding up with quite large exhangeable sets (you can have millions of wrong completions of a 16-clue grid, some of which presumably differ from the target by a large amount).

It is true that there can be millions of wrong combinations, but in some sense we don't care about that - it is only the exchangeable sets that we care about, and (as you observed) we only need to keep those for which no subset is already in the list. This means that large exchangeable sets are usually just chucked out straight away..

In addition, we don't actually need to start with 16-clue grids - we can use ANY grid with multiple solutions to add a few to the mix..

I have done some more extensive experiments (on "strangely familiar") in the following fashion

- construct a few hundred thousand 35-clue subgrids
- complete them in all possible ways and identify the exchangeable sets
- maintain a list of all exchangeable sets subject to the rule that any that are known to be not minimal are thrown out

The interesting thing is that the list of exchangeable sets grows quickly to start with (as I pump in more incorrectly completed grids), but then the rate of growth slows down and after a while the list becomes fairly stable.... AND it is not as large as I feared.

For SF I get the following sort of numbers (focusing on the small exchangeable sets because these give the most power in restricting the size of the hitting set):

2 exchangeable 4-sets
1 5 19 23
36 37 72 73

(as a C programmer, my numbering of the cells is from 0..80 row by row)

14 exchangeable 6-sets
7 8 43 44 79 80
19 20 65 70 73 79
63 67 71 72 76 80
18 19 27 31 46 49
51 52 53 69 70 71
28 33 37 41 50 51
21 23 48 50 75 77
0 6 20 24 36 38
3 4 39 40 75 76
15 16 33 34 78 79
12 13 48 49 57 58
4 5 49 50 67 68
21 22 30 31 66 67
10 13 15 19 22 24

18 x 8-sets, 10 x 9-sets, 69 x 10-sets, 57 x 11-sets, 201 x 12-sets, 160 x 13-sets, 584 x 14-sets, 615 x 15-sets, 1718 x 16-sets, 2592 x 17-sets,..

In this particular experiment the numbers continued to rise until about 13000 x 21-sets, but then decreased again down to a single 39-set... I found less than 100000 sets altogether... if I ran the experiment for longer, I bet that I would not find many more, and indeed may even find fewer (remembering that each additional exchangeable set can potentially reduce the overall size of the list).

So, how many 16-clue hitting sets are there that touch all of these 100000 exchangeable sets? I would bet that there aren't many...

Trouble is, my attempt at writing a hitting set program in about 15 minutes today was not a success and I won't have much time tomorrow to try it.... so I have no feel for whether this number is horrible or pretty much OK. My (naive) feeling is that one might get quite a long way by taking a few hundred, or maybe a few thousand, of the smallest of the sets.

Cheers

gordon

[dukuso]

gordon wrote:
>... I found less than 100000 sets altogether...

sounds promising

>Trouble is, my attempt at writing a hitting set program in
>about 15 minutes today was not a success

the "hitting set" , isn't it just the same as "set-cover" ?
The sets are the 81 collections of supersets of the 81 cells
and they must cover the whole 100000 sets-collection.
Maybe you can get a setcover program somewhere ?

Guenter.

[gfroyle]

the "hitting set" , isn't it just the same as "set-cover" ?

Yep.. they are just dual problems, so a program for one would solve the other.. I had a (very quick) look for implementations for Minimum Set Cover, but found nothing. I may have another look later today..

Cheers

Gordon

[coloin]

To explain my NOT "below the belt" comment.

If we were to get an easy way of classifying sudoku grids. Say we were to imput all the 16 clues given plus all the rest of the logically infered clues from that said 16.

Now if 1 valid grid gets spat out from the system -

Have we got a 16 ?

Yes we have. And we could prove it with a long drawn out guess logic.

I admit there are 2 logistical problems to solve before we can do this
ie
classify all the grids - possible
identify 16 clues - ?

- but essentially thats how B got the number of grids !

[Moschopulus]

Hammerite said "I've now convinced myself that the minimum number of clues for a 4x4 is 4. I have a proof which might not be totally rigorous, but it convinces me. However, I can't be bothered to post it, or at least, not just now, this late at night."

I would like to see your proof of this. I'm sure the minimum number of clues is 4.

Could I suggest that the computational people practice their methods on the 4x4 case. Have you done so already? Surely we should be able to do this case at the very least.

[coloin]

Red Ed published the equivs for B1B2B3 completion - and there are 44.

Based on my last posts - in the maths section - on reflection there isnt a lot of point in generating Bertram's number a different way. But it might be interesting to see what combination of 44s the grid that our 17 is in.

I have been working on a classification system and have some further interesting conclusions.

For B1B2B3
Take in order B1B2B3 [academic]
B1 as before
B2 216*56 " only eight different grids - combinations in column 456**
.......................................................

**
look in Red Ed's column 4 concerning row 2 of box 2 It has 1 in all initial rows

look in Red Ed's column 5

43 x 3 [it is either one number or two which are equivilent]
1 x 2 [this is the boring symetrical 456 123 789 in row 2]

therefore B2 can effectivlyly be either
xxx
12x...x 43 times
3xx
or
xxx
123.....x 1 times
xxx
..................................................................
We can reresent the interesting 43 ways B1B2B3 as
123 4xx xxx
456 13x xxx
789 2xx xxx
Different members will depend on the ways you can fill in B3. [I am not sure if the position of the 2 and the 3 in their rows is relevant][It isnt in terms of affecting box 3] I need to work out the number of possible box3 fillings. I find it impossible to tell what 44 a shute comes from!
............................................................................................

From the gang of 44 - perhaps if we cross a horizontal 42 with a vertical 43 - we might get a set of tight grids.

I will check where our 17 comes from

[dukuso]

Coloin,

are you trying to find all classes modulo

(1) permuting any 3 entries in a minirow or minicolumn
(2) permuting the 9 symbols
(3) permuting the 3 columns in a stack
(4) permuting the 3 stacks
(5) permuting the 3 rows in a band
(6) permuting the 3 bands
(7) transposing


?