The New Sudoku Players' Forum

[angusj]

Here is an interesting collection of 29 17-hint puzzles... what do they have in common?

They all have the same solution?!

[gfroyle]

Here is an interesting collection of 29 17-hint puzzles... what do they have in common?

They all have the same solution?!

Correct... they are all subgrids of the SAME grid...

So this particular grid gives us at least 29 uniquely completable 17-hint puzzles (which is the most for any grid containing 17s that I know of), hence my frustration that none of these can be reduced by just one further clue without losing the uniquely completable property.

But maybe this grid still contains many more 17s and maybe 16s and so on. I just have no way to telling, and the complete search is far too large unless I am missing some clever tricks to dramatically reduce it..

Cheers

Gordon

[Red Ed]

But maybe this grid still contains many more 17s and maybe 16s and so on. I just have no way to telling, and the complete search is far too large unless I am missing some clever tricks to dramatically reduce it..

Can I ask about non-clever tricks? To what extent have you taken your 450 grids and replaced some collection of N clues with some other collection of N-1? I know you've tried removing a single clue and hoping that the result is uniquely solvable. Of course (else you'd have mentioned it!) none is, but some do have quite a low number of solutions, e.g. a 16-clue subgrid with just 12 solutions in one case. I'm currently taking each few-solutions 16-clue subgrid and replacing a clue (naively 16x(81-15)x9 possibilities) in the hope of finding a uniquely solvable puzzle, but to no avail so far. So, back to my question: have you already done this or something similar?

Actually, one other thing I'll mention in passing is the amazing effect that a single clue can have in slashing the number of solutions. I've seen several examples now of 16-clue subgrids with >1000000 solutions which, with the addition of a single clue, suddenly become uniquely solvable. Crikey!

[gfroyle]

Can I ask about non-clever tricks? To what extent have you taken your 450 grids and replaced some collection of N clues with some other collection of N-1?

I have done a large number of non-clever things... basically, for each grid that I find, I attempt to "perturb" it a little and see what kinds of things I find. The perturbations that I have used include

- replacing each empty entry with a legitimate clue (thus increasing the number of clues)
- deleting each clue (thus decreasing the number of clues)
- exchanging any two entries of the grid (unless both are empty)
- altering any clue to a different, but legitimate, value
- more complex, but time-consuming variants of these involving altering or permuting 2 or more entries at the same time; these have not been applied globally as each one can generate a huge number of candidates.

These techniques are how I have managed to create my lists of small-clue puzzles, now up to 2687 x 17s and over 540000 x 18s (all different).

There are quite a few "near misses" that I have found..

Code: Select all

5 . 2  . . .  4 . . 
. . .  7 1 .  . . 3 
. . .  . . .  . . . 

. . .  . . 4  6 . . 
. 7 .  2 . .  . . . 
. 1 .  . . .  . . . 

6 . .  . . 2  . . . 
. . .  . 3 .  . 1 . 
4 . .  . . .  . . .


is interesting, because it has only 16 clues. It CANNOT be uniquely solvable, because it is missing both 8 and 9, and so they can always be exchanged in any final solution.

But, this turns out to be the only problem - the puzzle has exactly TWO solutions...

[gfroyle]

These techniques are how I have managed to create my lists of small-clue puzzles, now up to 2687 x 17s and over 540000 x 18s (all different).

PS This is also the reason that my data cannot be considered statistically representative; the construction techniques will cause the resulting puzzles to be highly correlated, rather than randomly distributed. So we don't want to read anything much into the statistical analyses ..

[coloin]

this 17 grid

639 241 785
284 765 193
517 983 624

123 857 946
796 432 851
458 619 237

342 178 569
861 594 372
975 326 418

Unremarkable apart from:
There is one pair [subsuduku] that I eventually spotted
- the 1/3 in the first and second boxes

Is it possible to have a grid which doesnt have a pair ?

