Solve Sudoku problems in Go.

sudoku.go

package main

import (
	"io/ioutil"
	"log"
	"os"
	"regexp"
	"strings"
)

const (
	ASCII = ".123456789"
	BIN   = "\000\001\002\003\004\005\006\007\010\011"
)

var (
	regWS      = regexp.MustCompile("[ \t\r\n]+")
	regInvalid = regexp.MustCompile("[^123456789\\.]")
)

type puzzle struct {
	grid []byte
}

func newPuzzle(lines string) *puzzle {
	pzl := new(puzzle)

	s := regWS.ReplaceAllString(lines, "")
	if len(s) != 81 {
		log.Fatalf("Grid is the wrong size.")
	}
	invalid := regInvalid.FindStringIndex(s)
	if invalid != nil {
		log.Fatalf("Illegal character %s in puzzle.",
			s[invalid[0]:invalid[1]])
	}
	s = translate(s, ASCII, BIN)
	pzl.grid = []byte(s)

	if pzl.hasDuplicates() {
		log.Fatalf("Initial puzzle has duplicates.")
	}
	return pzl
}

func (pzl *puzzle) copyPuzzle() *puzzle {
	pz := new(puzzle)
	pz.grid = make([]byte, 81)
	copy(pz.grid, pzl.grid)
	return pz
}

func (pzl *puzzle) String() string {
	lines := make([]string, 9)
	for i := 0; i < 9; i++ {
		lines[i] = string(pzl.grid[i*9 : i*9+9])
		lines[i] = translate(lines[i], BIN, ASCII)
	}
	return strings.Join(lines, "\n") + "\n"
}

func (pzl *puzzle) get(row, col int) byte {
	return pzl.grid[row*9+col]
}

func (pzl *puzzle) set(row, col int, newValue byte) {
	if newValue < 0 || newValue > 9 {
		log.Fatalf("Illegal cell value.")
	}
	pzl.grid[row*9+col] = newValue
}

func (pzl *puzzle) eachUnknown(fn func(r, c, b int)) {
	for row := 0; row < 9; row++ {
		for col := 0; col < 9; col++ {
			index := row*9 + col
			if pzl.grid[index] != 0 {
				continue
			}
			box := boxOfIndex(index)
			fn(row, col, box)
		}
	}
}

func (pzl *puzzle) hasDuplicates() bool {
	for row := 0; row < 9; row++ {
		if !unique(pzl.rowDigits(row)) {
			return true
		}
	}
	for col := 0; col < 9; col++ {
		if !unique(pzl.colDigits(col)) {
			return true
		}
	}
	for box := 0; box < 9; box++ {
		if !unique(pzl.boxDigits(box)) {
			return true
		}
	}
	return false
}

func (pzl *puzzle) rowDigits(row int) string {
	return string(pzl.grid[row*9 : row*9+9])
}

func (pzl *puzzle) colDigits(col int) string {
	line := make([]byte, 9)
	for i := 0; i < 9; i++ {
		line[i] = pzl.grid[i*9+col]
	}
	return string(line)
}

func (pzl *puzzle) boxDigits(box int) string {
	line := make([]byte, 9)
	count := 0
	for i := 0; i < 81; i++ {
		if boxOfIndex(i) == box {
			line[count] = pzl.grid[i]
			count++
		}
	}
	return string(line)
}

func (pzl *puzzle) possible(row, col, box int) []byte {
	allDigits := make([]int, 10)
	for _, d := range pzl.rowDigits(row) {
		allDigits[d]++
	}
	for _, d := range pzl.colDigits(col) {
		allDigits[d]++
	}
	for _, d := range pzl.boxDigits(box) {
		allDigits[d]++
	}
	possible := make([]byte, 0, 9)
	for i := byte(1); i <= 9; i++ {
		if allDigits[i] == 0 {
			possible = append(possible, i)
		}
	}
	return possible
}

func translate(s, from, to string) string {
	return strings.Map(func(c int) int {
		i := strings.Index(from, string([]byte{byte(c)}))
		return int(to[i])
	}, s)
}

func boxOfIndex(index int) int {
	row := index / 9
	col := index % 9
	return row/3*3 + col/3
}

func unique(digits string) bool {
	for i := 0; i < 9; i++ {
		if strings.Count(digits, string([]byte{1 + byte(i)})) > 1 {
			return false
		}
	}
	return true
}

func scan(pzl *puzzle) (rmin, cmin int, pmin []byte) {
	changed := true
	for changed {
		changed = false
		rmin = -1
		cmin = -1
		min := 10
		pzl.eachUnknown(func(row, col, box int) {
			p := pzl.possible(row, col, box)
			switch len(p) {
			case 0:
				rmin = -2
				cmin = -2
				return
			case 1:
				pzl.set(row, col, p[0])
				changed = true
			default:
				if !changed && len(p) < min {
					min = len(p)
					rmin, cmin, pmin = row, col, p
				}
			}
		})
	}
	return
}

func solve(pzl *puzzle) *puzzle {
	pzl = pzl.copyPuzzle()
	r, c, p := scan(pzl)
	if r == -1 {
		return pzl
	} else if r == -2 {
		return nil
	}

	for _, guess := range p {
		pzl.set(r, c, guess)
		result := solve(pzl)
		if result != nil {
			return result
		}
	}

	return nil
}

func main() {
	if len(os.Args) < 2 {
		log.Fatalf("You need to provide a input file's name.")
	}
	input, err := ioutil.ReadFile(os.Args[1])
	if err != nil {
		log.Fatalf("Read input file failed: %v", err)
	}
	pzl := newPuzzle(string(input))
	log.Printf("The initial puzzle is:\n%v", pzl)
	result := solve(pzl)
	if result != nil {
		log.Printf("The first solution found is:\n%v", result)
	} else {
		log.Printf("There is no solution to this puzzle.")
	}
}