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

11
votes

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?

4
sudoku
Just curious, why can't you use backtracking? – Patrik
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. – Wil
Does an expert play rubik's cube by trial and error? – justin
@Justin: No rubik's cubes have always an algorithmic solution. See for example rubikssolver.com – Patrik
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. – Dipto

4 Answers

3
votes

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

2
votes

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.

1
votes

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)

0
votes

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