# Sudoku Solver in Go Language

```/*
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 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)
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())
}
```

Tags:
• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic

Your reply will be screened

Your IP address will be recorded

• 0 comments