solver

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