3

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".

Jesvin Jose
  • 22,498
  • 32
  • 109
  • 202
  • Sudoku puzzles can have more than one solution – Sentry Feb 01 '12 at 12:44
  • 2
    @Sentry - The point is that they don't. At least not well-designed ones. – Anders Marzi Tornblad Feb 01 '12 at 12:52
  • Updated the question with "the kind that appears in newspapers" to clear the misconception – Jesvin Jose Feb 01 '12 at 12:58
  • 1
    @atornblad - You're probably right if you consider sudoku puzzles you find in newspapers and such. But the general problem class of sudokus also includes a 9x9 grid with only one initial digit in it. And I just saw the updated question ;) – Sentry Mar 09 '12 at 16:00

3 Answers3

4

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.

Sentry
  • 4,102
  • 2
  • 30
  • 38
1

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.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
-1

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.

cmm
  • 319
  • 3
  • 11