Sudoku solver algorithm by Golang, converted from Python language by http://norvig.com/sudoku.html

main.go

package main

import (
    "sudoku"    
)

func main(){
    grid := "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
    grid1 := "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"
    hard := ".....6....59.....82....8....45........3........6..3.54...325..6.................."    
    if values, ok := sudoku.Solve(grid); ok{
        sudoku.Display(values)
    }
    if values, ok := sudoku.Solve(grid1); ok{
        sudoku.Display(values)
    }
    if values, ok := sudoku.Solve(hard); ok{
        sudoku.Display(values)
    }
    
}

SudokuBrain.go

package sudoku

/**
* Algorithm from http://norvig.com/sudoku.html
*/

import (
	"fmt"
	"strings"
)
/**
* Expand functions for string
*/
type Digits string

type Square struct {
	Row int
	Col int
}

func (ds Digits) Contains(d rune) bool {
	return strings.ContainsRune(string(ds), d)
}

func (ds Digits) Clone() Digits {
	return ds
}

func (ds Digits) IsEmpty() bool {
	return len(ds) == 0
}

func (ds Digits) IsOne() bool {
	return len(ds) == 1
}

func (ds *Digits) Add(d rune) bool {
	if ds.Contains(d) {
		return false
	} else {
		*ds = *ds + Digits(d)
		return true
	}

}

func (ds Digits) Remove(d rune) Digits {
	return Digits(strings.Replace(string(ds), string(d), "", -1))
}

func (ds Digits) String() string {
	return string(ds)
}

func CloneValues(values map[Square]Digits) map[Square]Digits {
	result := make(map[Square]Digits)
	for k, ds := range values {
		result[k] = ds.Clone()
	}
	return result
}

var digits Digits = Digits("123456789")
var rows []int = []int{0, 1, 2, 3, 4, 5, 6, 7, 8}
var cols []int = []int{0, 1, 2, 3, 4, 5, 6, 7, 8}

func Cross(rows, cols []int) []Square {
	result := make([]Square, len(rows)*len(cols))
	count := 0
	for i := 0; i < len(rows); i++ {
		for j := 0; j < len(cols); j++ {
			result[count] = Square{Row: i, Col: j}
			count++
		}
	}

	return result
}

func Col(col int) []Square {
	result := make([]Square, 9)
	for i := 0; i < 9; i++ {
		result[i] = Square{i, col}
	}
	return result
}

func Row(row int) []Square {
	result := make([]Square, 9)
	for i := 0; i < 9; i++ {
		result[i] = Square{row, i}
	}
	return result
}

func Zone(row, col int) []Square {
	result := make([]Square, 9)
	baseRow, baseCol := row/3*3, col/3*3
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			result[i*3+j] = Square{baseRow + i, baseCol + j}
		}
	}

	return result
}

func InitUnit(row, col int) [][]Square {
	result := make([][]Square, 3)
	result[0] = Row(row)
	result[1] = Col(col)
	result[2] = Zone(row, col)
	return result
}

func InitUnits() map[Square][][]Square {
	result := make(map[Square][][]Square)

	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			result[Square{i, j}] = InitUnit(i, j)
		}
	}

	return result
}

func InitPeers() map[Square]map[Square]Square {
	result := make(map[Square]map[Square]Square)
	for _, s := range squares {
		us := units[s]
		result[s] = make(map[Square]Square)
		for _, uss := range us {
			for _, ss := range uss {
				if ss != s {
					result[s][ss] = ss
				}
			}
		}
	}
	return result
}

// ----------------

var squares []Square = Cross(rows, cols)
var units map[Square][][]Square = InitUnits()
var peers map[Square]map[Square]Square = InitPeers()

// ----------------

