60
$\begingroup$

I've seen Sudoku puzzles that can be solved two different ways. Referring to a traditional 9x9 grid:

  1. Is it possible for a Sudoku puzzle to have more than two solutions? If so, what is the maximum number of solutions a single Sudoku puzzle can have?

  2. For any given puzzle, is there a way to find out how many solutions it has (other than brute force)?

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ I imagine it also depends on the number of predefined numbers. A blank Sudoku could obviously have thousands of different solutions. $\endgroup$
    – PriestVallon
    Commented May 14, 2014 at 20:35
  • 1
    $\begingroup$ The only times I've ever seen multiple solutions, there have been an even number of them, as they relied on being able to swap numbers at corners of a rectangle. I'll have to dig some to find the proof that that's the only possible way, though. $\endgroup$
    – ClickRick
    Commented May 14, 2014 at 20:37
  • 13
    $\begingroup$ If the puzzle is well-defined, there should be only one solution. $\endgroup$
    – Kyle Kanos
    Commented May 14, 2014 at 20:38
  • 3
    $\begingroup$ It is an interesting question whether a Sudoku can have exactly 3 solutions, but it is not an interesting question to ask about the maximal number of solutions - just leave the grid empty and count all Sudokus. Also, I think that one should NEVER put three different questions in a single one. $\endgroup$
    – user11235
    Commented May 14, 2014 at 20:52
  • 1
    $\begingroup$ @user11235 I only intended for it to be 2 related questions, but I can see where the misunderstanding occurred; I've edited. I consider the first question to all be the same question. The second is a different question, sure, but it's all the same concept. It would seem silly to ask the two separately (which is how I try to judge whether questions should be broken up or not). I'm basically saying "If it's possible for > 2, what's the max and how do I find out?" I just tried to format it in an easy-to-read way. $\endgroup$
    – WendiKidd
    Commented May 14, 2014 at 21:02

4 Answers 4

Reset to default
44
$\begingroup$

Most Sudoku puzzles published have only one solution. If there is more than one solution, it is probably a mistake. That said, puzzles with incomplete clues can have multiple solutions. In the extreme case, a puzzle with no clues has 6,670,903,752,021,072,936,960 solutions according to Wikipedia.

I don't know if it's possible to have exactly 3 solutions, but boards with 2 and 4 (and more) solutions are easy to find. In general, I think boards with an even number of solutions are easier to create.

Finding the number of solutions is a generalization of Sudoku solving algorithms, and there are Sudoku algorithms that do significantly better than brute forcing. Once the board has been filled out as far as possible, it can be brute forced the rest of the way.

Improve this answer
$\endgroup$
9
  • 7
    $\begingroup$ The comment about odd-and even number solutions is misleading... almost all sudokus have a single (odd number) solution. $\endgroup$
    – rolfl
    Commented May 14, 2014 at 20:42
  • 2
    $\begingroup$ Published Sudoku puzzles traditionally have one solution, but incomplete Sudoku boards can have many solutions. $\endgroup$
    – Kendall Frey
    Commented May 14, 2014 at 20:44
  • 3
    $\begingroup$ @rolfl: I think single solution is the only odd-number solution that is easy to create. That's one point of this answer. $\endgroup$
    – justhalf
    Commented Jul 25, 2014 at 6:13
  • 1
    $\begingroup$ You could fit all those possibilities in the IPv6 address space 51 quadrillion times. $\endgroup$
    – Fred
    Commented Nov 7, 2014 at 18:27
  • 4
    $\begingroup$ I can think of a way of building a Sudoku with solution count a multiple of three, but forcing exactly three seems really challenging. This would make an interesting question in its own right, here or on math.SE. $\endgroup$
    – Steven Stadnicki
    Commented Apr 5, 2015 at 18:09
28
$\begingroup$

I have seen two dissenting opinions on this subject (and in my opinion, the first option is right):

  1. By definition, a Sudoku has only one solution. Anything else is just a grid of numbers. Sometimes, there are errors in a publication, and a starting grid has multiple solutions, but, then the starting grid was not a Sudoku!

  2. From Wikipedia: The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960, or approximately 6.67×1021 (ignoring rotations and other factors, there are many fewer solutions, just 5,472,730,538

Assuming you define a sudoku to have just one possible solution, then the rest of your questions are moot.

If the sudoku is defined to have multiple solutions, then, brute-forcing is one way, but it is also possible to pre-compute all possible solutions for all inputs, and look up the result that way (a rainbow table).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Does wikipedia account for the fact that if you turn a board sideways or flip it, it will resemble other puzzles? $\endgroup$
    – Anon
    Commented Dec 10, 2019 at 5:11
  • $\begingroup$ From the looks of it, the "5,472,730,538" number above accounts for rotations, reflections, and also swapping the numbers around in every possible way (replace 1 with 2 and 2 with 1 everywhere, for example). So a single modern hard drive could actually store the full list of unique Sudoku solutions. $\endgroup$
    – Dave Greene
    Commented Jun 17, 2020 at 18:18
  • 2
    $\begingroup$ People here seem to struggle to agree on definitions like 'guessing' and 'solutions'. The Wikipedia reference is completely irrelevant. 5472730538 is related to permutations of a grid, not the number of solutions a solver may find in a given puzzle. Therefore you do not present two dissenting opinions, you present one opinion, and mistake an entirely different concept for another. $\endgroup$
    – bryc
    Commented Sep 17, 2020 at 17:49
12
$\begingroup$

By definition, all valid Sudoku puzzles should have only one solution. In point of fact, many of the techniques used for solving puzzles depend on there being only one solution. All of the Unique Rectangle techniques for example, only work if there is one, and only one, solution.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is basically a circular argument. $\endgroup$
    – user2617804
    Commented Sep 22, 2021 at 8:48
-4
$\begingroup$

It depends on the difficulty level. If the number of clues is more than 20, most of the time it has only one solution (but no mathematical support is there). However, if the number of clues is less than 20 (for example: 12, 15, 17), multiple solutions may exist.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ This answer provides a grid with 77 digits and 2 solutions. On the other hand, it has been proven that the minimum number of digits that is required for a grid to have a unique solution is 17. $\endgroup$
    – xhienne
    Commented Jul 3, 2018 at 22:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.