递归法解决数独sudoku，附python实现代码

递归法解决数独sudoku，python实现 定义

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复 。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

算法思想

利用递归的思想，对于sudoku数组，每一个数字判断当前行、列、九宫中已经出现的数字，从未出现的数字中顺序选择一个填入空白处。如果发现某一个空格没有可填数字，则进行回溯。
初始化：
sudoku数组9x9数组，初始化为0
tmp数组1x9数组，初始化为0

代码

# -*- coding: utf-8 -*-
# @Time    : 2022/4/30 15:45
# @Author  : kunkun
# @File    : algorithm1.py
# ------------------------------
# 解决数独算法1
# 算法主要思路，递归寻找可以填入的值，找不到则回溯

import numpy as np

sudoku = np.zeros((9, 9), dtype=np.int32)


def dfs(x, y):
    if x == 9:  # 找到答案，返回True
        return 1
    if sudoku[x][y] != 0:  # 当前位置已经有值
        if y + 1 <= 8:
            return dfs(x, y + 1)
        else:
            return dfs(x + 1, 0)
    tmp = np.zeros(9, np.int32)  # 记录待用的数字
    for i in range(9):
        if sudoku[x][i] > 0:
            # print('x', sudoku[x][i])
            tmp[sudoku[x][i] - 1] = 1  # 当前行已用的数字
        if sudoku[i][y] > 0:
            # print('y', sudoku[i][y])
            tmp[sudoku[i][y] - 1] = 1  # 当前列已用的数字
    # 寻找九宫格位置
    start = x // 3
    end = y // 3
    for i in range(start * 3, start * 3 + 3):
        for j in range(end * 3, end * 3 + 3):
            if sudoku[i][j] > 0:
                # print(sudoku[i][j])
                tmp[sudoku[i][j] - 1] = 1
    # print(tmp)
    for i in range(9):
        if tmp[i] == 0:
            sudoku[x][y] = i + 1  # 填值
            # print(x, y, i + 1)
            if y + 1 <= 8:
                if dfs(x, y + 1) == 1:
                    return 1
            else:
                if dfs(x + 1, 0) == 1:
                    return 1
    # 回溯
    sudoku[x][y] = 0
    return 0


if __name__ == '__main__':
    sudoku = [[0, 0, 0, 0, 0, 0, 0, 0, 4],
              [0, 2, 8, 7, 5, 0, 0, 3, 0],
              [0, 3, 1, 0, 0, 2, 0, 0, 0],
              [6, 5, 0, 2, 3, 7, 0, 0, 0],
              [0, 0, 0, 0, 9, 0, 0, 0, 0],
              [0, 0, 0, 6, 8, 1, 0, 5, 9],
              [0, 0, 0, 9, 0, 0, 8, 6, 0],
              [0, 9, 0, 0, 2, 4, 3, 1, 0],
              [5, 0, 0, 0, 0, 0, 0, 0, 0]]
    if dfs(0, 0) == 0:
        print("No Solution")
    else:
        for i in range(9):
            print(sudoku[i])

总结

递归法实现，总体来说比较简单，唯一需要注意的就是退出递归的条件。下面会尝试几种新的方法实现解决数独的算法。