# Are \*all\* Sudoku configurations solvable?
**URL:** https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444
**Category:** Factual Questions
**Created:** [March 7, 2008, 3:07pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444 "2008-03-07T15:07:29Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)
#### Post date: [March 7, 2008, 3:07pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/1 "2008-03-07T15:07:29Z")
I know a Sudoku fanatic as saw a nice, artsy board meant for Sudoku that I thought he might like as a gift. It made me wonder though if, as you placed tiles (with numbers on them) on the 9x9 board if it were possible to make an unsolvable Sudoku?
Is there a proof one way or another on this?
---
### Author:  [@zut](https://boards.straightdope.com/u/zut)
#### Post date: [March 7, 2008, 3:26pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/2 "2008-03-07T15:26:58Z")
“Unsolvable” in the sense that it has _no_ solutions, or “unsolvable” in the sense that it has _multiple_ solutions? The answer to either is clearly “yes,” unless you’re assuming a certain number of tiles.
---
### Author:  [@FatBaldGuy](https://boards.straightdope.com/u/FatBaldGuy)
#### Post date: [March 7, 2008, 4:27pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/3 "2008-03-07T16:27:37Z")
If you take a blank sudoku board and start randomly placing numbers on it, your chances are better than 50/50 that you will come up with a puzzle that is not only unsolvable, but illegal. In other words, the probability is high that you will place 2 or more of the same number in a row, column or block, which is not allowed.
As I understand it, people who create sudoku puzzles start with a grid that is completely filled in (and legal) and then remove some of the numbers.
Remember also, that the pattern of filled and blank squares at the start must be symmetrical on the horzontal, vertical and diagonal axes.
---
### Author:  [@Roog](https://boards.straightdope.com/u/Roog)
#### Post date: [March 7, 2008, 4:30pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/4 "2008-03-07T16:30:58Z")
The pattern need not be symmetrical.
---
### Author:  [@FatBaldGuy](https://boards.straightdope.com/u/FatBaldGuy)
#### Post date: [March 7, 2008, 4:36pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/5 "2008-03-07T16:36:39Z")
Missed the edit window. Actually, it should be symmetrical on both diagonals, not horizontal and vertical.
**Roog** , I suppose you are right that it doesn’t absolute need to be symmetrical, but I have seen that stated as a rule in some sudoku books.
---
### Author:  [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)
#### Post date: [March 7, 2008, 4:50pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/6 "2008-03-07T16:50:34Z")
For the purposes of the discussion I am assuming a legal setup (e.g. not repeating the same number in a row or column).
---
### Author:  [@Roog](https://boards.straightdope.com/u/Roog)
#### Post date: [March 7, 2008, 5:01pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/7 "2008-03-07T17:01:04Z")
As **Fat** said, the puzzles are created by removing numbers from a completely filled grid. When a number is removed (or pair of numbers for the symmetrical case), the algorithm checks to see if the puzzle can be solved from that point using the various standard tricks. So, if the puzzle was created that way, it must be solvable. You can, of course, create an unsolvable puzzle by just putting a few random numbers (without repeats in rows, columns and squares) into the grid.
I’m still looking for a completely unsymmetrical puzzle…
---
### Author:  [@zut](https://boards.straightdope.com/u/zut)
#### Post date: [March 7, 2008, 5:01pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/8 "2008-03-07T17:01:09Z")
[QUOTE=Whack-a-Mole]
For the purposes of the discussion I am assuming a legal setup (e.g. not repeating the same number in a row or column).
[/QUOTE]
Again, “unsolvable” in the sense that it has _no_ solutions, or “unsolvable” in the sense that it has _multiple_ solutions?
```auto
1 X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
```
clearly has multiple solutions, while
```auto
1 2 3 4 5 6 7 8 X
X X X X X X X X 2
X X X X X X X X 3
X X X X X X X X 4
X X X X X X X X 5
X X X X X X X X 6
X X X X X X X X 7
X X X X X X X X 8
X X X X X X X X 9
```
doesn’t _yet_ have an illegal number placement, but clearly has no solution)
---
### Author:  [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)
#### Post date: [March 7, 2008, 5:04pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/9 "2008-03-07T17:04:49Z")
[QUOTE=zut]
Again, “unsolvable” in the sense that it has _no_ solutions, or “unsolvable” in the sense that it has _multiple_ solutions?
[/quote]
I do not see how “multiple” solutions counts as unsolvable. Seems eminently solvable to me.
I see your point in the second example though.
---
### Author:  [@nivlac](https://boards.straightdope.com/u/nivlac)
#### Post date: [March 7, 2008, 5:14pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/10 "2008-03-07T17:14:11Z")
Yeah the problem is not well defined. Of course it is possible to have legal setups with no solutions as well as multiple solutions. If you consider how the puzzles are constructed it is possible to create a puzzle that has a legitimate starting point but whose solution cannot be deducted strictly from logic.
---
### Author:  [@gazpacho](https://boards.straightdope.com/u/gazpacho)
#### Post date: [March 7, 2008, 5:23pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/11 "2008-03-07T17:23:57Z")
[QUOTE=Whack-a-Mole]
I do not see how “multiple” solutions counts as unsolvable. Seems eminently solvable to me.
[/QUOTE]
Well many people consider a proper sudoku puzzle to have one and only one solution. It is a somewhat arbitrary rule but it is followed by most puzzle creators.
---
### Author:  [@zut](https://boards.straightdope.com/u/zut)
#### Post date: [March 7, 2008, 5:44pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/12 "2008-03-07T17:44:22Z")
Perhaps a more interesting question is, “what is the minimum number of numbers that can exist on a Sudoku grid that gives a puzzle with no solution?” Let me propose this:
```auto
X X X | X X X | X X X
X X X | X X X | X X X
X X X | 1 X X | X X X
---------------------
X X 1 | X X X | X X X
X X X | X 2 X | X X X
X X X | X X X | 1 X X
---------------------
X X X | X X 1 | X X X
X X X | X X X | X X X
X X X | X X X | X X X
```
(It’s even symmetric!) Is that minimal?
---
### Author:  [@Hawkeyeop](https://boards.straightdope.com/u/Hawkeyeop)
#### Post date: [March 7, 2008, 5:50pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/13 "2008-03-07T17:50:48Z")
Well, it only takes 2 numbers if you don’t mind the setup being already illegal.
---
### Author:  [@The\_Hamster\_King](https://boards.straightdope.com/u/The_Hamster_King)
#### Post date: [March 7, 2008, 5:55pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/14 "2008-03-07T17:55:13Z")
[QUOTE=Roog]
I’m still looking for a completely unsymmetrical puzzle…
[/QUOTE]
[Here’s one.](http://www.amazon.com/Sudoku-Will-Shortz-2008-Calendar/dp/B000WZPDAA/ref=sr_1_13?ie=UTF8&s=office-products&qid=1204912344&sr=8-13) Most of the Will Shortz sudoku are assymmetrical. Personally I prefer them that way.
---
### Author:  [@Blaster\_Master](https://boards.straightdope.com/u/Blaster_Master)
#### Post date: [March 7, 2008, 6:01pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/15 "2008-03-07T18:01:30Z")
[QUOTE=Whack-a-Mole]
I do not see how “multiple” solutions counts as unsolvable. Seems eminently solvable to me.
I see your point in the second example though.
[/QUOTE]
It must have one and only one solution, otherwise the logic just doesn’t work. I’ve actually seen some in news papers where they don’t have unique solutions, and it’s enormously frustrating, because I’ll easily get it down to a certain point, and end up having a point where I can’t figure out how to progress. Did I mess up my logic, or does the puzzle not have a unique solution? At least I feel vindicated when I plug the problem puzzle into SimpleSudoku (great program, BTW) and it tells me the puzzle has multiple solutions.
Either way, Sudoku puzzles can always be solved without guessing (I believe that’s actually one of the rules), so if it’s purely a series of logical functions, it necessarily must have a single solution.
---
### Author:  [@Peter\_Morris](https://boards.straightdope.com/u/Peter_Morris)
#### Post date: [March 7, 2008, 6:19pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/16 "2008-03-07T18:19:49Z")
Is it possible to have a Suduko that has only one possible solution, BUT it is impossible to deduce the solution, it can only be found by trial and error?
---
### Author:  [@Blaster\_Master](https://boards.straightdope.com/u/Blaster_Master)
#### Post date: [March 7, 2008, 6:33pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/17 "2008-03-07T18:33:08Z")
[QUOTE=Peter Morris]
Is it possible to have a Suduko that has only one possible solution, BUT it is impossible to deduce the solution, it can only be found by trial and error?
[/QUOTE]
That would be difficult to prove. They only way you can say it has a unique solution is by running it through a Sudoku solver and verifying that, when the series of known Sudoku rules are applied iteratively, it produces a unique solution. That is, IF there is only a single solution, that information MUST be somehow within the puzzle, and so there must be some for of logic that can extract that information, otherwise, it wouldn’t dictate a single solution.
Basically, I think it may be possible that there are puzzles that exist that we can’t solve but that’s only because there’s a rule that is as of yet unknown to the solver. For instance, using SimpleSudoku on Extreme mode, I’ve repeatedly run into puzzles that necessarily require one of the most complex rules programmed into it. Had I not known the rule, I would have presumed the puzzle unsolvable. It is entirely possible that there exists even more complex logical rules. Of course, it’s hard to say, because they tend to design the puzzles around the complexity of the rules required to solve it.
---
### Author:  [@ftg](https://boards.straightdope.com/u/ftg)
#### Post date: [March 7, 2008, 10:45pm UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/18 "2008-03-07T22:45:59Z")
[QUOTE=Peter Morris]
Is it possible to have a Suduko that has only one possible solution, BUT it is impossible to deduce the solution, it can only be found by trial and error?
[/QUOTE]
This keeps coming up and I don’t know why. _Of course_ it’s always possible to solve a correctly designed Suduko without guessing. Take the Boolean encoding found on the Wikipedia page for Suduko, encode your puzzle, and solve the Boolean equation by multiplying through. Ta-da. (BTW: the size of the Boolean formula may increase to exponential size along the way, but that’s what you get for messing with NP-Complete problems.)
If anything is computable, it can be done computed deterministically. (Actually, the proof is that non-determinism doesn’t add power.) I have no idea why people think that trial-and-error is so special.
---
### Author:  [@totoismomo](https://boards.straightdope.com/u/totoismomo)
#### Post date: [March 8, 2008, 2:02am UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/19 "2008-03-08T02:02:05Z")
[QUOTE=ftg]
This keeps coming up and I don’t know why. _Of course_ it’s always possible to solve a correctly designed Suduko without guessing. Take the Boolean encoding found on the Wikipedia page for Suduko, encode your puzzle, and solve the Boolean equation by multiplying through. Ta-da. (BTW: the size of the Boolean formula may increase to exponential size along the way, but that’s what you get for messing with NP-Complete problems.)
[/QUOTE]
Can you tell me more about this boolean encoding method of solving? I can’t seem reference to it [here](http://en.wikipedia.org/wiki/Sudoku) , [here](http://en.wikipedia.org/wiki/Mathematics_of_Sudoku), or [here](http://en.wikipedia.org/wiki/Algorithmics_of_sudoku).
---
### Author:  [@Oslo\_Ostragoth](https://boards.straightdope.com/u/Oslo_Ostragoth)
#### Post date: [March 8, 2008, 6:15am UTC](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444/20 "2008-03-08T06:15:30Z")
[QUOTE=Pochacco]
[Here’s one.](http://www.amazon.com/Sudoku-Will-Shortz-2008-Calendar/dp/B000WZPDAA/ref=sr_1_13?ie=UTF8&s=office-products&qid=1204912344&sr=8-13) Most of the Will Shortz sudoku are assymmetrical. Personally I prefer them that way.
[/QUOTE]
Are you referring to the one on the cover?
[Next page](https://boards.straightdope.com/t/are-all-sudoku-configurations-solvable/440444.md?page=2)