sudoku.go

package main

import (
	"fmt"
	"os"
)

const (
	size = sqrt * sqrt
	sqrt = 3
)

func main() {
	var t table
	empties := make([]pointer, 0, 50)
	for i := 0; i < size; i++ {
		var line string
		fmt.Scan(&line)
		if len(line) != size {
			panic("please insert 9 chars")
		}
		for j, c := range line {
			if '1' <= c && c <= '9' {
				t[i][j] = int(c - '0')
			} else {
				empties = append(empties, pointer{i, j})
			}
		}
	}
	think(&t, empties, 0)
	fmt.Println("no answer")
}

func think(t *table, empties []pointer, depth int) {
	if len(empties) == depth {
		for y := 0; y < size; y++ {
			for x := 0; x < size; x++ {
				fmt.Print(t[y][x])
			}
			fmt.Println()
		}
		os.Exit(0)
	}
	p := empties[depth]
	var conflict [size + 1]bool // tricky +1
	for px := 0; px < size; px++ {
		n := t[px][p.y]
		conflict[n] = true
	}
	for py := 0; py < size; py++ {
		n := t[p.x][py]
		conflict[n] = true
	}
	for px := p.x / sqrt * sqrt; px < (p.x/sqrt+1)*sqrt; px++ {
		for py := p.y / sqrt * sqrt; py < (p.y/sqrt+1)*sqrt; py++ {
			n := t[px][py]
			conflict[n] = true
		}
	}
	for n := 1; n <= size; n++ {
		if !conflict[n] {
			t[p.x][p.y] = n
			think(t, empties, depth+1)
			t[p.x][p.y] = 0
		}
	}
}

type table [size][size]int

type pointer struct{ x, y int }