solver

README

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

Documentation

Overview

Package solver provides functionality for solving sudoku puzzles.

Index

• type Coords
  • func NewCoords(x, y uint8) (*Coords, error)
• type Matrix
  • func NewMatrix(input [9][9]uint8) (*Matrix, error)
  • func (m *Matrix) Copy() *Matrix
  • func (m *Matrix) Hash() (string, error)
  • func (m *Matrix) LocalizeSquare(coords *Coords) *Square
  • func (m *Matrix) Solve() (*Matrix, error)
  • func (m *Matrix) Solved() bool
  • func (m *Matrix) String() string
  • func (m *Matrix) Transpose() *Matrix
  • func (m *Matrix) Valid(digit uint8, coords *Coords) bool
• type Square
  • func (s *Square) String() string

Types

type Coords

type Coords struct {
	X uint8
	Y uint8
}

Coords represent the X and Y values in matrix or square.

func NewCoords

func NewCoords(x, y uint8) (*Coords, error)

NewCoords accepts two integers and outputs the new coords.

type Matrix

type Matrix struct {
	Rows [9][9]uint8
	Cols [9][9]uint8
}

Matrix holds all puzzle rows and cols.

func NewMatrix

func NewMatrix(input [9][9]uint8) (*Matrix, error)

NewMatrix accepts the two-dimensional array of rows and outputs a new matrix.

func (*Matrix) Copy

func (m *Matrix) Copy() *Matrix

Copy copies the matrix passed as the receiver into the matrix passed as the argument.

func (*Matrix) Hash

func (m *Matrix) Hash() (string, error)

Hash calculates the SHA256 hash of the matrix.

func (*Matrix) LocalizeSquare

func (m *Matrix) LocalizeSquare(coords *Coords) *Square

LocalizeSquare finds the specific square based on the given coords.

func (*Matrix) Solve

func (m *Matrix) Solve() (*Matrix, error)

Solve performs a brute-force recursion to find all solutions of the matrix.

func (*Matrix) Solved

func (m *Matrix) Solved() bool

Solved checks if the matrix has already been solved.

func (*Matrix) String

func (m *Matrix) String() string

String outputs the matrix in an easy-to-read format.

func (*Matrix) Transpose

func (m *Matrix) Transpose() *Matrix

Transpose transposes the matrix passed as the receiver into the matrix passed as the argument.

func (*Matrix) Valid

func (m *Matrix) Valid(digit uint8, coords *Coords) bool

Valid checks if the given digit and coords are valid with the respect to the provided matrix.

type Square

type Square struct {
	Rows [3][3]uint8
	Cols [3][3]uint8
}

Square holds rows and cols of a single square.

func (*Square) String

func (s *Square) String() string

String outputs the square in an easy-to-read format.