/* Copyright (C) 2015 by Alexandru Cojocaru */

/* This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

package main

import (
	"fmt"
)

// Used returns true if n is arleady used in row r or column c or the block
// from the interception of the two.
func used(grid *[9][9]uint8, r, c int, n uint8) bool {
	for c2 := 0; c2 < 9; c2++ {
		if c2 == c {
			continue
		}
		if grid[r][c2] == n {
			return true
		}
	}
	for r2 := 0; r2 < 9; r2++ {
		if r2 == r {
			continue
		}
		if grid[r2][c] == n {
			return true
		}
	}
	br := r - r%3
	bc := c - c%3
	for r2 := br; r2 < br+3; r2++ {
		for c2 := bc; c2 < bc+3; c2++ {
			if r2 == r && c2 == c {
				continue
			}
			if grid[r2][c2] == n {
				return true
			}
		}
	}
	return false
}

func solve(grid *[9][9]uint8) bool {
	r := 0
	c := 0
	for ; r < 9; r++ {
		c = 0
		for ; c < 9; c++ {
			if grid[r][c] == 0 {
				goto b
			}

		}
	}

b:
	if r == 9 {
		return true
	} else {
		var n uint8 = 1
		for ; n <= 9; n++ {
			if !used(grid, r, c, n) {
				grid[r][c] = n
				if solve(grid) {
					return true
				}
				grid[r][c] = 0
			}
		}
		return false
	}
}

func main() {
	var grid = [9][9]uint8{
		{7, 0, 0, 1, 0, 0, 0, 0, 0},
		{0, 2, 0, 0, 0, 0, 0, 1, 5},
		{0, 0, 0, 0, 0, 6, 3, 9, 0},
		{2, 0, 0, 0, 1, 8, 0, 0, 0},
		{0, 4, 0, 0, 9, 0, 0, 7, 0},
		{0, 0, 0, 7, 5, 0, 0, 0, 3},
		{0, 7, 8, 5, 0, 0, 0, 0, 0},
		{5, 6, 0, 0, 0, 0, 0, 4, 0},
		{0, 0, 0, 0, 0, 1, 0, 0, 2},
	}
	fmt.Println(grid)
	solve(&grid)
	fmt.Println(grid)
}