Creating a Sudoku Solver Algorithm from Scratch

3 years ago
69

A walkthrough showing how to solve a Sudoku with an algorithm written from scratch (using Kotlin).

ERRATA: I loosely refer to the "Branch-and-Prune" algorithm as "Branch-and-Bound" at times in this presentation. This technically is not correct as I'm not doing any linear relaxation that occurs in optimization variants of state space search problems. I'm simply pruning branches that do not meet constraints.

The branch-and-prune/branch-and-bound algorithm can be enormously useful not just for solving Sudokus, but also real-world problems like scheduling (staff, classrooms, server jobs, transportation) and the knapsack problem.

GitHub source code can be found here:
https://github.com/thomasnield/kotlin-sudoku-solver

Here is an example that generates a classroom schedule:
https://github.com/thomasnield/optimized-scheduling-demo

If you want to learn more about discrete optimization, I highly recommend this class on Coursera:
https://www.coursera.org/learn/discrete-optimization/home/welcome

Loading comments...