A quick google search will provide you with numerous Sudoku solvers and algorithms including ones using backtracking, exploratory search, etc. Such algorithms can find a solution (if exists) to a Sudoku problem even if it is not humanly possible find deterministic cell values. Of course, a brute force approach by a human being will probably eventually yield the correct solution, but for this post I consider the approach used to selectively use constraints to determine the correct cell values one by one. One can trivially reduce a Sudoku problem to one that doesn't have enough values to apply constraints and find correct values in a deterministic way.
This solver uses the same constraint based approaches to selectively determine the solution cell by cell. In other words, I have tried to make this solver akin to human heuristic solving and any sudoku problem solvable by this is guaranteed to be solvable by a human in the deterministic approach described above. Overall, this solver can double as a classifier of sudoku puzzles into difficulty levels based on certain parameters. Code available here.
No comments:
Post a Comment