Gfroyle - Considering the number of grids [Bertram] and considering the number of ways you can fill in 16 numbers in each grid [approx 9^9*8^7] there is hope !

[coloin]

the 17

639 241 785 ........... 3&1 paired
284 765 193
517 983 624 ........... 1&3 paired

123 857 946
796 432 851
458 619 237

342 178 569
861 594 372
975 326 418

= when rearranged

123 468 957
456 917 832
789 352 146

842 975 361
731 624 578
695 183 429

264 895 713
518 736 294
397 241 685

the 2nd and 3rd boxes are represented :

156 278 349 189 267 345

now which of the 44 does this belong to ? [help !]

now which of the 275 does this belong to ? [help !]

[Red Ed]

You don't need to limit yourself just to square sub-sudokus. For example this grid ...

Code: Select all

124|567|893
378|294|516
659|831|742
---+---+---
987|123|465
231|456|978
546|789|321
---+---+---
863|972|154
495|618|237
712|345|689

... has the following chain within it, in which the 2s and 1s can be interchanged:

Code: Select all

12.|...|...
...|...|...
...|...|...
---+---+---
...|...|...
2.1|...|...
...|...|...
---+---+---
...|...|...
...|...|...
.12|...|...

This means you have to have a clue in one of those six cells, assuming you want the unique completion of your puzzle to be the grid I listed first.

It's easy to create lots of chains of this type and then somewhat less easy to search for a minimal set of clues that between them touch all of the chains. When you do so, you obtain a lower bound on the minimum number of clues for that grid.

The tightness of the lower bound depends on how many chains you can be bothered to throw into the mix, plus probably some other factors I haven't thought of. With a fairly limited set of chains, for example, you can prove with a few minutes of computer time that the grid above needs at least 10 clues. Of course that's no surprise -- but it's nice to prove something for a change. And it might help select promising grids for further study, possibly even suggesting a good position from which to expand the clue set ...

UPDATE: if I try this on Gordon's "strangely familiar" grid then the lower bound drops to 9. So it's a pretty crummy lower bound, but it may yet prove to be a nice indicator of good grids.

Further thought/question: we're really after general sets of cells that must be incident with at least one clue, not just chains. Example: the first two columns forms such a set. Call the full list of such sets L. Actually we only care about L' = sets in L for which no subset is in L. Any ideas on how to enumerate L' (or a small superset of it) ...?

[gfroyle]

Further thought/question: we're really after general sets of cells that must be incident with at least one clue, not just chains. Example: the first two columns forms such a set. Call the full list of such sets L. Actually we only care about L' = sets in L for which no subset is in L. Any ideas on how to enumerate L' (or a small superset of it) ...?

First throw in every pair of rows/columns in the same block... they are forced to be in your set L.

Then the cells occupied by every pair of colours; obviously we have to touch at least one colour from every pair.

Then for each pair of colours x,y form the "xy-chains" obtained by starting at an arbitrary cell coloured x, and going alternately horizontally and vertically while also alternating between x and y. If such an xy-chain meets every block in an even number of cells (ie 0 or 2) then it is a valid one. Of course each of these chains may be the whole collection of cells coloured x and y, which would represent no further restrictions... But if we could find a largish collection of small chains, then a lower bound would be a distinct possibility.

(Of course, one could also consider walking "horizontal, within block, horizontal, within block" etc to get a variant of a chain. This time the requirement would be that each column must contain an even number of them.)

I wonder what we would get for a lower bound using all those sets?

(Of course, the problem of finding the minimum number of cells mutually touching all the sets is an instance of an NP-complete problem, so may be hardish to solve with a lot of sets to cover.)

Cheers

Gordon

Edit: Realized that the minimum number of cells problem is not the one I thought it was originally, so will have to look up which one it is.

[Red Ed]

I wonder what we would get for a lower bound using all those sets?

I was using all those sets already and getting rather weak bounds.

I was more interested in sets that distinguish between the following alternatives (within a band, for example) :

