Insoluble Sudoku Puzzles

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

Insoluble Sudoku Puzzles

Postby gerrygeek » Thu Mar 06, 2008 8:19 pm

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

Postby coloin » Thu Mar 06, 2008 8:35 pm

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: 1629
Joined: 05 May 2005

Insoluable Sudoku Puzzles

Postby Cec » Fri Mar 07, 2008 11:07 am

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

Postby Bigtone53 » Fri Mar 07, 2008 4:05 pm

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

Postby gerrygeek » Fri Mar 07, 2008 11:22 pm

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

Postby m_b_metcalf » Fri Mar 07, 2008 11:35 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Postby StrmCkr » Sat Mar 08, 2008 8:03 am

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.
User avatar
StrmCkr
 
Posts: 625
Joined: 05 September 2006

Re: Insoluble SUDOKU problems

Postby gsf » Sat Mar 08, 2008 5:02 pm

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


Return to Help with puzzles and solving techniques