数独

数独_牛客题霸_牛客网

问题简述

请编写一个程序，给数独中的剩余的空格填写上数字
空格用字符'.'表示
假设给定的数独只有唯一的解法

思路

• 使用三个矩阵记录每行、每列、每块出现过的数字；开始时，需要对已经出现过的数字初始化；

• 难点1：

  • 对 board[i][j] 很容易确定他所在的行和列，但是确定所在块需要对坐标做一个转换；

  • 具体来说，假设块的标号从左往右，从上往下依次为 0~8，则对 (i,j)，其所在块的 id 为 k = 3*(i/3) + j/3；

  • 简单验证几个位置，(0,0) 在第 0 块，(8,8) 在第 8 块；(4,5) 在第 4 块；

• 难点2：

  • 确定下一个遍历位置，最直观的顺序是从左往右，从上往下；

  • 假设当前位置为 (i, j) 表示第 i 行，第 j 列；则下一个位置 (nxt_i, nxt_j) 为：

    • nxt_i = i if j != 8 else i + 1；

    • nxt_j = j + 1 if j != 8 else 0；

• 详见代码；

Python

class Solution:
    def solveSudoku(self , board):
        if not board: return []
        
        n = len(board)  # 9
        row = [[0] * (n + 1) for _ in range(n)]
        col = [[0] * (n + 1) for _ in range(n)]
        blk = [[0] * (n + 1) for _ in range(n)]
        
        def init():
            """初始化 row, clo, blk 记录出现过的数字"""
            for i in range(n):
                for j in range(n):
                    # 确定块 id
                    k = 3 * (i // 3) + j // 3
                    if (x := board[i][j]) != '.':
                        x = int(x)
                        row[i][x] = col[j][x] = blk[k][x] = 1
        
        def dfs(i, j):
            # 顺利达到最后一行，说明每个位置都满足要求
            if i == n: return True
            
            # 确定下一个遍历位置
            nxt_i = i if j != (n - 1) else i + 1
            nxt_j = j + 1 if j != (n - 1) else 0
            
            # 如果当前位置不需要填，直接到下一个位置
            if board[i][j] != '.':
                return dfs(nxt_i, nxt_j)
            
            # 对当前位置遍历每个可用数字
            k = 3 * (i // 3) + j // 3  # 块 id
            for x in range(1, 10):
                # 不可用，跳过
                if row[i][x] or col[j][x] or blk[k][x]:
                    continue
                # 可用，DFS回溯
                row[i][x] = col[j][x] = blk[k][x] = 1
                board[i][j] = str(x)
                if dfs(nxt_i, nxt_j):
                    return True
                board[i][j] = '.'
                row[i][x] = col[j][x] = blk[k][x] = 0
            
            return False
        
        init()
        dfs(0, 0)
        return board