Is there any algorithm that can solve ANY traditional sudoku puzzles, WITHOUT guessing (or similar techniques)?

Question

Is there any algorithm that solves ANY traditional sudoku puzzle, WITHOUT guessing?

Here Guessing means trying an candidate and see how far it goes, if a contradiction is found with the guess, backtracking to the guessing step and try another candidate; when all candidates are exhausted without success, backtracking to the previous guessing step (if there is one; otherwise the puzzle proofs invalid.), etc.

EDIT1: Thank you for your replies.

traditional sudoku means 81-box sudoku, without any other constraints. Let us say the we know the solution is unique, is there any algorithm that can GUARANTEE to solve it without backtracking? Backtracking is a universal tool, I have nothing wrong with it but, using a universal tool to solve sudoku decreases the value and fun in deciphering (manually, or by computer) sudoku puzzles.

How can a human being solve the so called "the hardest sudoku in the world", does he need to guess?

I heard some researcher accidentally found that their algorithm for some data analysis can solve all sudoku. Is that true, do they have to guess too?

Aureomycin

Just curious, why can't you use backtracking? – Catalpa

Whilst I understand what you are trying to do, and it is possible for beginner/easy ones, some of the harder sudoku puzzles involving a guessing step where you can't progress without taking a gamble and backtracking. – Meit

Does an expert play rubik's cube by trial and error? – Aureomycin

@Justin: No rubik's cubes have always an algorithmic solution. See for example rubikssolver.com – Catalpa

Long ago I was working on such an algorithm and came up with something that is close. I used place finding, candidate checking, and primitive set techniques together. It was able to solve almost everything but the very hard problems. I found something called X-wing and Y-wing technique what I think will complete the solution. But I didn't understand those clearly and abandoned that project. If anyone aware of those technique and ever implemented, we can come up with a complete solution. – Schnell

Please provide or link examples which you consider not solveable by simply having the rules applied over and over by a patient and fast computer. That is what I did and I was disappointed that it solved all sudokus I could find, without the need to do any advanced logic. – Carson

Are you looking for an algorithm/program which did not fail on any known example? Or are you looking for scientific/mathmatical proof that the algorithm can solve anything, i.e. that no unsolveable one can exist? – Carson

Answer 1

You can use the techniques that humans use to solve sudokus. Just keep track of every possible number in every square and place a number if there is only one possibility. Keep updating the possibilies until the sudoku is solved. You can exclude possibilities by using the rules or use some more complex reasoning. For example, if in one row two squares have the possibility 1 and 2, all other squares in that row can't be 1 or 2.

However, keep in mind that not every sudoku has a unique solution, and not every sudoku can be solved with this method.

Edit: More complicated human techniques can be found here:

http://www.sudokudragon.com/sudokustrategy.htm

Catalpa

"not every sudoku can be solved with this method" — So your "answer" doesn't actually answer the question, then. – Youngran

If you have, for example, an empty puzzle, you won't be able to solve it without 'guessing'. There is no answer for the generic case. – Catalpa

Does the empty puzzle count as a "traditional" Sudoku puzzle? Perhaps that category needs to be better defined before an explicit answer can be given. – Youngran

Answer 2

Not a solid answer, just FYI:

There's a online Sudoku solver, solving problem like a human (rather than a computer) with the following strategies.

1: Hidden Singles
2: Naked Pairs/Triples
3: Hidden Pairs/Triples
4: Naked Quads
5: Pointing Pairs
6: Box/Line Reduction
Tough Strategies ==========
7: X-Wing
8: Simple Colouring
9: Y-Wing
10: Sword-Fish
11: XYZ Wing
Diabolical Strategies ==========
12: X-Cycles
13: XY-Chain
14: 3D Medusa
15: Jelly-Fish
16: Unique Rectangles
17: Extended Unique Rect.
18: Hidden Unique Rect's
19: WXYZ Wing
20: Aligned Pair Exclusion
Extreme Strategies ==========
21: Grouped X-Cycles
22: Empty Rectangles
23: Finned X-Wing
24: Finned Sword-Fish
25: Altern. Inference Chains
26: Sue-de-Coq
27: Digit Forcing Chains
28: Nishio Forcing Chains
29: Cell Forcing Chains
30: Unit Forcing Chains
31: Almost Locked Sets
32: Death Blossom
33: Pattern Overlay Method
34: Quad Forcing Chains
"Trial and Error" ==========
35: Bowman's Bingo

I tried it by importing a Sudoku picked from the "very hard" level of a Android Sudoku App, on which I stuck quite a while. The solver worked it out, the most advanced strategy being used is "3D Medusa", really impressive.

About the last strategy,

Bowman’s Bingo doesn’t solve all ‘bifurcating’ Sudokus but if applied thoroughly it will crack more than 80% of them. It’s not a panacea like Tabling or Nishio but it is easier to do and will work better if you are down to your last twenty or so unsolved squares.

Draconic

Answer 3

If you just want any algorithm that works without guessing, you can write all traditional sudokus and their solution in a big lookup table. Your algorithm would be doing a lookup. No guessing involved (but the lookup table still feels dirty to me).

"[...] Jarvis/Russell computed the number of essentially different (symmetrically distinct) solutions as 5,472,730,538." (From https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_essentially_different_Sudoku_solutions)

Hortative

What du you think how much space this lookup table would need? ;) – Osi

Lets say one sudoku and its solution take together 128 byte. Then this lookup table would take about 650 gb. And you have to transform a given sudoku into something like a normalized form to do a lookup, or you have to guess a transformation an make in worst case 2*3!^8 lookups. – Osi

Yes. You can optimize our silly lookup table, by only storing the hints necessary to get a backtrack free algorithm out of a bind. – Hortative

Answer 4

An algorithm has been discovered that is deterministic (i.e. no backtracking), and guaranteed to find a solution to all sudoku problems but it's quite complex.

Details can be found here: http://www.nature.com/srep/2012/121011/srep00725/full/srep00725.html

Suppositious