Results 1 to 15 of 15

Thread: Number of Unique Solutions to an Empty Sudoku Puzzle

  1. #1

    Thread Starter
    Member
    Join Date
    Feb 2005
    Posts
    36

    Number of Unique Solutions to an Empty Sudoku Puzzle

    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!

  2. #2
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    I'm pretty sure actually calculating this is difficult, but according to Wikipedia there are 6670903752021072936960 "essentially different" Sudoku grids. This page is cited as source.
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  3. #3
    Hyperactive Member
    Join Date
    Mar 2002
    Location
    Boston, MA
    Posts
    391

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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.

  4. #4
    PowerPoster
    Join Date
    Apr 2007
    Location
    The Netherlands
    Posts
    5,070

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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?

  5. #5
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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?
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  6. #6
    Hyperactive Member
    Join Date
    Mar 2002
    Location
    Boston, MA
    Posts
    391

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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.

  7. #7
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,989

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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.
    My usual boring signature: Nothing

  8. #8
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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:

    Code:
    '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.
    Last edited by jemidiah; Aug 2nd, 2008 at 02:54 AM.
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  9. #9
    Hyperactive Member
    Join Date
    Jun 2007
    Posts
    280

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    Here is an algorithm
    Slower than a crippled Vista
    More buggy than a fresh XP install
    Look! Down the road, some 50 miles behind the drunken snail.
    It's Ubuntu!

  10. #10
    Cumbrian Milk's Avatar
    Join Date
    Jan 2007
    Location
    0xDEADBEEF
    Posts
    2,448

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    Check out Andrew Stuart's site, he has got together a logic solver (no brute force) it uses 36 different algorithms. Merri started a logic solver collaboration project 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 is my bag now

  11. #11
    New Member
    Join Date
    Sep 2008
    Posts
    1

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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.

  12. #12
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  13. #13
    PowerPoster
    Join Date
    Apr 2007
    Location
    The Netherlands
    Posts
    5,070

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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?

  14. #14
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    Quote Originally Posted by jemidiah
    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 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.

  15. #15
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Number of Unique Solutions to an Empty Sudoku Puzzle

    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.
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width