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
- calculate(through an simple rule checking) all possible values of each cell that is empty.
- Count empty cells
- If any cell has only one possibility, set the cell value and re-calculate all possibility
- re-count empty cells
- If old empty cell count < new empty cell count, repeat
- 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
- set first possibility for first empty cell
- check if grid isValid==true; (if solved then break), else set first possibility for next cell, repeat
- 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:
- randomly set the values of each empty cell
- calculate error count
- Generate a random neighboring solution and re-count errors
- if new error count < old error count: keep new grid, else keep old one
- if grid is solved then break; else repeat
Now for my questions:
- Is my simulated annealing algorithm correct?
- 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.
- How do I generate random neighboring solution in step 3