Sudoku Solver in Go Language

[randomfox]

/*
    Sudoku solver.

    Last updated: November 27, 2012
    Author: Po Shan Cheah

    This is a puzzle where you have to fill all the blank spaces with digits
    from 1 to 9 such that no row, column, or 3x3 block of cells have any
    digits repeated.

    Supply the puzzle via standard input or via a file whose file name is
    given as the first command line argument. Example input:

	xxx 6xx 9x2
	xx6 1xx x87
	2x7 5xx xx1

	xxx xx8 7xx
	4x2 xxx 1x6
	xx9 2xx xxx

	6xx xx3 5x8
	59x xx1 2xx
	8x4 xx7 xxx
*/

package main

import (
    "bufio"
    "fmt"
    "io"
    "log"
    "os"
    "regexp"
    "strconv"
    "time"
)

type boardType [9][9]int

/*
   Returns a buffered reader after opening the first command line argument
   as a file. If there is no command line argument, returns a buffered
   reader of stdin.
*/
func getInput() *bufio.Reader {
    inf := os.Stdin
    if len(os.Args) >= 2 {
	file, err := os.Open(os.Args[1])
	if err != nil {
	    log.Fatal(err)
	}
	inf = file
    }
    return bufio.NewReader(inf)
}

// Parse board information from input. Returns a 2D array with numbers from
// the puzzle and 0s for empty cells.
func readBoard() *boardType {
    var board boardType

    bufin := getInput()
    wsRegex := regexp.MustCompile(`\s+`)
    lineno := 0
    for lineno < 9 {
	line, err := bufin.ReadString('\n')
	if err == io.EOF {
	    log.Fatalf("Not enough rows. Only %d found.\n", lineno)
	}
	if err != nil {
	    log.Fatal(err)
	}

	// Remove whitespace.
	line2 := wsRegex.ReplaceAllString(line, "")

	if len(line2) > 0 {
	    if len(line2) < 9 {
		log.Fatalf("Line %d: '%s' does not have enough cells.\n", lineno, line)
	    }

	    for pos, ch := range line2 {
		if pos >= 9 {
		    break
		}
		cell, _ := strconv.Atoi(string(ch))
		board[lineno][pos] = cell
	    }

	    lineno += 1
	}
    }

    return &board
}

// Display the board.
func (board *boardType) printBoard() {
    for rownum, row := range *board {
	for colnum, cell := range row {
	    fmt.Printf("%d ", cell)
	    if colnum % 3 == 2 {
		fmt.Print(" ")
	    }
	}
	fmt.Println()
	if rownum % 3 == 2 {
	    fmt.Println()
	}
    }
}

// Return a list of numbers that could go into cell row, col on the board.
func (board *boardType) getPossible(row, col int) []int {
    used := map[int] bool {}

    // Check row and column.
    for i := 0; i < 9; i++ {
	used[(*board)[row][i]] = true
	used[(*board)[i][col]] = true
    }

    // Check the 3x3 block containing this cell.
    blockrow := row - row % 3
    blockcol := col - col % 3
    for i := blockrow; i < blockrow + 3; i++ {
	for j := blockcol; j < blockcol + 3; j++ {
	    used[(*board)[i][j]] = true
	}
    }

    possible := []int {}
    for i := 1; i <= 9; i++ {
	if !used[i] {
	    possible = append(possible, i)
	}
    }
    return possible
}

// Keeps track of the number of board possibilities (partial solutions and
// dead ends) examined.
var nodecount int = 0

// Recursive function to find a solution by exhaustive search. Returns true
// if solution found.
func tryBoard(board *boardType, row, col int) bool {
    // If we are already past all the rows and columns then we have a
    // solution.
    if row >= 9 || col >= 9 {
	fmt.Println("Found a solution:")
	board.printBoard()
	return true
    }

    nodecount++

    // Calculate the next column, wrapping over to the next row if
    // necessary.
    nextrow := row
    nextcol := col + 1
    if nextcol >= 9 {
	nextrow ++
	nextcol = 0
    }

    // Skip over cells that are already filled.
    if (*board)[row][col] != 0 {
	return tryBoard(board, nextrow, nextcol)
    }

    // Try all numbers that fit in the current cell.
    for _, tok := range board.getPossible(row, col) {
	(*board)[row][col] = tok
	if tryBoard(board, nextrow, nextcol) {
	    return true
	}
    }
    (*board)[row][col] = 0
    return false
}

func main() {
    board := readBoard()

    fmt.Println("Puzzle:")
    board.printBoard()

    start := time.Now()
    if !tryBoard(board, 0, 0) {
	fmt.Println("No solution found.")
    }
    elapsed := time.Since(start)
    fmt.Printf("%d nodes examined.\n", nodecount)
    fmt.Printf("Elapsed time: %f seconds\n", elapsed.Seconds())
}