leetcode-go/hard/37.go

package main

// IntMap ...
type IntMap []int

func (im IntMap) set(id, num int) {
	im[id] |= 1 << uint(num)
}

func (im IntMap) get(id, num int) bool {
	return im[id]&(1<<uint(num)) == 1
}

func getAnswer(occur int) (ans byte, ok bool) {
	cnt := 0
	for i, bit := 1, 1; i <= 9; i++ {
		if occur&bit == 0 {
			cnt++
			ans = byte(i + '0')
		}
		bit <<= 1
	}
	return ans, cnt == 1
}

func solveSudoku(board [][]byte) {
	var rowMap, colMap, blockMap IntMap
	rowMap = make([]int, 9)
	colMap = make([]int, 9)
	blockMap = make([]int, 9)
	for y, row := range board {
		for x, col := range row {
			if col == '.' {
				continue
			}
			num := int(col - '0')
			rowMap.set(y, num)
			colMap.set(x, num)
			blockMap.set(y/3*3+x/3, num)
		}
	}
	for y, row := range board {
		for x, col := range row {
			if col != '.' {
				continue
			}
			blockID := y/3*3 + x/3
			occur := rowMap[y] & colMap[x] & blockMap[blockID]
			ans, ok := getAnswer(occur)
			if ok {
				board[y][x] = ans
			}
		}
	}
}

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)
}