Code: Select all

362 581 479
914 672 538
857 493 126

... versus ...

Code: Select all

314 682 579
962 571 438
857 493 126

I guess, thinking about it, this would be quite easy to code up. You swap (1,6) in col 2, forcing you to swap (5,6) in col 4 and (1,2) in col 6, which in turn force swaps of (4,5) in col 7 and (2,4) in col 3. This is a closed loop taking up less than a full pair of rows and so generates the following set in L' and allows you to ignore the superset which is (row1,row2).

Code: Select all

in row1: .** *.* *..
in row2: .** *.* *..

Perhaps I'll code this up this evening and see how it behaves.

[gfroyle]

I was more interested in sets that distinguish between the following alternatives (within a band, for example) :

Code: Select all

362 581 479
914 672 538
857 493 126

... versus ...

Code: Select all

314 682 579
962 571 438
857 493 126

I guess, thinking about it, this would be quite easy to code up. You swap (1,6) in col 2, forcing you to swap (5,6) in col 4 and (1,2) in col 6, which in turn force swaps of (4,5) in col 7 and (2,4) in col 3. This is a closed loop taking up less than a full pair of rows and so generates the following set in L' and allows you to ignore the superset which is (row1,row2).

Code: Select all

in row1: .** *.* *..
in row2: .** *.* *..

Very interesting... I think this is really heading towards a workable idea....

What you have actually done here is to select 5 columns such that R1 restricted to those 5 columns is equal to R2 restricted to those 5 columns (at least as a set).

In your example you have

Code: Select all

.62 5.1 4..
.14 6.2 5..


where the two rows both contain {1,2,4,5,6} in those particular positions.

Hence, these particular entries can be swapped in any completion.

But, of course if these 5 columns have this property, then so do the complementary 4 columns.

Code: Select all

3.. .8. .79
9.. .7. .38


So now you have two subsets for the price of one...

Hmm... I await your results (I would do it myself, but no time )

Gordon

[dukuso]

>the 17
>
>639 241 785 ........... 3&1 paired
>284 765 193
>517 983 624 ........... 1&3 paired
>
>123 857 946
>796 432 851
>458 619 237
>
>342 178 569
>861 594 372
>975 326 418
>
>= when rearranged

34 29 38 , 32 34 18

you permute the symbols, such that block one becomes 123,456,789

>123 468 957
>456 917 832
>789 352 146
>
>842 975 361
>731 624 578
>695 183 429
>
>264 895 713
>518 736 294
>397 241 685

34 9 38 , 32 34 18
hmm, the 2nd band changed from 29 to 9 ?
Well, you included some errors !

>the 2nd and 3rd boxes are represented :
>
>156 278 349 189 267 345

I don't understand how you get this

>now which of the 44 does this belong to ? [help !]

OK, I just entered the 2 sudokus in my class-printing program
(which I can send if anyone is interested)

>now which of the 275 does this belong to ? [help !]

what you mean ?
I never heard about anything with "275" in this context.
There are 416 classes for a chute (6^5*9! operations).
It should be possible to write a program to identify
within that 416-class, but I haven't yet done this.



>You don't need to limit yourself just to square sub-sudokus.
>For example this grid ...Code:
>124|567|893
>378|294|516
>659|831|742
>---+---+---
>987|123|465
>231|456|978
>546|789|321
>---+---+---
>863|972|154
>495|618|237
>712|345|689

27 38 27 , 27 38 27

>... has the following chain within it, in which the 2s and 1s
>can be interchanged:Code:
>12.|...|...
>...|...|...
>...|...|...
>---+---+---
>...|...|...
>2.1|...|...
>...|...|...
>---+---+---
>...|...|...
>...|...|...
>.12|...|...
>This means you have to have a clue in one of those six cells,
>assuming you want the unique completion of your puzzle to be
>the grid I listed first.

pick 2 symbols, make the graph whose vertices are the
cells containing these 2 symbols. There is an edge, whenever
two cells are in the same row,column or block.
A chain is any connected component in this bipartite graph.

