sudoku_solver.go

/*
  Solution:
    - Backtracking: O(1) time, O(1) space
*/
func solveSudoku(board [][]byte) {
	columns := initColumns(board)
	rows := initRows(board)
	squares := initSquares(board)

	backtrack(board, columns, rows, squares, 0, 0)
}

func initColumns(board [][]byte) []map[byte]struct{} {
	columns := make([]map[byte]struct{}, len(board))

	for j := 0; j < len(board[0]); j++ {
		columns[j] = make(map[byte]struct{})
		for i := 0; i < len(board); i++ {
			if board[i][j] == '.' {
				continue
			}

			columns[j][board[i][j]] = struct{}{}
		}
	}

	return columns
}

func initRows(board [][]byte) []map[byte]struct{} {
	rows := make([]map[byte]struct{}, len(board))

	for i := 0; i < len(board); i++ {
		rows[i] = make(map[byte]struct{})
		for j := 0; j < len(board[0]); j++ {
			if board[i][j] == '.' {
				continue
			}

			rows[i][board[i][j]] = struct{}{}
		}
	}

	return rows
}

func initSquares(board [][]byte) [][]map[byte]struct{} {
	squares := make([][]map[byte]struct{}, len(board))

	for squareI := 0; squareI < len(board)/3; squareI++ {
		squares[squareI] = make([]map[byte]struct{}, len(board))
		for squareJ := 0; squareJ < len(board[0])/3; squareJ++ {
			squares[squareI][squareJ] = make(map[byte]struct{})
			initSquare(board, squares[squareI][squareJ], squareI, squareJ)
		}
	}

	return squares
}

func initSquare(board [][]byte, square map[byte]struct{}, squareI int, squareJ int) {
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			k := squareI*3 + i
			l := squareJ*3 + j

			if board[k][l] == '.' {
				continue
			}

			square[board[k][l]] = struct{}{}
		}
	}
}

func backtrack(board [][]byte, columns []map[byte]struct{}, rows []map[byte]struct{}, squares [][]map[byte]struct{}, i int, j int) bool {
	if i == len(board) {
		return true
	}

	if board[i][j] != '.' {
		nextI, nextJ := getNextIndexes(board, i, j)
		return backtrack(board, columns, rows, squares, nextI, nextJ)
	}

	availableChars := []byte{'1','2','3','4','5','6','7','8','9'}
	for _, c := range availableChars {
		if !canBePlaced(c, i, j, columns, rows, squares) {
			continue
		}

		squareI, squareJ := getSquareIndexes(i, j)
		nextI, nextJ := getNextIndexes(board, i, j)

		board[i][j] = c
		columns[j][c] = struct{}{}
		rows[i][c] = struct{}{}
		squares[squareI][squareJ][c] = struct{}{}

		solved := backtrack(board, columns, rows, squares, nextI, nextJ)
		if solved {
			return true
		}

		board[i][j] = '.'
		delete(columns[j], c)
		delete(rows[i], c)
		delete(squares[squareI][squareJ], c)
	}

	return false
}

func getNextIndexes(board [][]byte, i int, j int) (int, int) {
	if j == len(board[0])-1 {
		return i + 1, 0
	} else {
		return i, j + 1
	}
}

func getSquareIndexes(i int, j int) (int, int) {
	return i / 3, j / 3
}

func canBePlaced(c byte, i int, j int, columns []map[byte]struct{}, rows []map[byte]struct{}, squares [][]map[byte]struct{}) bool {
	if _, ok := columns[j][c]; ok {
		return false
	}
	if _, ok := rows[i][c]; ok {
		return false
	}

	squareI, squareJ := getSquareIndexes(i, j)
	if _, ok := squares[squareI][squareJ][c]; ok {
		return false
	}

	return true
}