The New Sudoku Players' Forum

[angusj]

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.

That's exactly right.

That's all you need, but notice other things with colors in this puzzle ...
r5c1 and r5c8 also form a conjugate pair, so both r5c8 and r9c8 must be the same color. Since they share the same column that color must be the 'false' color.

Finally, like most great ideas, they invariably come from someone else
Anyhow, it was Andrew McKernan (in the Sudoku Programmers forum) who got me started on colors.

[gfroyle]

But I feel I must make the point that it is only whether a "starting grid" has a unique solution that is of interest.*
* I suppose that I do speak only for myself here, however.

I agree with this point - mathematically speaking, the natural question is simply what is the smallest number of clues in a uniquely completable puzzle.

The question "what is the smallest number of clues in a uniquely completable puzzle solvable by techniques A,B and C" is clearly more specific (and hence less natural) and to a mathematician would not even be a valid question unless there was agreement on exactly how A, B and C were defined.

To me, the borderline between so-called trial-and-error and maintaining a short mental list of selections that are impossible because they subsequently cause a blockage is not clear anyway.

Cheers

Gordon

[Animator]

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.

That's exactly right.

Not 'exactly'... r9c2 should be r9c3.

For those that are having trouble seeing it:

If r5c1 is 9, then there is only one place for the number 9 in box 7. This means that r5c1 = r9c3. If it's isn't then both aren't, since then r8c1 has to be the number 9 to statify column 1, and therefor r9c3 can't be the number 9.

The same goes for r6c2 and r8c1. If r6c2 is number 9 then r8c1 has to be the number 9 (again, column 1). If it's the number 9 then r5c1 has to be the number 9, which means r8c1 can't be the number 9.

So far for the verbose explenation:

r5c1 = r9c3
r6c2 = r8c1
r8c1 = r9c8
r9c3 = r8c9

Now take a look at r5c8:

r5c8 = r6c2
r5c8 = r8c1 (We know that r6c2 has the same value as r8c1. So we replace it in the equation.)
r5c8 = r9c8 (r8c1 = r9c8). This is only true when both have another number then 9. If r5c8 or r9c8 is 9 then both of them have to be 9, which is impossible.

[coloin]

The minimum number of hints to produce a unique and valid grid.

Unique = there can be only one
Valid = valid

It is ok to guess - as long as you can show that all other guesses result in invalid grids.

I think there must be a 16 out there !

[Hammerite]

What do you mean by "valid" though? It's not clear to me. If you mean that the unique solution follows the rules of Su Doku (i.e. precisely one of each of nine symbols in every row, column and 3x3 box) then yes, I agree.

ps. thank you gfroyle

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

Ha, ha! When I read your post yesterday I thought, "What is this guy talking about?" However, with today's set of fresh eyes, when I reread my own post, I now ponder, "What was I thinking of?" I think I came close to making your point about starting grids having unique solutions, but I passed by it while headed in a different direction, blinded momentarily by the bright glare of trial-and-error.

Instead of choosing to focus on trial-and-error, I should have highlighted that none of the 19 possible grids -- which arise from removing one clue from the 19-cell grid -- have unique solutions. Therefore it stands to reason that removing a clue from any given starting grid may result in the new starting grid having multiple solutions. Thus not every starting grid can be reduced to 17.

I hope this makes as much sense to me tomorrow as it does today.

[su bloko]

Instead of choosing to focus on trial-and-error, I should have highlighted that none of the 19 possible grids -- which arise from removing one clue from the 19-cell grid -- have unique solutions. Therefore it stands to reason that removing a clue from any given starting grid may result in the new starting grid having multiple solutions. Thus not every starting grid can be reduced to 17.

I am not sure this follows. If you select 17 numbers from the completed grid (that is 17 numbers not restricted to the 19 original clues) it may or may not be possible to produce a problem that has a unique solution. It remains to be seen whether every complete grid has a 17 clue position that provides a unique solution. I am not aware of an an example that has been proven to preclude this possibility.

[scrose]

I am not sure this follows. If you select 17 numbers from the completed grid it may or may not be possible to produce a problem that has a unique solution.

Ah, but that is not what I said. I reasoned that not every starting grid (i.e. a 9x9 grid with less than 81 cells filled in) can be reduced to a 17-clue grid with a unique solution. This is subtly different from saying not every complete grid (i.e. a 9x9 grid with all 81 cells filled in) can be reduced to 17-clue grid with a unique solution.

So, as you stated, the question that remains is whether every valid (i.e. adheres to number placement rules) complete/solution grid (i.e. a 9x9 grid with all 81 cells filled in) can be reduced to a 17-clue grid with a unique solution (one that may or may not require trial-and-error).

[gfroyle]

Here is a question related to the minimum Sudoku problem..

Can you find a uniquely completable starting grid with 18 clues, exactly two of each number?

