# 【基础篇 - Day 24】 2020-11-24 - 37. 解数独
# 题目描述
# 入选理由
hashtable 如何用于辅助简化状态获取
# 题目描述
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
提示：
给定的数独序列只包含数字 1-9 和字符 '.' 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sudoku-solver 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处
# 我的回答
https://github.com/leetcode-pp/91alg-2/issues/50#issuecomment-732646188
# 解法一
# 时空复杂度
时间复杂度：O(n^2) n 是 81? 算不来
空间复杂度: O(3*81)
var solveSudoku = function (board) {
let col = {}
let row = {}
let square = {}
for (let i = 0; i < 9; i++) {
col[i] = {}
row[i] = {}
square[i] = {}
}
function isVaildNum(i, j, num) {
const squareIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3)
if (row[i][num]) return false
if (col[j][num]) return false
if (square[squareIndex][num]) return false
return true
}
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[i].length; j++) {
const num = board[i][j]
if (num === '.') continue
const squareIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3)
row[i][num] = col[j][num] = square[squareIndex][num] = true
}
}
function recursion(m, n) {
if (m === 9 && n === 0) return true
let newRow = n + 1 === 9 ? m + 1 : m
let newCol = (n + 1) % 9
if (board[m][n] !== '.') return recursion(newRow, newCol)
for (let i = 1; i <= 9; i++) {
let newVal = String(i)
if (isVaildNum(m, n, newVal)) {
board[m][n] = newVal
const squareIndex = Math.floor(m / 3) * 3 + Math.floor(n / 3)
row[m][newVal] = col[n][newVal] = square[squareIndex][newVal] = true
if (recursion(newRow, newCol)) return true
board[m][n] = '.'
row[m][newVal] = col[n][newVal] = square[squareIndex][newVal] = false
}
}
return false
}
recursion(0, 0)
return board
};