60

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)?

bobble
  • 10,245
  • 4
  • 32
  • 80
WendiKidd
  • 2,423
  • 2
  • 20
  • 26
  • 4
    I imagine it also depends on the number of predefined numbers. A blank Sudoku could obviously have thousands of different solutions. – PriestVallon May 14 '14 at 20:35
  • 1
    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. – ClickRick May 14 '14 at 20:37
  • 12
    If the puzzle is well-defined, there should be only one solution. – Kyle Kanos May 14 '14 at 20:38
  • 3
    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. – user11235 May 14 '14 at 20:52
  • 1
    @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. – WendiKidd May 14 '14 at 21:02
  • 1
    For some reason I'm thinking that as long as a Sudoku has multiple solutions, it should be an even number, because usually you end up with pointing pairs, and if a puzzle can go into more than one direction it's probably going to be because of those. I can't explain that mathematically, but it seems right. – Kingrames Aug 21 '15 at 21:25
  • 1
    There can be several answers. Whenever there are the same pair of numbers (i.e.. 2 & 6) in one column of one square, and those two numbers are also in another square but a different column, as well as having two possible numbers line up in the same two rows, then the two numbers will be interchangeable without affecting the remainder of the puzzle. 25% of the puzzles I have played on line have had 2 or more possible answers. Whenever you find the above condition, just randomly place either one of the pair and then place the remaining numbers accordingly. –  Sep 24 '15 at 17:15

4 Answers4

44

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.

Kendall Frey
  • 3,383
  • 23
  • 27
  • 7
    The comment about odd-and even number solutions is misleading... almost all sudokus have a single (odd number) solution. – rolfl May 14 '14 at 20:42
  • 2
    Published Sudoku puzzles traditionally have one solution, but incomplete Sudoku boards can have many solutions. – Kendall Frey May 14 '14 at 20:44
  • 3
    @rolfl: I think single solution is the only odd-number solution that is easy to create. That's one point of this answer. – justhalf Jul 25 '14 at 06:13
  • 1
    You could fit all those possibilities in the IPv6 address space 51 quadrillion times. – Fred Nov 07 '14 at 18:27
  • 4
    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. – Steven Stadnicki Apr 05 '15 at 18:09
  • Whoever came up with 6,670,903,752,021,072,936,960 did a good job narrowing down from $ python3 -c "from math import factorial; print(factorial(9*9))" 5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000 – Galen Apr 26 '20 at 20:16
  • @Galen Your comment made me decide to look it up. Wikipedia > https://oeis.org/A107739 > http://www.afjarvis.staff.shef.ac.uk/sudoku/bertram.html > "This page contains details of the enumeration of Sudoku grids. ... The algorithm is a brute force count". Almost disappointing. – DimeCadmium May 25 '20 at 18:24
  • 1
    It's actually not at all difficult to make a Sudoku-ish puzzle with three solutions. I don't know Sudoku terminology, but someone who probably does know the lingo called it "two pseudo X-wings sharing a cell". – Dave Greene Jun 17 '20 at 18:11
  • There are puzzles with p solutions, where p is any prime below 821. The idea I have is that one can probably combine primes, to produce puzzles with non-prime number of solutions - see https://math.stackexchange.com/questions/823966/smallest-integer-k-so-that-no-sudoku-grid-has-exactly-k-solutions – Per Alexandersson Sep 04 '21 at 12:04
28

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).

Community
  • 1
rolfl
  • 389
  • 2
  • 10
  • Does wikipedia account for the fact that if you turn a board sideways or flip it, it will resemble other puzzles? – Anon Dec 10 '19 at 05:11
  • 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. – Dave Greene Jun 17 '20 at 18:18
  • 2
    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. – bryc Sep 17 '20 at 17:49
12

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.

Donald.McLean
  • 361
  • 1
  • 10
-3

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.

Bailey M
  • 16,973
  • 2
  • 69
  • 119
haradhan chel
  • 9
  • 1
  • 3
    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. – xhienne Jul 03 '18 at 22:24