The New Sudoku Players' Forum

[Hammerite]

Hello all,

First post. Woo!

First off I would like to apologise if the points I raise in this topic are frequently discussed ones that the board collectively is tired of. I know how annoying forum users generally find such threads by newbies. I have not read through all the posts on the forum so far, not even their titles. Please ignore the topic and don't flame if you find the topic irksome!

What I was interested in is the matter of the minimum number of clues needed in a (incomplete standard 9x9) Su Doku grid for that grid to have a unique solution. That is, the natural number k such that there exists at least one incomplete (standard 9x9) Su Doku grid with k clues that has a unique solution, and there exist no incomplete (standard 9x9) Su Doku grids with fewer than k clues that have a unique solution.

Here is a grid I found on another board (actually it was a blog, I'll get the URL if anyone is interested) which has 17 clues and a unique solution.

??6 9?? ?7?
??? ?1? ??2
8?? ??? ???

?2? ??? ??4
??? ??? ??1
??5 ??6 ???

??? ??? ?6?
??? ??2 ?5?
?1? ?43 ???

(I wasn't able to solve this puzzle without using a proof by contradiction at this stage...

146 928 375
5?? 617 842
872 435 916

721 359 684
?68 274 5X1
4?5 186 ?Y?

25? 891 46?
?84 762 15?
61? 543 ??8

where X and Y mean the same as ?

Note that precisely one of X and Y must be 3. Assuming that Y is 3 eventually leaves us unable to place a 9 in the bottom right 3x3 box. It follows that X is 3 and proceeding from this leads to a unique solution.)

[scrose]

Welcome to the forum! I think we're quite a polite bunch; newbies are certainly not turned away at the door.

From what I've read, so far 17 is the minimum for a non-symmetrical grid and 18 is the minimum for a symmetrical grid. Here is another 17-cell grid with a unique solution, but this one can be solved without trial-and-error. It came from this site.

Code: Select all

 . 9 8 | . . . | . . .
 . . . | . 7 . | . . .
 . . . | . 1 5 | . . .
-------+-------+-------
 1 . . | . . . | . . .
 . . . | 2 . . | . . 9
 . . . | 9 . 6 | . 8 2
-------+-------+-------
 . . . | . . . | . 3 .
 5 . 1 | . . . | . . .
 . . . | 4 . . | . 2 .

[Hammerite]

Thankyou scrose! And thanks also for the extra example...

Those examples show that 17 is an upper bound for k. I wonder, though, how much thought has been put into finding a lower bound... I will read some of the posts on this forum at some point.

I went for a stroll to Tesco and as I came back I had some thoughts... I considered what would happen if there were 7 clues in the grid. Clearly if there are 7 clues in the grid, then at most 7 of the 9 symbols will appear in the initial grid. Then at least 2 of the symbols do not appear in the initial grid. Clearly in any solution of the grid, the grid produced by the transposition of the 2 non-appearing symbols is also a solution. However, can it really be called a different solution? The two symbols are, by virtue of not being in the grid, invented by us, the solvers, and so if all that changes is that we transpose them, while keeping their respective locations the same, we may decide that the two solutions are in fact equivalent. If, however, having fixed one of each of those two symbols in one of the 18 cells those two symbols occupy overall, we can swap some or all of the symbols in the remaining 16 such cells and produce another solution, then the solution we had certainly isn't unique. If we can prove that we can do this in at least one way for any solution we come up with to any Su Doku puzzle with 7 clues, then we have shown that any Su Doku puzzle with 7 clues has either no solutions, or more than one solution, in which case a lower bound for k is 8. It would follow that k is 8, 9, 10, 11, 12, 13, 14, 15, 16 or 17. However, I would imagine that k is further towards the right of this list than the left.

[Hammerite]

An upper bound for k for a 4x4 Su Doku is 4:

Code: Select all

1 . | . .      1 4 | 3 2
. 2 | . .      3 2 | 1 4
--------  =>  ---------
. 3 | . .      4 3 | 2 1
. . | 4 .      2 1 | 4 3

[angusj]

Code: Select all

??6 9?? ?7?
??? ?1? ??2
8?? ??? ???

?2? ??? ??4
??? ??? ??1
??5 ??6 ???

??? ??? ?6?
??? ??2 ?5?
?1? ?43 ???

(I wasn't able to solve this puzzle without using a proof by contradiction at this stage...

It can be solved using colors on candidate 9 ( see http://www.angusj.com/sudoku/hints.php#colors ) once other logical steps have been exhausted.

[gfroyle]

I am collecting 17-hint examples that can be uniquely completed.

Please see

http://www.csse.uwa.edu.au/~gordon/sudokumin.php

for details of the progress so far.

This is only in early draft stage, but there seems to be enough recurring interest in this theme to open it up even if incomplete.

I do intend to include full details of how I (a) determine equivalence, and (b) give full credit to original discoverers, but the day job takes me away from this task sometimes


There is a variety of interesting behaviour, including two 17-hint examples that differ in only one position (yet are genuinely different!).

Comments and queries welcome...

Gordon

[angusj]

I am collecting 17-hint examples that can be uniquely completed.

Good stuff. I particularly liked the first one as it was the most challenging.

[scrose]

It can be solved using colors on candidate 9 once other logical steps have been exhausted.

Let me see if I understand your colouring technique as it applies to this puzzle. Please verify if I have this right.

Looking only at the candidate 9's, r5c1 and r8c1 form a conjugate pair in column 1, r8c1 and r9c2 form a conjugate pair in block 7, and r9c2 and r9c8 form a conjugate pair in row 9. So the candidate 9 at r5c8 can be eliminated.

[Hammerite]

Hey gfroyle,

Transposing the matrix (that is, exchanging rows and columns).
Permuting (ie. rearranging) rows within a single block.
Permuting (ie. rearranging) columns within a single block.
Permuting the blocks row-wise.
Permuting the blocks column-wise.

That's a nice page there, I think I shall try some of them in due course...

I just thought that to the list of operations should be added permutations on the nine symbols. That is, if a permutation on the nine symbols (on its own or in combination with the other operations) transforms one of the puzzles into another one, then the two puzzles should be regarded as mathematically equivalent.

e.g.

Code: Select all

 + 3 +     + + +     9 + +                    + 4 +     + + +     9 + +
 6 + +     4 + +     + + +                    6 + +     3 + +     + + +
 + + +     + + +     7 + +                    + + +     + + +     7 + +
 
 + 7 +     2 9 +     + + +                    + 7 +     2 9 +     + + +
 + + +     3 + +     + 6 +  is equivalent to  + + +     4 + +     + 6 +
 + + +     + + +     + 4 +                    + + +     + + +     + 3 +
 
 4 + +     + + 5     + 8 +                    3 + +     + + 5     + 8 +
 + + +     + 7 +     3 + +                    + + +     + 7 +     4 + +
 + + 1     + + +     + + +                    + + 1     + + +     + + +


because the 3s and 4s have been transposed.

[Hammerite]

I mean, perhaps you regard that as an obvious point, but I don't know whether you might want to explicitly point it out.

[coloin]

There are two unanswered Qs in Sudoku
1 Number of valid grids
2 Minimum number of hints for a unique grid

1 Is solved by number crunching on a pc
2. 17 at present [- last month it was 18]

What is special about the sudokus that can be expressed as 17
Can every Suduku be reduced to 17 ? If not - why not ?


Note on transformations
Some manouveres such as a reflection and a couple of row/column swops can give rise to the same effect as a rotation. ["double-counting"]

[scrose]

Can every Suduku be reduced to 17 ? If not - why not ?

Not every starting grid can be reduced to 17. The removal of one or more clues can result in trial-and-error being needed to solve the reduced grid. Take the following 19-cell grid as an example (source). You cannot remove a single clue without resulting in an 18-cell grid that requires trial-and-error to solve it. In fact, all of the resulting 18-cell grids will have multiple solutions, from as few as 26 (if r8c5 is removed) up to as many as 14526 (if r8c4 is removed)!

Code: Select all

 . . . | . . 9 | . . .
 . . . | . 1 4 | 7 . .
 . . 2 | . . . | . . .
-------+-------+-------
 7 . . | . . . | . 8 6
 5 . . | . 3 . | . . 2
 9 4 . | . . . | . . 1
-------+-------+-------
 . . . | . . . | 4 . .
 . . 6 | 2 5 . | . . .
 . . . | 8 . . | . . .

So a more precise question would be can every valid solution grid be reduced to 17? My gut feeling is that the answer is no. I suspect that there is a limited number of arrangements of solution grids that will permit a starting grid to be reduced to 17 clues.

[gfroyle]

Hey gfroyle,

I just thought that to the list of operations should be added permutations on the nine symbols. That is, if a permutation on the nine symbols (on its

Yes of course it should... in fact, it is already implemented that way, but I just forgot to write it down in the list!

Thanks for pointing this out..

Gordon

[Hammerite]

Thankyou scrose.

But I feel I must make the point that it is only whether a "starting grid" has a unique solution that is of interest.* The method needed to solve is irrelevant, indeed to bar certain methods should (I imagine) add greatly to the complexity of the mathematical solution to the problem of determining the value of k. As well as introducing a complication that is of no interest.*

* I suppose that I do speak only for myself here, however.

[gfroyle]

So a more precise question would be can every valid solution grid be reduced to 17? My gut feeling is that the answer is no. I suspect that there is a limited number of arrangements of solution grids that will permit a starting grid to be reduced to 17 clues.

I am absolutely certain that not every valid solution has a 17-hint "starter", though of course PROVING this might be more difficult....

This does raise an interesting question however - given a valid completed grid, what is the smallest uniquely completable sub-grid? And how many of them are there? These are computationally very difficult questions.

One thing on my page of 17-hint examples that is not apparent (and in fact, you need computer to confirm) is that THREE of those examples actually complete to EQUIVALENT final grids. In other words, this particular grid has at least three distinct 17-cell sub-grids that are uniquely completable..

More later

Gordon