Solving Sudoku puzzles using constraint programming09 Jun 2018
I’ve been a big fan of Sudoku puzzles for years but never asked myself how to programmatically solve them - perhaps I didn’t want to ruin the magic.
A typical Sudoku puzzle (CC0 from Wikipedia)
Now that I’m spending a lot of time looking at discrete optimization problems at my job, I’m starting to see everything through the lens of CSP.
So one afternoon, as I was scribbling on a magazine puzzle, I realized I could use constraint programming for it. Similar to the classic queens problem, I would define constraint satisfaction and let a backtracking algorithm find a solution.
In less than an hour I got my own implementation running in Python and OR-Tools.
Later I’d find dozens of blogs describing differents way of achieving this, but none using OR-Tools. So here it is, my own implementation of a Sudoku solver inspired by a magazine puzzle and a cup of coffee.
CSP provides an elegant framework to solve problems. As programmers we instinctively jump to imperative conditional logic, but constraint programming lets you zoom out and think of the problem in terms of variables, constraints, and objectives. This means that the algorithm is universal, and you should focus on the problem formulation instead.
- project: sudokill
- code: https://github.com/defvol/sudokill
- technologies: python and or-tools
- topics: constraint programming, constraint satisfaction problem, and discrete programming