Brute force Sudoku solver

sudoku.go

// Copyright (c) 2013 Jordon Smith <[email protected]>

// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

package main

import (
  "errors"
	"fmt"
	"strconv"
)

/* 
int block = (row/3)*3 + (col/3);
This numbers the blocks like this:
+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

0 - 012 345 678
1 - 012 345 678
2 - 012 345 678
-------------
3 - 012 345 678
4 - 012 345 678
5 - 012 345 678
-------------
6 - 012 345 678
7 - 012 345 678
8 - 012 345 678
*/

type cell struct {
	value     int
	immutable bool
}
type Puzzle [9][9]cell

func NewPuzzle(puzl string) (*Puzzle, error) {
	if len(puzl) != 81 {
		return nil, errors.New("Malformed puzzle string!")
	}
	p := Puzzle{}
	row, col, clues := 0, 0, 0
	for i := 0; i < len(puzl); i++ {
		// this is nasty fix it
		val, err := strconv.Atoi(puzl[i : i+1])
		if err != nil {
			return nil, err
		}

		p[row][col].value = val
		if val != 0 {
			clues++
			p[row][col].immutable = true
		} else {
			p[row][col].immutable = false
		}
		row, col = next(row, col)
	}
	if !p.isValid() {
		return nil, errors.New("Invalid puzzle!")
	}
	fmt.Println("Puzzle has", clues, "clues.")
	return &p, nil
}

func (p *Puzzle) Print() {
	fmt.Println("___________________")
	for row := 0; row < 9; row++ {
		fmt.Printf("|")
		for col := 0; col < 9; col++ {
			fmt.Printf("%d|", p[row][col].value)
		}
		fmt.Printf("\n")
	}
	fmt.Println("-------------------")
}

func (p *Puzzle) isValid() bool {
	for r := 0; r < 9; r++ {
		for c := 0; c < 9; c++ {
			if !checkRow(p, r, c) || !checkColumn(p, r, c) || !checkSection(p, r, c) {
				return false
			}
		}
	}
	return true
}

func checkRow(p *Puzzle, row, col int) bool {
	if p[row][col].value == 0 {
		return true
	}

	for i := 0; i < 9; i++ {
		if p[row][col].value == p[row][i].value && col != i {
			return false
		}
	}
	return true
}

func checkColumn(p *Puzzle, row, col int) bool {
	if p[row][col].value == 0 {
		return true
	}

	for i := 0; i < 9; i++ {
		if p[row][col].value == p[i][col].value && row != i {
			return false
		}
	}
	return true
}

func checkSection(p *Puzzle, row, col int) bool {
	if p[row][col].value == 0 {
		return true
	}

	for r := (row / 3) * 3; r < (row/3)*3+3; r++ {
		for c := (col / 3) * 3; c < (col/3)*3+3; c++ {
			if p[row][col].value == p[r][c].value && row != r && col != c {
				return false
			}
		}
	}
	return true
}

func next(row, col int) (int, int) {
	if col == 8 {
		return row + 1, 0
	}
	return row, col + 1
}

func previous(row, col int) (int, int) {
	if col == 0 {
		return row - 1, 8
	}
	return row, col - 1
}

func SolveRecursive(puzzle *Puzzle, row, col int, backwards bool) bool {
	// if the row is off the puzzle we have completed or failed
	if row > 8 {
		return true
	} else if row == -1 {
		return false
	}

	cell := &puzzle[row][col]
	if !cell.immutable {
		if cell.value == 9 && backwards {
			// reset this cell if we are backtracking and already at 9
			cell.value = 0
		} else {
			for val := cell.value + 1; val <= 9; val++ {
				cell.value = val
				if puzzle.isValid() {
					fmt.Printf("[%d,%d] set to %d\n", row, col, val)
					backwards = false
					break
				} else if val == 9 {
					fmt.Printf("No valid value found for [%d,%d] moving back...\n", row, col)
					cell.value = 0
					backwards = true
				}
			}
		}
	}

	// this was a pre-given cell, move onto the next
	if backwards {
		r, c := previous(row, col)
		return SolveRecursive(puzzle, r, c, backwards)
	}
	r, c := next(row, col)
	return SolveRecursive(puzzle, r, c, backwards)
}

func main() {
	puzzle, err := NewPuzzle("605720039400005100020100004090030706100809005204050080800003020002900001350067408")

	// very bad case
	//puzzle, err := NewPuzzle("900104002080060070000000000400000001070000030300000007000000000030070080100209004")

	//puzzle, err := NewPuzzle("084560093001008050000910740208000071000401000310000504056084000070200800890075430")
	//puzzle, err := NewPuzzle("428159673196374825375862941981423567564718392732596184243681759617945238859237416")
	//puzzle, err := NewPuzzle("000000000000000000000000000000000000000000000000000000000000000000000000000000000")
	//puzzle, err := NewPuzzle("006057091000209400500010870620000040901070206030000089012090004005702000340560700")
	//puzzle, err := NewPuzzle("600108203020040090803005400504607009030000050700803102001700906080030020302904005")
	if err != nil {
		fmt.Println(err)
	} else {
		puzzle.Print()
		if SolveRecursive(puzzle, 0, 0, false) {
			fmt.Println("Solved puzzle!")
			puzzle.Print()
		} else {
			fmt.Println("Failed!")
		}
	}
}