leetcode-go/hard/37.go

package main

const (
	// ROW ...
	ROW = iota
	// COL ...
	COL
	// BLOCK ...
	BLOCK
)

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

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

func (m SudokuMap) put(area, id, num int) {
	m[area][id] |= 1 << uint(num)
}

func (m SudokuMap) del(area, id, num int) {
	m[area][id] &= (1 << uint(num)) ^ 0x1FF
}

func solveSudoku(board [][]byte) {
	var m SudokuMap
	m = make([][]int, 3)
	for i := range m {
		m[i] = make([]int, 9)
	}
	for y, row := range board {
		for x, col := range row {
			if col == '.' {
				continue
			}
			num := int(col - '0')
			m.put(ROW, y, num)
			m.put(COL, x, num)
			m.put(BLOCK, y/3*3+x/3, num)
		}
	}
	stack := make([]Grid, 0)
	for y, row := range board {
		for x, col := range row {
			if col != '.' {
				continue
			}
			occur := m[ROW][y] & m[COL][x] & m[BLOCK][y/3*3+x/3]
			bit := 1
			for i := 0; i < 9; i++ {
				if bit&occur == 0 { // Is valid
					stack = append(stack, Grid{x, y, 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)
}