Suduko simulating Annealing

Question

Is Simulating Annealing a good algorithm for generating and solving Sudoku problems? Why or why not?

I had implemented a Sudoku game with backtracking but now I want to do it with a local search kind of algorithm in Java. However, I have no idea of where to start. Is there any available library I could use?

Answer 1

Sudoku is a problem with breadcrumbs in it that lead to the optimal solution (even in the hardest cases). What I mean by that is that the constraints confine it that much that the combinatorial explosion of the search space isn't too big (relatively speaking of course): the way to proceed is clear. Other examples of such problems are the Einstein/Zebra puzzle, SendMoreMoney puzzle and n-queens. Those are perfect backtracking cases. While Simulated Annealing does kinda work on those, it's not the correct tool for the job (backtracking is). On the other hand, Simulated Annealing (and other metaheuristics) excel at realistic problems such as course timetabling, employee rostering, vrp, ...

An available library you could use is OptaPlanner (Java, open source): Someone already wrote a Sudoku solver for it 2 years ago, for an older version of OptaPlanner (then it was still called Drools Planner). By default it looks like he configured Tabu Search, but it's a 2 line change to switch that to Simulated Annealing.

Answer 2

To answer your 1st question on simulating annealing algorithm,

Pros + Cons of Simulated Annealing

• Good: Quickly finds a minimum

• Bad: May not find global minimum (best solution)

• Increasing temperature makes it slower, but less likely we will get stuck in local minimum

Source: cs.mercer.edu

As for your 2nd question on solving algorithms in Java, see here for full source code with walk through. Hope this helps!