go-challenge8

sudoku-solver.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const (
	height = 9
	width  = 9
	delim  = " "
)

var puzzle [height][width]int

func checkPuzzle() bool {
	for h := 0; h < height; h++ {
		if ok := checkPuzzleInternal(0, width, h, h+1); !ok {
			return false
		}
	}

	for w := 0; w < width; w++ {
		if ok := checkPuzzleInternal(w, w+1, 0, height); !ok {
			return false
		}
	}

	for h := 0; h < height; h += 3 {
		for w := 0; w < width; w += 3 {
			if ok := checkPuzzleInternal(w, w+3, h, h+3); !ok {
				return false
			}
		}
	}

	return true
}

func checkPuzzleInternal(ws, we, hs, he int) bool {
	m := make(map[int]bool)
	for w := ws; w < we; w++ {
		for h := hs; h < he; h++ {
			if puzzle[h][w] == 0 {
				continue
			}
			if _, exists := m[puzzle[h][w]]; exists {
				return false
			}
			m[puzzle[h][w]] = true
		}
	}
	return true
}

func getBlankIndex() (int, int) {
	var i, j int
	for i = 0; i < height; i++ {
		for j = 0; j < width; j++ {
			if puzzle[i][j] == 0 {
				return i, j
			}
		}
	}
	return height, width
}

func solve() {
	h, w := getBlankIndex()
	if h == height && w == width {
		for i := 0; i < height; i++ {
			for j := 0; j < width; j++ {
				if j > 0 {
					fmt.Print(delim)
				}
				fmt.Print(puzzle[i][j])
			}
			fmt.Print("\n")
		}
		os.Exit(0)
	}
	for n := 1; n <= 9; n++ {
		puzzle[h][w] = n
		if checkPuzzle() {
			solve()
		}
	}
	puzzle[h][w] = 0
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	i := 0
	for scanner.Scan() {
		if i >= width {
			return
		}
		for j, s := range strings.Split(scanner.Text(), delim) {
			if j >= width {
				return
			}
			var n int
			var err error
			if strings.Compare(s, "_") == 0 {
				n = 0
			} else {
				n, err = strconv.Atoi(s)
				if err != nil {
					fmt.Println(err)
					os.Exit(1)
				}
			}
			puzzle[i][j] = n
		}
		i += 1
	}

	solve()
	fmt.Println("Could not solve it.")
	os.Exit(1)
}