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?
“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.
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.
The pattern need not be symmetrical.
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.
For the purposes of the discussion I am assuming a legal setup (e.g. not repeating the same number in a row or column).
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…
Again, “unsolvable” in the sense that it has no solutions, or “unsolvable” in the sense that it has multiple solutions?
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
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)
I do not see how “multiple” solutions counts as unsolvable. Seems eminently solvable to me.
I see your point in the second example though.
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.
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.
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:
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?
Well, it only takes 2 numbers if you don’t mind the setup being already illegal.
Here’s one. Most of the Will Shortz sudoku are assymmetrical. Personally I prefer them that way.
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.
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?
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.
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.
Can you tell me more about this boolean encoding method of solving? I can’t seem reference to it here , here, or here.
Are you referring to the one on the cover?