randomfox: (Default)
[personal profile] 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())
}

From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

randomfox: (Default)
randomfox

November 2012

S M T W T F S
    123
45678910
11121314151617
18192021222324
25262728 2930 

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 05:25 am
Powered by Dreamwidth Studios