Sudoku Solver BackTracking vs Simulated Annealing

Question

Before you read any further, assume you know what sudoku game and how to go about solving it.

So I have created a sudoku solver with brute-force: The algorithm goes as

1. calculate(through an simple rule checking) all possible values of each cell that is empty.
2. Count empty cells
3. If any cell has only one possibility, set the cell value and re-calculate all possibility
4. re-count empty cells
5. If old empty cell count < new empty cell count, repeat
6. else apply bruteforce

Brute Force algorithm
1. (nested)for each cell apply first possibility
2. Check isSolved if true? break: else apply second possibility and repeat.

While the above B.F. algorithm works for easy and medium problems, but difficult problems with a lot of possibilities for each cell, crashes the program due to nested for loop

My backtracking algorithm uses the same first algo to narrow down the search, then

1. set first possibility for first empty cell
2. check if grid isValid==true; (if solved then break), else set first possibility for next cell, repeat
3. if grid isValid==false, go back to previous cell and set next possibility and continue

I have applied BackTracking algorithm on 6x6 grid and it works, I have yet to apply it on 9x9 grid.

Simulated Annealing algorithm:

1. randomly set the values of each empty cell
2. calculate error count
3. Generate a random neighboring solution and re-count errors
4. if new error count < old error count: keep new grid, else keep old one
5. if grid is solved then break; else repeat

Now for my questions:

1. Is my simulated annealing algorithm correct?
2. Obviously BackTracking will solve the problem much faster than BruteForce, How much faster will Simulated Annealing solve a problem? Since it shuffles randomly it might end up taking longer to solve than BackTracking.
3. How do I generate random neighboring solution in step 3

Answer 1

1. Is my simulated annealing algorithm correct?

This is not Simulated Annealing, what you describe is called Stochastic Hill Climbing. SA will also accept new configurations with a certain probability when they are worse than the old configuration (and lower that probability over time). You did not specify how exactly you calculate "error count", and, as you already mentioned, the way you produce "neighboring solutions". It will depend on those details if a non-deterministic algorithm will get stuck in a local minimum (which means it will not produce a solution with error count 0). Note that even when you implement a correct SA algorithm, there is no guarantee it will find a global optimum, which is probably what you are looking for here.

2. Obviously BackTracking will solve the problem much faster than BruteForce, How much faster will Simulated Annealing solve a problem?

That depends on the actual implementation of both, and how much optimization effort you invest in each of the implementations. However, a real SA algorithm needs you to specify an "initial temperature" and a "cooling down" rate, and if you specify these parameters wrong, you end up with either a very slow algorithm, or an algorithm which does not find a solution at all. Simple "Hill Climbing" will most probably give you the latter.

3. How do I generate random neighboring solution in step 3

You can try out different things, but one simple approach would probably be to modify one cell and exchange one number by another. Another simple approach is to distribute each digit from 1 to 9 exactly 9 times over the grid, and then swap cell contents randomly.

Check also my answer on this older SO question.