(As usual, all I require is there is only one legal completion, regardless of how it may be found.)

Cheers

Gordon

[Hammerite]

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.

[coloin]

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

Any news on this.

I agree that a valid 81 grid can be reduced to a minimum number which still gives this grid - taking away one more hint gives more than one solution. The minimum number depends on which numbers you chose to remove - of course. But can some grids be reduced to 17 and others not.

When we see what group [see Red Ed and Frazer's posts] these 17ers are in we might have a chance to understand - and maybe get the 16 !

Regards, keep working on it.

[gfroyle]

Any news on this.

The work continues... I started looking for 17-hint uniquely completable grids with the expectation that if there were large numbers of those, then there would probably be a 16 out there somewhere. Conversely, if there were very few 17s, then that might be the cutoff point.

In order to construct 17s, I also collect a pile of 18s as a sort of by-product.

By now, I have collected 1075 different (ie genuinely different, not just relabellings or rearrangements) uniquely completable 17-hint grids, and about 78000 uniquely completable 18-hint grids.

I have not bunged these on my webpages yet because I need to rewrite my PHP code so that it doesn't attempt to display all 1075 of them at once when someone visits...

I have kept some statistics on how many occurrences of each number there are in these grids. For example

79 x (0^1, 1^2, 2^3, 3^3)

means that there are 79 grids where one number is missing (0^1), two numbers occur once each (1^2), 3 numbers appear two times each (2^3) and 3 numbers occur three times each.

The stats so far are

79 x (0^1, 1^2, 2^3, 3^3)
301 x (0^1, 1^1, 2^5, 3^2)
57 x (0^1, 2^7, 3^1)
1 x (1^5, 3^4)
28 x (1^4, 2^2, 3^3)
308 x (1^3, 2^3, 3^3)
301 x (1^2, 2^6, 3^2)


Things that are "different" from all the others are often interesting mathematically, so here is the single example of type (1^5, 3^4) - notice that there is one each of {1,3,4,8,9} and three each of {2,5,6,7}

Code: Select all

+ + +  + 6 +  + 3 +
+ + +  8 + +  2 + +
2 + +  5 + +  + + +

+ + +  2 9 +  5 + +
+ 7 6  + + +  + + +
+ + +  + + +  1 + +

+ + +  + + 7  + 6 4
5 + +  + + +  + + +
+ + +  + + +  + 7 +


How does this rate as an actual puzzle? (I have not yet had time to code up all the "rules" and figure out how to assign a rating to a puzzle...). Probably it cannot be done just using the rules without some backtracking...

[angusj]

I started looking for 17-hint uniquely completable grids

Just out of curiosity, do you know if any of these are symmetrical?

How does this rate as an actual puzzle?

I would rate it easy (ie nothing harder than a hidden single).

[gfroyle]

I started looking for 17-hint uniquely completable grids

Just out of curiosity, do you know if any of these are symmetrical?

Yes... and no..

It depends on whether you want symmetry or *NICE* symmetry.

As far as a mathematician is concerned a pattern has NO symmetry if and only if NONE of the group elements (the row permutations, column permutations and transpositions mentioned in other posts) preserve the pattern. (Of course, one of the elements is "the identity" which leaves everything fixed, but we can ignore that as an interesting symmetry!) But there are some patterns that DO have non-identity group elements that preserve them....

Code: Select all

+ + +  + 7 6  + + +
+ 4 +  + + +  + 9 +
+ 3 +  + + +  + 5 +

+ + +  + + +  7 + 1
+ + 9  2 + +  + + +
8 + +  + + +  6 + +

+ + 5  4 + +  + 3 +
6 + +  + + +  + + +
+ + +  + + +  8 + +

This pattern has SOME symmetry - it is preserved under the two permutations R2 <-> R3 and C4 <-> C5. So in fact, it has a symmetry group of order 4.

But of course to most people "symmetric" means that it should have a NICE symmetry, like a rotation or maybe a reflection, or maybe both... In general, I think that a group element has to have very few fixed points to qualify as a "nice" symmetry.

In this case we are (currently) out of luck.. the automorphisms of the patterns found so far are all just these sort of crappy little row-exchanges...



Now, just for MY curiousity - if I send you the file of 1000+ puzzles, can your program quickly determine which of them are interesting games-wise? (Of course, I should just update my own program, but I am kinda addicted to finding this elusive 16-hint example at the moment)

It is a little surprising (to me) that the other 17-hint example was so easy - I guess it really is not very highly dependent on the number of clues.

Cheers

Gordon

[Nick70]

308 x (1^3, 2^3, 3^3)
301 x (1^2, 2^6, 3^2)

Those two would imply 18 and 20 clues respectively. The last one 10 numbers even instead of 9.

BTW the notation is really confusing from a mathematical point of view, something like this would be better:

79 x (1x0, 2x1, 3x2, 3x3)