|
2 weeks ago | |
---|---|---|
fuzzing | 3 months ago | |
.gitignore | 2 weeks ago | |
.gitlab-ci.yml | 1 month ago | |
LICENSE | 8 months ago | |
README.md | 2 weeks ago | |
go.mod | 2 weeks ago | |
go.sum | 2 weeks ago | |
solver.go | 2 weeks ago | |
solver_test.go | 1 month ago |
Sudoku solver is a brute-force recursive solver for 9x9 sudoku puzzles.
You should be using Go modules in your project. Get the sudoku-solver
package:
go get git.sitilge.id.lv/sitilge/sudoku-solver
Run go test -v
in the root directory.
package main
import (
"fmt"
solver "git.sitilge.id.lv/sitilge/sudoku-solver"
"log"
)
func main() {
input := [9][9]uint8{
{0, 4, 2, 0, 0, 0, 0, 0, 5},
{0, 0, 0, 6, 3, 2, 0, 8, 0},
{0, 8, 0, 0, 4, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{7, 1, 5, 0, 6, 8, 3, 4, 0},
{9, 0, 8, 3, 5, 0, 7, 6, 1},
{0, 9, 1, 0, 0, 6, 0, 0, 0},
{0, 0, 0, 0, 2, 0, 1, 9, 0},
{0, 0, 6, 1, 0, 0, 0, 5, 0},
}
//Create a new matrix.
m, err := solver.NewMatrix(input)
if err != nil {
log.Fatal(err)
}
//Solve the puzzle.
solution, err := m.Solve()
if err != nil {
fmt.Printf("unable to solve: %s", err)
}
fmt.Println(solution.String())
}
Sometimes concepts like profiling are invaluable in catching bottlenecks. For example, catching algo flaws reduced time of solving a puzzle ~100x. Some grids took ~100s (yikes!) and got reduced to ~1s. Exploring more bottlenecks discovered some functions to be improved, resulting in ~10x improvement over the previous - now ~100ms. The algo is still slow - much of it comes from calling Valid
, which loops through every row, column, and square to check if the digit is valid. It can be further improved using constraint satisfaction. See this blog post for more ideas.
As regards doing the profiling, you can use the following snippet early in your source and run the program. Then execute go tool pprof solver.prof
and type web
in the interactive prompt. It will take you to the browser tab with a nice visualisation.
f, err := os.Create("solver.prof")
if err != nil {
log.Fatal(err)
}
pprof.StartCPUProfile(f)
defer pprof.StopCPUProfile()
You can use he Dockerfile
to build an image with compatible go-fuzz
and go
versions. The data you acquire during the fuzzing session is valuable, e.g. you should keep the corpus in your git repo.
docker build -f fuzzing/Dockerfile -t sudoku-solver-fuzzing .
docker run \
-v ${PWD}/fuzzing/corpus:/go/src/git.sitilge.id.lv/sitilge/sudoku-solver/fuzzing/corpus \
-v ${PWD}/fuzzing/crashers:/go/src/git.sitilge.id.lv/sitilge/sudoku-solver/fuzzing/crashers \
-v ${PWD}/fuzzing/suppressions:/go/src/git.sitilge.id.lv/sitilge/sudoku-solver/fuzzing/suppressions \
sudoku-solver-fuzzing