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

Posted by justin on Stack Overflow See other posts from Stack Overflow or by justin
Published on 2011-08-20T23:56:18Z Indexed on 2012/04/15 17:28 UTC
Read the original article Hit count: 274

Filed under:

sudoku

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?

Related posts about sudoku

Do you play Sudoku ?

as seen on Oracle Blogs - Search for 'Oracle Blogs'
Did you know that 11gR2 database could solve a Sudoku puzzle with a single query and, most of the time, and this in less than a second ? The following query shows you how ! Simply pass a flattened Sudoku grid to it a get the result instantaneously ! col "Solution" format a9 … >>> More
Python sudoku programming

as seen on Stack Overflow - Search for 'Stack Overflow'
I need your help on this. I have this program and I must finish it. It's missing 3 parts. Here is the program I'm working with: import copy def display(A): if A: for i in range(9): for j in range(9): if type(A[i][j]) == type([]): print A[i][j][0], … >>> More
Sudoku solver evaluation function

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, So I'm trying to write a simple genetic algorithm for solving a sudoku (not the most efficient way, I know, but it's just to practice evolutionary algorithms). I'm having some problems coming up with an efficient evaluation function to test if the puzzle is solved or not and how many errors there… >>> More
Solving Naked Triples in Sudoku

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I wished I paid more attention to the math classes back in Uni. :) How do I implement this math formula for naked triples? Naked Triples Take three cells C = {c1, c2, c3} that share a unit U. Take three numbers N = {n1, n2, n3}. If each cell in C has as its candidates ci ? N then we can… >>> More
Sudoku Solver

as seen on SQL Blog - Search for 'SQL Blog'
Today I am putting up something silly, just for fun. I set myself the task a while back to write a Sudoku solver in T-SQL, but with two dumb constraints that I would never follow given a real problem: I didn’t look at any documented techniques for solving Sudoku, and I specifically avoided T-SQL solutions… >>> More

Developer IT