Number of Unique Solutions to an Empty Sudoku Puzzle

[greg_schmit]

So, I've been programming lately with sudoku puzzles and how to generate/solve them. I do have one problem that I cannot figure out for the life of me, and that is how many unique sudoku puzzles are there? I don't know if combinations or permutations will hep me, but if anyone knows, that would be interesting. Thanks!

[jemidiah]

I'm pretty sure actually calculating this is difficult, but according to Wikipedia there are 6670903752021072936960 "essentially different" Sudoku grids. This page (http://www.afjarvis.staff.shef.ac.uk/sudoku/bertram.html) is cited as source.

[wy125]

Hi. I wrote a solver once and had the same questions as you did. Well I was more concerned with the problem of determining how many solutions exist for a given puzzle. I never figured it out but I did notice that some of the solutions my solver got were different than some given a puzzle book. So even the puzzles given in books aren't constrained such that they have only one solution.

Your program won't have to check over the space of all possible puzzles. All the puzzles you see on the web and in books, since they've been started, are constrained enough so you only search a fraction of the space. If you actually did want to determine the number of possible sudoku puzzles knowledge of permutations would certainly help.

[NickThissen]

You got different solutions than the puzzlebook? Isn't that weird...? If you solve the puzzle in the normal way eg without guessing and simply working structurally until you filled all the spaces, is it then even possible to get multiple solutions?? I can't see how...

Maybe in the harder puzzles where you have no choice but to guess sometimes, I can see how you would possibly get multiple solutions there... But still... Small chance, no?

[jemidiah]

If you solve a Sudoku in "the normal way" without having to guess you're guaranteed to have found the unique solution. If there were any other solution, it would contradict at least one of the facts you used to keep yourself from guessing.

Yeah I find it odd that a puzzle book would make you guess. Maybe, though. I'd find it a little more likely that there was a subtle mistake in the second solution, but who knows?

[wy125]

Yeah I definitely saw more than one answer in some cases and it was a higher-level puzzle. I agree that it doesn't make sense to put a puzzle in a book that has more than one solution, but I do think that you will encounter them from time to time. I don't think it's done on purpose. That's why I wanted to know how to tell when a puzzle was sufficiently constrained to guarantee only one solution. I don't think it's a trivial problem.

It's been a while since I've worked on it but let me see if I can dig one up that had two solutions or maybe search around to see if anyone else has encountered them also.

[Shaggy Hiker]

I've seen at least one with something like four solutions, but I, too, felt it was a mistake on the part of the publisher, as normally it isn't done. I carefully tested all solutions for accuracy, just to make sure.

[jemidiah]

I figure there's some set of a few operations you can perform to solve any uniquely solvable Sudoku, and I bet there's been a lot of research into that too. At the least advanced elimination methods can be used to solve most of the "difficult" ones out there.

You can brute force it as well, recursively guessing once all other options are exhausted until you either get a contradiction or finish the puzzle.

The recursive method would be incredibly simple, actually, something like this:


'SolveSudoku prints every possible solution to the given Sudoku if it is solvable. If it is unsolvable, function does nothing.
function SolveSudoku(ByVal Sudoku)
SolveButDontGuess(Sudoku)

If Complete(Sudoku) Then Print(Sudoku) 'Base case 1
If Contradiction(Sudoku) Then Exit Function 'Base case 2

If Incomplete(Sudoku) Then 'Recusive case
Guesses = GetGuesses(Sudoku)
For Each Guess in Guesses
MakeOneGuess(Sudoku, Guess)
SolveSudoku(Sudoku)
UndoOneGuess(Sudoku, Guess)
End If
End If
end


This sorta makes me want to write a Sudoku solver to see how inefficient this method is. But not enough to actually write it :). Writing a good SolveButDontGuess function is really the guts of the problem, the rest is all pretty basic. Even GetGuesses is simple enough if your SolveButDontGuess function does some sort of elimination routine that gives a list of valid number placements.

[AsmIscool]

Here is an algorithm (http://www.instructables.com/id/Solve-Sudoku-Without-even-thinking!/)

[Milk]

Check out Andrew Stuart's site (http://www.scanraid.com/sudoku.htm), he has got together a logic solver (no brute force) it uses 36 different algorithms. Merri started a logic solver collaboration project (http://www.vbforums.com/showthread.php?t=475089&highlight=sudoku) a while back. It sort of died a death but it might be worth a look.

There defiantly are sudokus out there with several solutions, badly written puzzles if you ask me.

Killer (http://www.killersudokuonline.com/) is my bag now :D

[Junbo]

I checked this thread because I solved a difficult sudoku puzzle (from the daily newspaper...Difficulty Level *****) and the solution was different from the one they published in the paper the next day! I was surprised because I thought each puzzle had a unique solution. The other odd thing about this particular puzzle....when filling out the last four open squares, which were in different quadrants that were associated vertically, the numbers could have been interchanged and still solved the puzzle. In other words '6' and '1' were the last two numbers to enter in both the upper left and lower left quadrants, and could have been interchanged so that as long as you alternated vertically it solved the puzzle either way.

The other thing was that my solution was RADICALLY different than the one published the next day. There were 23 "given" numbers that were obviously the same but over half of the other 58 numbers were in different locations in my solution vs. the published solution.

[jemidiah]

Most published Sudoku's should only have one solution (any more and it would be unsolvable without a guess or an error, which is a bad thing in either case). If you think about a very empty Sudoko, say one with only 2 numbers given, there are loads of valid solutions. As you add more given numbers, the number of solutions dwindles drastically and eventually you're left with a unique solution.

I'd guess that they check almost all published Sudokus with a computer solving algorithm (not that tough to write bad ones) but I suppose bugs and oversights might yield the odd, non-unique solution Sudoku. But, it seems to me that it's more likely there's a subtle error, maybe with only two instances of doubling, that would generate a different and incorrect solution. But I dunno :)

[NickThissen]

I can imagine a situation where there are two possible solutions but you wouldn't have to guess: the situation Junbo described.

Suppose you have four empty fields left, two in the top-left corner and two in the bottom-left corner (right above each other). Suppose then that in each quadrant (top-left and bottom-left) you only need a 6 and 1. Then you could choose from two positions where you place the 1 and the other three numbers follow... Well I guess this could technically be called guessing since you don't derive the 1 from the current puzzle, but if you know beforehand that it is going to work out it's not really guessing is it?

[Merri]

This sorta makes me want to write a Sudoku solver to see how inefficient this method is. But not enough to actually write it :). Writing a good SolveButDontGuess function is really the guts of the problem, the rest is all pretty basic. Even GetGuesses is simple enough if your SolveButDontGuess function does some sort of elimination routine that gives a list of valid number placements.
Then take a look at my sudoku solver contest entry (http://www.vbforums.com/showthread.php?t=356827) from three years ago, if you still happen to use classic VB. It is still the fastest VB6 sudoku solving code that I know of. It uses very simple solver logic and once that is done it'll jump into brute force backtracking.


Just as an interesting note: I still haven't solved a single sudoku by hand to this day.

[jemidiah]

I'd define a "guess" as arbitrarily choosing one thing from several choices. So yeah, I'd say technically that situation does yield a "guess" but I see your point that it's not an uninformed guess.

Wow, each Sudoku was solved in under a millisecond with Merri's solver, that's really cool.