>It's easy to create lots of chains of this type and then
>somewhat less easy to search for a minimal set of clues that
>between them touch all of the chains. When you do so, you
>obtain a lower bound on the minimum number of clues for that
>grid.

OK, what's the sudokugrid with the largest lower bound
that we can create this way ?

>The tightness of the lower bound depends on how many chains
>you can be bothered to throw into the mix, plus probably some
>other factors I haven't thought of.

the chains should be disjoint, else you can kill two or
more of them with one clue

>With a fairly limited set
>of chains, for example, you can prove with a few minutes of
>computer time that the grid above needs at least 10 clues. Of
>course that's no surprise -- but it's nice to prove something
>for a change. And it might help select promising grids for
>further study, possibly even suggesting a good position from
>which to expand the clue set ...

the statistics of Gordon's 17-puzzles shows that this
is not too promising.

>UPDATE: if I try this on Gordon's "strangely familiar" grid
>then the lower bound drops to 9. So it's a pretty crummy lower
>bound, but it may yet prove to be a nice indicator of good
>grids.

when you pick a number, say 1, search for all from the 46656
arrangements containing all the 1-clues and not containing any other clues.
For some number there should be a unique such arrangement in a sudoku.
Fill in their 9 (equal)numbers as new clues. Continue.
I assume this method would solve most sudokus.
It won't solve a sudoku with e.g. 12 clues, 6 numbers occurring
once and 3 twice.
So a sudoku with 12 clues, no symbol occurs more than twice,
wouldn't be solvable with this method.

For each digit d let S(d) be the subset from the 46656 configurations
containing all occurances of this digit but no other of the clues.
For any pair (d1,d2) ...


>Further thought/question: we're really after general sets of
>cells that must be incident with at least one clue, not just
>chains. Example: the first two columns forms such a set.
>Call the full list of such sets L. Actually we only care about L' =
>sets in L for which no subset is in L. Any ideas on how to
>enumerate L' (or a small superset of it) ...?

[coloin]

>the 2nd and 3rd boxes are represented :
>156 278 349 189 267 345
I don't understand how you get this

This is how Red Ed represented the 2nd and 3rd boxes when outlining the 44. [However he cleverly shuffled/reduced them so that nearly all of the first column in box2 was represented by 124] I didnt get it at first either.

123 478 569
456 139 278
789 256 134

as 124/357/689/125/367/489, the entries in the columns of blocks 2 and 3 written in order. (This way of storing the columns means that Ed finds all possible "duplication" equivalences in the terminology of the paper, not only 2xk or kx2, but any possible higher ones too; this presumably accounts for why Ed has to make just 44 searches, compared with Bertram's 71.) ...

Im not sure what mistake Ive made -
I changed box 1 to
123
456
789 by number substitution [is it even possible to do it by row and column shuffling?]

34 29 38 , 32 34 18 ...

Please could you explain this nomeclature !

As to which class of the 275 transformation / +/- invarients / essentially different grids this sudoku grid is - can this not be applied here ?

Regards and belated comiserations re "Eternity"

[dukuso]

> This is how Red Ed represented the 2nd and 3rd boxes when
> outlining the 44.

I see. He does it by hand, while I need a program to
display it this way:

34 29 38 , 32 34 18 ...

>Please could you explain this nomeclature !

these are the indices of the 6 chunks into the list of the 44.
(sorted,minimal members)
I must have explained it earlier, the whole list is in the ..math-thread
I found it here:
http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&start=255

>As to which class of the 275 transformation / +/- invarients /
>essentially different grids this sudoku grid is - can this not be applied
> here ?

still no idea which class you mean and how you ever get something
with "275" in context with sudoku

[coloin]

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

as well as the encompassing:
http://www.shef.ac.uk/~pm1afj/sudoku/

I still cant follow yours !

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.

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

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. 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 !