sudoku

sudoku.go

package main

import (
	"errors"
	"fmt"
)

func main() {
	test_puzzle := [9][9]int{
		{5, 0, 0, 0, 0, 9, 1, 0, 0},
		{0, 0, 0, 0, 6, 2, 5, 0, 8},
		{0, 1, 0, 0, 0, 8, 7, 6, 4},
		{0, 6, 5, 0, 1, 3, 0, 2, 0},
		{2, 4, 0, 0, 0, 7, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 7, 0, 0, 0, 0, 0, 5, 6},
		{0, 5, 8, 7, 0, 0, 3, 0, 0},
		{0, 0, 0, 0, 4, 0, 8, 0, 0}}

	for _, row := range test_puzzle {
		for _, col := range row {
			fmt.Print(col, ", ")
		}
		fmt.Println()
	}

	// Valid column tests
	if valid(test_puzzle, 0, 1, 2) != true {
		panic("expected true, got false")
	}
	if valid(test_puzzle, 0, 1, 5) != false {
		panic("expected false, got true")
	}

	// Valid row tests
	if valid(test_puzzle, 2, 0, 3) != true {
		panic("expected true, got false")
	}

	if valid(test_puzzle, 2, 0, 5) != false {
		panic("expected false, got true")
	}

	// Valid 3x3 block tests
	if valid(test_puzzle, 3, 0, 7) != true {
		panic("expected true, got false")
	}
	if valid(test_puzzle, 3, 0, 4) != false {
		panic("expected false, got true")
	}

	solution, err := solve(test_puzzle)
	if err != nil {
		fmt.Println("OH NOES: ", err)
	}

	fmt.Println("--- SOLUTION ---")
	for _, row := range solution {
		for _, col := range row {
			fmt.Print(col, ", ")
		}
		fmt.Println()
	}
}

func solve(puzzle [9][9]int) ([9][9]int, error) {
	// check if the puzzle is alreayd solved
	isComplete := true
	for _, row := range puzzle {
		for _, col := range row {
			if col == 0 {
				isComplete = false
			}
		}
	}
	if isComplete == true {
		return puzzle, nil
	}

	for r := 0; r < 9; r++ {
		for c := 0; c < 9; c++ {
			if puzzle[r][c] == 0 {
				for v := 1; v <= 9; v++ {
					if valid(puzzle, r, c, v) {
						puzzle[r][c] = v
						solution, err := solve(puzzle)
						if err == nil {
							return solution, nil
						}
						puzzle[r][c] = 0
					}
				}
				return puzzle, errors.New("Invalid move")
			}
		}
	}
	return puzzle, errors.New("Invalid")
}

func valid(puzzle [9][9]int, row int, col int, number int) bool {
	// Valid row
	for c := 0; c < 9; c++ {
		if puzzle[row][c] == number {
			return false
		}
	}
	// Valid column
	for r := 0; r < 9; r++ {
		if puzzle[r][col] == number {
			return false
		}
	}

	// Valid 3x3 grid
	startRow := row - row%3
	startCol := col - col%3
	for r := 0; r < 3; r++ {
		for c := 0; c < 3; c++ {
			if puzzle[startRow+r][startCol+c] == number {
				return false
			}
		}
	}

	return true
}