sudoku.go

package main

import (
    "fmt"
    "os"
    "flag"
    "log"
    "bufio"
)

type board struct {
    cells [9][9]byte
    rows, cols [9]uint16
    secs [3][3]uint16
    got byte
}

var b board

func (b *board)set(x, y int, v byte) bool {
    if b.cells[y][x] != 0 {
        panic("huh?")
    }
    var vm uint16 = 1 << v
    sx, sy := x/3, y/3

    if ((b.secs[sy][sx] | b.rows[y] | b.cols[x]) & vm) != 0 { return true }

    b.cells[y][x] = v
    b.got ++
    b.secs[sy][sx] |= vm
    b.rows[y] |= vm
    b.cols[x] |= vm
    return false
}

func (b *board)isReady() bool { return b.got == 81 }

func mask2free(mask uint16) (v []byte) {
    for i := 1; i <= 9; i ++ {
        if ((1 << uint(i)) & mask) == 0 {
            v = append(v, byte(i))
        }
    }
    return
}

func (b *board)solve() board {
    b_x, b_y, b_len := 0, 0, 100
    var b_cands []byte

    for got := true; got; {
        got = false
        b_len = 100
        b_cands = nil

        for y, l := range(b.cells) {
            for x, c := range(l) {
                if c == 0 {
                    sx, sy := x/3, y/3
                    vm := b.rows[y] | b.cols[x] | b.secs[sy][sx]
                    cands := mask2free(vm)
                    c_l := len(cands)

                    if c_l == 0 {
                        return *b
                    }

                    if c_l > 1 {
                        if c_l < b_len {
                            b_len = c_l
                            b_x = x
                            b_y = y
                            b_cands = cands
                        }
                        continue
                    }

                    got = true
                    b.set(x, y, cands[0])
                    if b.isReady() {
                        return *b
                    }
                }
            }
        }
    }

    for _, c := range(b_cands) {
        b1 := *b
        b1.set(b_x, b_y, c)
        b1 = b1.solve()
        if b1.isReady() {
            return b1
        }
    }

    return *b
}

func readBoard(fname string) (b board) {
    file, err := os.Open(fname)
    if err != nil {
        log.Fatal(err)
    }
    defer file.Close()

    r := bufio.NewReader(file)

    for y := range(b.cells) {
        l, err := r.ReadBytes('\n')
        if err != nil {
            log.Fatal(err)
        }

        if (len(l) != 10) {
            log.Fatal("line too long:", l)
        }

        for x := 0; x < 9; x ++ {
            c := l[x]
            if c >= '1' && c <= '9' {
                if b.set(x, y, c - '0') {
                    panic("set!")
                }
            }
        }
    }

    return
}

func printBoard(b board) {
    for _, l := range(b.cells) {
        for x := range(l) {
            c := l[x]
            if c > 0 {
                fmt.Printf("%d", l[x])
            } else {
                fmt.Print(".")
            }
        }
        fmt.Println("")
    }
}

func init() {
    flag.Parse()
    args := flag.Args()

    if len(args) == 0 {
        log.Fatal("no args!")
    }

    b = readBoard(args[0])
}

func main() {
    printBoard(b)
    printBoard(b.solve())
}