func ParseGrid(grid string) (map[Square]Digits, bool) {
	values := make(map[Square]Digits)
	for _, s := range squares {
		values[s] = digits.Clone()
	}

	for s, d := range GridValue(grid) {
		if digits.Contains(d) {

			if otherValues, ok := Assign(values, s, d); ok {
				values = otherValues
			} else {
				return values, false //fail if we can't assign d to square s
			}
		}
	}
	return values, true
}

/**
Convert grid runeo a dict of {square int} with 0 or . for empties
*/
func GridValue(grid string) map[Square]rune {
	values := make(map[Square]rune)
	for i, s := range squares {
		c := grid[i]
		if c >= '1' && c <= '9' {
			values[s] = rune(c)
		} else {
			values[s] = '0'
		}
	}
	return values
}

/**
Eliminate all the other values (except d) from values[s] and propagate.
Return values, except return False if a contradiction is detected.
*/
func Assign(values map[Square]Digits, s Square, d rune) (map[Square]Digits, bool) {
	otherValues := values[s].Remove(d)
	for _, d2 := range otherValues {
		vs, ok := Eliminate(values, s, d2)
		if !ok {
			return vs, false
		} else {
			values = vs
		}
	}
	return values, true
}

/**
Eliminate d from values[s]; propagate when values or places <= 2.
Return values, except return False if a contradiction is detected.
*/
func Eliminate(values map[Square]Digits, s Square, d rune) (map[Square]Digits, bool) {
	if !values[s].Contains(d) {
		return values, true //already elimiated
	}
	values[s] = values[s].Remove(d)
	// (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
	if values[s].IsEmpty() {
		return values, false
	} else if values[s].IsOne() {
		d2 := rune(values[s][0])
		for s2, _ := range peers[s] {
			if vs, ok := Eliminate(values, s2, d2); !ok {
				return vs, false
			} else {
				values = vs
			}
		}
	}

	// (2) If a unit u is reduced to only one place for a value d, then put it there.
	for _, u := range units[s] {
		var dplaces []Square = make([]Square, 0, 5)
		for _, ss := range u {
			if values[ss].Contains(d) {
				dplaces = append(dplaces, ss)
			}
		}

		if len(dplaces) == 0 {
			return values, false
		} else if len(dplaces) == 1 {
			//d can only be in one place in unit; assign it there
			if values1, ok := Assign(values, dplaces[0], d); !ok {
				return values1, false
			} else {
				values = values1
			}

		}
	}
	return values, true
}

func Solve(grid string) (map[Square]Digits, bool) {
	values, ok := ParseGrid(grid)
	if ok {
		return Search(values, ok)
	} else {
		return nil, false
	}
}

func Search(values map[Square]Digits, previous bool) (map[Square]Digits, bool) {
	if !previous {
		return values, false
	}

	flag := true
	for _, d := range values {
		if len(d) > 1 {
			flag = false
			break
		}
	}

	if flag {
		return values, true
	}

	var minS Square
	var min int = 10
	for _, s := range squares {
		if len(values[s]) > 1 && len(values[s]) < min {
			minS = s
			min = len(values[s])
		}
	}

	for _, d := range values[minS] {
		if values1, ok1 := Assign(CloneValues(values), minS, d); ok1 {
			if values2, ok2 := Search(values1, ok1); ok2 {
				return values2, ok2
			}
		}
	}

	return values, false
}

//---------------
func nSpace(n int) string {
	result := ""
	for i := 0; i < n; i++ {
		result += " "
	}
	return result
}

func maxLength(values map[Square]Digits) int {
	max := 0
	for _, v := range values {
		if len(v) > max {
			max = len(v)
		}
	}

	return max
}

func Display(values map[Square]Digits) {
	width := maxLength(values) + 1
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			fmt.Print(values[Square{i, j}], nSpace(width-len(values[Square{i, j}])))
			if j == 2 || j == 5 {
				fmt.Print("| ")
			}
		}
		fmt.Println()
		if i == 2 || i == 5 {
			fmt.Println("------+-------+------")
		}
	}

	fmt.Println()
}