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 a125da9972 Update some comments 10 months ago
fuzzing Update the initial corpus, remove crashers and suprresions dirs, update the fuzzer 1 year ago
.gitignore Update some comments 10 months ago
.gitlab-ci.yml Output test coverage report that can be aggregated by GitLab 1 year ago
LICENSE Gofmt the project and added license 1 year ago
README.md Update some comments 10 months ago
go.mod Update some comments 10 months ago
go.sum Update some comments 10 months ago
solver.go Update some comments 10 months ago
solver_test.go Update the hash function based on the report by gosec 1 year ago

README.md

sudoku-solver

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

Installation

You should be using Go modules in your project. 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