## Insoluble Sudoku Puzzles

Post the puzzle or solving technique that's causing you trouble and someone will help

### Insoluble Sudoku Puzzles

Are there insoluble Sudoku puzzles?

Are there some with more than one solution?

I think both statements may be true.
gerrygeek

Posts: 3
Joined: 04 March 2008

A "puzzle" is generally accepted to only be a "puzzle" if it has a valid single grid solution.

An insoluble "puzzle" has either more than 1 solution or it is invalid.

If it has more than one solution a clue has not covered all the remaining "unavoidabe sets"

If it is an invalid "puzzle" it has what I termed a "constrained" grid solution - a grid solution which doesnt satisfy the 3 [row,colum box] constraints.

All valid puzzles - no matter how difficult can be solved by a simple computor program [by backtracking]
All valid puzzles [even the hardest] can be solved by humans [with enough time] to "front-track" or guess. Not reccommended though.

Gerrygeek wrote:I believe I can solve ANY sudoku puzzle. Please post a one you believe to be insolvable and I will try to solve it.

How do you do it then ?

C
coloin

Posts: 1714
Joined: 05 May 2005

### Insoluable Sudoku Puzzles

coloin wrote:
Gerrygeek wrote:I believe I can solve ANY sudoku puzzle. Please post a one you believe to be insolvable and I will try to solve it.

How do you do it then ?

C

Please note that following Gerrygeek's above request which appeared in an earlier Thread I considered it preferable to discontinue that previous thread. I hope this initiative is acceptable, if not, I'll delete my related posts.

Cec
Cec

Posts: 1039
Joined: 16 June 2005

In his first email, Gerrygeek wrote

I believe I can solve ANY sudoku puzzle. Please post a one you believe to be insolvable and I will try to solve it.

It would be nice if one if the heavyduty experts in the forum could give Gerrygeek one of their ultrahard ones. I guess that any Sudoku can be solved by brute force but I believe that the ethos of this forum is to have some form of logical explanation of the steps to solution.
Bigtone53

Posts: 413
Joined: 19 September 2005

### Insoluble SUDOKU problems

But what of my questions please.

CAN there be more than one solution to a Sudoku problem which obey the normal rules?

Can some which seem OK have NO solution?

Can all soluble problems be solved by a computer program? Has anyone written such a program?

Thanks.
Gerrygeek
gerrygeek

Posts: 3
Joined: 04 March 2008

### Re: Insoluble SUDOKU problems

gerrygeek wrote:But what of my questions please.

CAN there be more than one solution to a Sudoku problem which obeys the normal rules?

No, by definition, otherwise it's not a Sudoku. There are problems that look like sudokus but have multuple solutions, for instance because some important clues are missing.
Can some which seem OK have NO solution?

Yes. As you say, they seem OK.
Can all soluble problems be solved by a computer program? Has anyone written such a program?

Yes and yes, if you mean by brute force. However, Sudoku Explainer can solve all known puzzles by logic (afaik); it might take several hours for a really hard one.

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 8983
Joined: 15 May 2006
Location: Berlin

i sent a pm to him containing some of the hardest known todate. with single solutions.

the deffinition of a puzzle is that it must only have a single solution - thus solvable.

mutiple solutions breaks that rule.
puzzles lacking enough specific clues have mutiple solutions and "seem okay"

other puzzles can "seem okay" but have no solution due to some arbritray cell that eventually has no valid clues.

explainer solves via logic.

brute force back tracking solves all puzzles in seconds and can produce the exact number of solutions for each puzzle via recursive trial and error
showing mutiple, zero or 1 solution.

some solvers impliment dancing links to solve quickly.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 781
Joined: 05 September 2006

### Re: Insoluble SUDOKU problems

m_b_metcalf wrote:
gerrygeek wrote:Can all soluble problems be solved by a computer program? Has anyone written such a program?

Yes and yes, if you mean by brute force. However, Sudoku Explainer can solve all known puzzles by logic (afaik); it might take several hours for a really hard one.

forcing chains are on the logic bubble
they require the propagation of propositions:
if this cell is set to X then what happens (using the forcing chain rules)
sudopedia wrote:A Forcing Chain is actually a move simulator. Instead of placing a digit in a cell, we use the chain to find out what would happen when we make that move. "Forcing" refers to the fact that placing a digit in one cell can force another cell to another digit.

the hardest puzzles require nested forcing chains, which means two simultaneous propositions propagated down two separate chains

what distinguishes forcing chains from pure backtracking is that the implications of a
proposition are limited to a single implication chain using naked/hidden singles
whereas in backtracking all implications of each guess (proposition), using the constraints in scope, are used (aka forcing nets)
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA