go-sudoku-solver
A concurrent & recursive sudoku solver written in golang, based on hexagonal architecture
Motivation
This is a small project that showcases the power of go routines by solving a sudoku puzzle. This solver solves arguably the world’s hardest sudoku ever in around 3 seconds.
Build status
Solution Approach
The solver employs two different sub-approaches to solve a sudoku
- The solver first maps the set of eligible numbers (that can be filled) for each cell. It also fills the cells which have just a single eligible number. This is a map and reduce performed on each cell.
-
If each iteration keeps reducing the number of unfilled cells, the solver keeps repeating map and reduce until the sudoku is solved.
- When the number of unfilled cells stops reducing, the solver switches to a brute force trial and error approach
- Under this approach, the cell with least number of eligible numbers is identified.
- The solver fires a go routine as a recursive call to itself for each of these eligible numbers after filling the cell with the number.
- In the next iteration, the next cell with least number of eligible numbers is picked up, so on and so forth
- This keeps repeating until either the sudoku is solved or a total of 10000000 (ten million) iterations are exhausted.
The approach results in a mega decision tree with each guess on a cell as a node. There is only one path which correctly solves the sudoku. When the solver hits this path, it returns the solved sudoku.
The sudoku is represented as a slice of int slice. A custom Copy method is written to perform deep copy of a sudoku. This is important since each thread of solver must work on a distinct copy of a sudoku to avoid data race.
Results
Here’s a snapshot of the solver run on arguably the world’s hardest sudoku ever.
