The New Sudoku Players' Forum

[gerrygeek]

Are there insoluble Sudoku puzzles?

Are there some with more than one solution?

I think both statements may be true.

[coloin]

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.

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

[Cec]

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

[Bigtone53]

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.

[gerrygeek]

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

[m_b_metcalf]

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

[StrmCkr]

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.

[gsf]

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)

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)