Simple sudoku solver using constraint propagation
What’s your favorite activity when you’re bored and there’s absolutely nothing else to do ? solving a sudoku ? No, it’s much more interesting to write a sudoku solver !
Solving NxN Sudoku is known to be a NP-complete problem, but it can still be done in a few milliseconds in a vast majority of cases.
Stop thinking about Brute-force search : even 9x9 grids would require seconds to solve !
Basically, Sudoku is a constraints satisfaction problem (like the eight queens, magic squares, …) and there’s a much clever way to solve this : “Constraint propagation”. In a way that mimics human reasoning.
What you do as a human is first find a cell having a single candidate, set it, and do it again. Simply.
When you “set” a cell, you propagate a new constraint to neighboor cells (ie same row, same column, same block), and so decreasing the choices.
Take a look at the board below for a better understanding. Cell candidates are drawn with small digits. Notice the small green “3”, there’s no other choice regarding to constraints. So we set this cell with “3” and remove “3” in the candidates of the same row, same column and same block in order to fit rules.
Easy grids will solve only using this basic technique called “lone single”, but there are other techniques like “hidden singles”, “naked pairs”, … that can be used when there’s no lone single or to speed up solving. (see here for a list : https://www.learn-sudoku.com/basic-techniques.html.)
So here is a simple program that first finds as much “lone single” as it can.
When there’s no more single, it finds the cell having the less candidates and explores each of them. One of them is good, others are bad and create conflict.
As we dont know in advance, we save the state so when a conflict is detected, we go back to that state and choose another candidate. This technique is called “backtracking”, and yes you have already done that on hard sudoku with your favorite eraser !;)
I know it’s not the first program to use this techniques and other sophisticated algorithms like the Dancing Links have a better time complexity. It’s a compromise between simplicity (it would require more code to implement other techniques) and performance. Even a simple technique can dramatically reduce the search tree and speed up the solving of the hardest sudoku grids.
As a bonus, this one can solve 16x16 grids (with a little more milliseconds :) and could be extended easily to 25x25.
So next, what about generating sudoku grids ?
Start thinking about how it can be done, maybe using a solver, maybe transforming an existing one, and how to make it unique !
Note : This constraint propagation algorithm is very special case of a more generic algorithm called “SAT solvers” which use “CNF” boolean expression reduction (and also a little backtracking).
demo