解数独问题的算法分析与代码实现

题目描述

编写程序解决数独问题。遵循数独规则：每一行、每一列和每个3x3宫内数字1-9各出现一次。空白格用'.'表示。

算法分析

算法寻找9x9格内未填充数字，尝试填写不冲突数字，若后续格子填充冲突，则回溯。数据结构包括col_used, row_used和box_used记录已填充数字。遍历数独记录已填数字，递归填充直到81个格子完成。

代码示例

def solveSudoku(board):
    row_used = [[] for i in range(9)]
    col_used = [[] for i in range(9)]
    box_used = [[[], [], []] for i in range(3)]
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] in "123456789":
                row_used[i].append(board[i][j])
                col_used[j].append(board[i][j])
                box_used[i // 3][j // 3].append(board[i][j])
    def dfs(board, i=0, j=0):
        if j == 9:
            i, j = i+1, 0
        if i == 9:
            return True
        if board[i][j] == ".":
            for num in ("123456789"):
                if num not in row_used[i] and num not in col_used[j] and num not in box_used[i // 3][j // 3]:
                    row_used[i].append(num)
                    col_used[j].append(num)
                    box_used[i // 3][j // 3].append(num)
                    board[i][j] = num
                    if dfs(board, i, j+1):
                        return True
                    row_used[i].pop()
                    col_used[j].pop()
                    box_used[i // 3][j // 3].pop()
                    board[i][j] = "."
            return False
        else:
            return dfs(board, i, j+1)
    dfs(board)
    return board
  

学习资源

提供测试开发试听课链接及提取码，强调学习和实践的重要性，并鼓励长期努力。

内推信息

内推字节跳动测试开发职位，提供招聘QQ群。