package main

// Slice ...
type Slice []interface{}

// Pop ...
func (s *Slice) Pop() interface{} {
	l := len(*s)
	top := (*s)[l-1]
	*s = (*s)[:l-1]
	return top
}

// Empty ...
func (s Slice) Empty() bool {
	return len(s) == 0
}

// Grid ...
type Grid struct {
	X   int
	Y   int
	Val int
}

// SudokuMap ...
type SudokuMap [][]int

// NewSudokuMap ...
func NewSudokuMap() (m SudokuMap) {
	m = make([][]int, 3) // 0 for col, 1 for row and 2 for block id
	for i := range m {
		m[i] = make([]int, 9)
	}
	return
}

var mask = [...]int{1, 2, 4, 8, 16, 32, 64, 128, 256, 512}

// Put ...
func (m SudokuMap) Put(x, y, val int) {
	m[0][x] |= mask[val]
	m[1][y] |= mask[val]
	m[2][y/3*3+x/3] |= mask[val]
}

// Get ...
func (m SudokuMap) Get(x, y, val int) bool {
	return (m[0][x]|m[1][y]|m[2][y/3*3+x/3])&mask[val] != 0
}

// Del ...
func (m SudokuMap) Del(x, y, val int) {
	mask := mask[val] ^ 0x3FF
	m[0][x] &= mask
	m[1][y] &= mask
	m[2][y/3*3+x/3] &= mask
}

func solveSudoku(board [][]byte) {
	// Init sudoku and count blank grid
	m := NewSudokuMap()
	blank := 0
	for y := range board {
		for x := range board[y] {
			if board[y][x] == '.' {
				blank++
			} else {
				m.Put(x, y, int(board[y][x]-'0'))
			}
		}
	}
	var stack Slice = make([]interface{}, 0)
	for len(stack) != blank { // Assume that all quetion is solvable
		for y := 0; y < 9; y++ {
			for x, i := 0, 1; x < 9; x++ {
				if board[y][x] == '.' { // Never use 'copy' or 'range' when backtracking in golang!!!
					for ; i <= 9; i++ {
						if !m.Get(x, y, i) { // Is valid
							m.Put(x, y, i)
							stack = append(stack, Grid{x, y, i})
							i = 1 // Reset next val
							break
						}
					}
					if i == 10 { // Not valid
						top := stack.Pop().(Grid)
						m.Del(top.X, top.Y, top.Val)
						x, y, i = top.X-1, top.Y, top.Val+1 // Try next val of last step
					}
				}
			}
		}
	}
	for !stack.Empty() {
		top := stack.Pop().(Grid)
		board[top.Y][top.X] = byte(top.Val + '0')
	}
}

// func main() {
// 	b1 := [][]byte{
// 		{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
// 		{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
// 		{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
// 		{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
// 		{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
// 		{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
// 		{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
// 		{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
// 		{'.', '.', '.', '.', '8', '.', '.', '7', '9'}}
// 	solveSudoku(b1)
// 	printBoard(b1)

// 	println()
// 	b2 := [][]byte{
// 		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
// 		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
// 		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
// 		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
// 		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
// 		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
// 		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
// 		{'.', '.', '.', '.', '.', '.', '.', '.', '.'},
// 		{'.', '.', '.', '.', '.', '.', '.', '.', '.'}}
// 	solveSudoku(b2)
// 	printBoard(b2)
// }