Solving sudoku with heuristics: a good idea?

Question

I was trying to solve a partially initialized sudoku puzzle (the kind that appears in newspapers) with the 'Drools Planner' package. While it can generate a (random) puzzle from scratch in 3 seconds, it gets stuck in a loop solving a partially initialized puzzle .

Question: Are heuristics such as tabu search and simulated annealing fundamentally a bad choice for sudoku? I am talking of completeness (will the solution be reached) and efficiency (is it overkill).

My doubt comes from the fact that a sudoku puzzle always has an exact and single solution and heuristic algorithms are (AFAIK) not designed to "reach them".

Answer 1

My answer to your yes/no question, if heuristics such as tabu search and simulated annealing are a bad choice for solving Sudoku, is yes.

The problem has far too many constraints for local search strategies to be efficient.

Sudoku is a good example for a constraint satisfaction problem (CSP), and CSP solvers are very good at solving it. That doesn't mean that local search won't work or that heuristics are a bad idea in general, but this problem can be solved pretty easily by propagating constraints.

Answer 2

Are heuristics such as tabu search and simulated annealing fundamentally a bad choice for sudoku?

Yes, if only because a good constraint propagation algorithm can solve sudokus very fast, so there's no need for heuristics at all. Besides, you (indeed) don't want a partial solution to a sudoku.

Answer 3

For a problem such as the 9x9 Sudoku, a tightly coded brute force search finds a solution very quickly. Further, since it can be certain of finding ALL solutions, it will also determine if the Sudoku is properly formed in that it has a unique solution.