Sudoku solver is a brute-force recursive solver for 9x9 sudoku puzzles.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
Martins Eglitis 5f24787c98 Update the initial corpus, remove crashers and suprresions dirs, update the fuzzer 3 weeks ago
fuzzing Update the initial corpus, remove crashers and suprresions dirs, update the fuzzer 3 weeks ago
.gitignore Add fuzzy tests 3 weeks ago
.gitlab-ci.yml Create a GitLab pipeline 1 month ago
LICENSE Gofmt the project and added license 5 months ago
README.md Update README.md 3 weeks ago
go.mod Add new corpus for fuzzing, update readme and Dockerfile 3 weeks ago
go.sum Add new corpus for fuzzing, update readme and Dockerfile 3 weeks ago
solver.go Update some comments 3 weeks ago
solver_test.go Update benchmarking to consider all matrices available 3 weeks ago

README.md

sudoku-solver

Sudoku solver is a brute-force recursive solver for 9x9 sudoku puzzles.

Installation

Get the sudoku-solver package:

go get git.sitilge.id.lv/sitilge/sudoku-solver

Testing

Run go test -v in the root directory.

Usage

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())
}

Profiling

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()

Fuzzing

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