【杂记】数独求解

一、背景

晚上睡前准备刷个朋友圈睡觉，突然在朋友圈看到有个小姑娘发了这么一张图：

突然想起来最近刷的题，有一道题正好是“有效的数独”，简单思索一下，再加上一点回溯 + 剪枝，应该就可以程序上解决这个问题了，于是打开刚关上的电脑，开始coding

二、解题思路

思考的解题思路有两种：

暴力遍历所有的可能性，然后检索是否是有效的数独，如果是无效的，从后往前的修改填入的元素，知道遍历完所有可能性或者找到有效解。但是这种方式效率感觉过低，不太想尝试

回溯 + 剪枝，在填入数字前，先判断在当前位置填入当前数字后，是否是有效的数独，如果是无效的，则继续判断下个数字，依次类推

因为借用了之前的代码， 所以这次写代码 + 调试代码，用了大概10分钟左右搞定了

感叹一下，平时多刷刷算法题，还是有好处的，思路开扩很多

三、代码实现

#coding=utf-8
import time
import random
class Solution:
    def __init__(self, shudu_array):
        # 要解的原始数独
        self.shudu_array = shudu_array
        # 用于记录当前每行、每列、每个小方格已填入的数组，用于判断是否是有效的数独
        self.rec = {'row' : {0 : [], 1 : [], 2 : [], 3 : [], 4 : [], 5 : [], 6 : [], 7 : [], 8 : [], 9 : []},
              'column' : {0 : [], 1 : [], 2 : [], 3 : [], 4 : [], 5 : [], 6 : [], 7 : [], 8 : [], 9 : []},
              'rect' : {0 : [], 1 : [], 2 : [], 3 : [], 4 : [], 5 : [], 6 : [], 7 : [], 8 : [], 9 : []}}
        # 根据原始数独数组，初始化记录表
        for row in range(0, 9):
            for column in range(0, 9):
                rect_num = row // 3 * 3 + column // 3
                if shudu_array[row][column] == 0:
                    continue
                curr_num = shudu_array[row][column]                self.rec['row'][row].append(curr_num)
                self.rec['column'][column].append(curr_num)
                self.rec['rect'][rect_num].append(curr_num)
    # 判断是否是有效的数独
    def is_valid(self, row, column, rect_num):
        rect_num = row // 3 * 3 + column // 3
        if self.shudu_array[row][column] == 0:
            return False
        curr_num = self.shudu_array[row][column]        if curr_num in self.rec['row'][row]:
            return False
        elif curr_num in self.rec['column'][column]:
            return False
        elif curr_num in self.rec['rect'][rect_num]:
            return False
        return True
 1/2    1 2 下一页 尾页