A Sudoku puzzle
A Sudoku puzzle
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.