A Sudoku puzzle

[lionelhill]

This isn't so much a "puzzle for programmers" as a question (since I don't know the answer):

How many valid sudoku puzzles are there? By valid, I mean that the puzzle isn't completed (at least one square is blank), that it can be completed, and that there is only one solution. By sudoku puzzle I mean the "traditional" variety: 9*9 grid divided into 9 3*3 blocks, with the digits 1-9 arranged without repetition in each row, block and column. I count all puzzles as "different" even if they are trivial variations on one-another (e.g. rotations, reflections) simply because it's easier to count them all as different than to define "trivial variation"!

As a variant on the above (and a more realistically useful number, since a puzzle with only one number missing is hardly a puzzle): How many unique, valid sudoku puzzles are there that are soluble, but only just, in the sense that they would not be soluble if any single number were removed?

If anyone wants to know the background to this question, it's this: quite a few years ago, I wrote a random sudoku-setting program. But puzzles published in newspapers are, of course, copyright. So the problem is this: what is the probability that my program will, at some point, reproduce a copyright puzzle from a newspaper? And independently, what is the probability that it is capable of producing a particular puzzle? I know the number of states possible in the random number generator behind my program, and suspect it to be much less than the total number of puzzles (I used a very cheap-and-cheerful generator from a 16-bit language, before people got excited by encryption and statistically-valid random numbers suitable for Monte Carlo techniques etc.). Of course there's a legal question too, of whether it should be possible to copyright a sudoku puzzle. If it was created by a computer, then copyrighting the puzzle is no better than copyrighting the number "6" because you generated it with a dice. And if it was created by hand, how can you prove it? Unlike crosswords, it's quite difficult to differentiate machine and hand products when it comes to sudokus.

 

[karluk]

I find these questions intriguing, but a quick internet search suggests that they have also been estensively researched by others already and would probably require a computer search to obtain precise results. I'm not sure if that encourages or discourages me from pursuing the subject.

 

[strongm]

>what is the probability that my program will, at some point, reproduce a copyright puzzle from a newspaper

Years ago, the very early 80s, (and possibly apocryphally) someone submitted a design to the patent office for software that would (in theory) generate all the possible permutations of 64K of 8-bit memory (at a time when most PCs typically had about 8-16K RAM) . As a result they wanted to claim copyright on all possible programs (that would fit in that memory space) ... they failed.

 

[Olaf Doschke]

See thread1551-1199656
and see

http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

That's a known number in the magnitude of 10^21.

Besides that large number, your more specific requirement does not reduce it, it surely only highers it, because starting from any of these solutions you'll need to remove digits to get at the point no two different solutions will be able, and there are surely very many ways to reduce a solution to a starting set.

On the other side, take another sample of the number of combinations you can do, if you combine 4 different shoes, trousers, pullovers and hats, you get 4^4 = 256, but I think after you saw about 8 random combinations further ones will look familiar already. That's also how the psychology of lottery numbers works. The results are looking familiar so it seems easy to get 3 or more right, but 6 out of 49 have a very very low probability, and here we just talk of millions, not something in the magnitude 10^21.

Bye, Olaf.

 

[Olaf Doschke]

Rereading wikipedia, the number of really distinct solutions is much lower, but still high enough: 5,472,730,538

There are many symmetries to consider, also you can of course permutate all 9 digits and also have a similar solution if you take one and replace all 9s with 1s and all 1s with 9s, etc.

I think there are still very many sudokus you can solve in very similar ways that seem familiar, actually sudokus got quite boring after a few of them, to me. Unless you don't copy over from a sudoku puzzl only riddle mag, it should never be coonsidered a copyright infringemant, if you have computed the same sudoku. If you do a generator, that results in a sudoku, once you enter a starting number for a pseudo random number generator, and always the same sudoku for the same seed number. Once you log these seed numbers with your puzzle, in case of the case you could show your generator has generated this puzzle. I'd say that is a proof, proof enough, because it would certainly be quite impossible to do the inverse and find the seed number needed for your sudoku generator, to generate the same sudoku as someone else.

Besides having such a generator shows you don't have much need to copy over some other mags sudoku.

Bye, Olaf.

 

[kwbMitel]

1- the total number of possible complete solutions is huge
2- the total number of puzzles that can be generated from each complete solution is also huge
3- the likelihood of a specific puzzle matching another random puzzle is significantly larger than 2 random puzzles matching

For these reasons and others pointed out by Olaf, I don't think you have much to worry about

**********************************************
What's most important is that you realise ... There is no spoon.

 

[lionelhill]

strongm, thanks for that snippet!

Everyone, sorry, I don't think I made myself clear enough. I'm not asking how many valid completed Sudoku grids there are, I'm asking how many valid puzzles (incompleted grids with a unique solution) exist.

My sub-question was how many puzzles there are with, in Wikipedia terms, the minimum number of givens (i.e. you cannot solve the puzzle uniquely if any single digit is removed from the starting position, but you can solve the puzzle uniquely without the addition of any more clues).

But looking at the horrendous effort needed to establish just the number of solutions, I'm convinced my questions are unfair! Thanks for pointing me at the Wikipedia page; it's a jolly interesting read.