【Python】python深度搜索+命令模式 解数独

python深度搜索+命令模式 解数独：

1. 先按照“行、列、组”三个约束来限定单元格的可选值，如果可选值只剩下一个就确定，直到找不到只有一个值的单元格。
2. 检查是否出现了某个单元格可选值为空，表示猜测的值不正确，就尝试下一个可选值。
3. 采用了命令模式（Command Design Pattern）记录每次变更，如果搜索失败就调用undo回滚。

python深度搜索+命令模式 解数独代码片段

1. [代码]解数独

def flatten(nested_list):
    for value in nested_list:
        if isinstance(value, list):
            for nested_value in flatten(value):
                yield nested_value
        else:
            yield value
 Python资源分享qun 784758214 ,内有安装包，PDF，学习视频，这里是Python学习者的聚集地，零基础，进阶，都欢迎
def some(nested_list, fn):
    for value in flatten(nested_list):
        if fn(value):
            return value
    return None
 
class Cell(set):
    def __init__(self, y, x):
        self.marked = False
        self.y = y
        self.x = x
        self.update(range(1, 10))
 
    def is_explicit(self):
        return len(self) == 1
 
    def mark(self, value):
        self.marked = True
        self.clear()
        self.add(value)
 
    def set(self, values):
        self.marked = False
        self.clear()
        self.update(values)
 
    def value(self):
        return next(iter(self))
 
    def __str__(self):
        size = len(self)
        if size == 0:
            return 'X'
        elif size == 1:
            return str(self.value())
        else:
            return '?'
 
class Table:
    def __init__(self):
        self.values = [[Cell(y, x) for x in xrange(9)] for y in xrange(9)]
 
    def is_valid(self):
        return all(flatten(self.values))
 
    def is_finished(self):
        return all([e.is_explicit() for e in flatten(self.values)])
 
    def first_implicit(self):
        return some(self.values, lambda e: not e.is_explicit())
 
    def first_explicit(self):
        return some(self.values, lambda e: not e.marked and e.is_explicit())
 
    def get_neighbors(self, y, x):
        neighbors = []
        # horizontal
        neighbors.extend([self.values[y][c] for c in xrange(9) if c != x and not self.values[y][c].marked])
        # vertical
        neighbors.extend([self.values[r][x] for r in xrange(9) if r != y and not self.values[r][x].marked])
        # box
        start_x = x / 3 * 3
        start_y = y / 3 * 3
        for r in range(start_y, start_y + 3):
            for c in range(start_x, start_x + 3):
                if r != y and c != x and not self.values[r][c].marked:
                    neighbors.append(self.values[r][c])
        return neighbors
 
    def __str__(self):
        return '\n'.join([' '.join(str(c) for c in r) for r in self.values])
 
class Command:
    def __init__(self, table, y, x, value):
        self.table = table
        self.y = y
        self.x = x
        self.value = value
        self.cell = table.values[y][x].copy()
        self.queue = []
        self.executed = False
 
    def redo(self):
        if self.executed:
            return
        else:
            self.executed = True
        self.queue = []
        for cell in self.table.get_neighbors(self.y, self.x):
            if self.value in cell:
                cell.remove(self.value)
                self.queue.append(cell)
        self.table.values[self.y][self.x].mark(self.value)
 
    def undo(self):
        if self.executed:
            self.executed = False
        else:
            return
        for cell in self.queue:
            cell.add(self.value)
        self.table.values[self.y][self.x].set(self.cell)
 
class Sudoku:
    def __init__(self):
        self.table = Table()
        self.queue = []
 
    def push(self, y, x, value):
        cmd = Command(self.table, y, x, value)
        cmd.redo()
        self.queue.append(cmd)
 
    def pop(self):
        cmd = self.queue.pop()
        cmd.undo()
 
    def load(self, matrix):
        for y, line in zip(range(9), matrix.strip().split('\n')):
            for
2000
x, value in zip(range(9), line.strip().split(' ')):
                if value != '?':
                    self.push(y, x, int(value))
        self.derive()
 
    def derive(self):
        count = 0
        while True:
            cell = self.table.first_explicit()
            if cell:
                self.push(cell.y, cell.x, cell.value())
                count += 1
            else:
                return count
 
    def revert(self, deep):
        for i in xrange(-1, deep):
            self.pop()
 
    def bfs(self):
        cell = self.table.first_implicit()
        for value in cell.copy():
            self.push(cell.y, cell.x, value)
            deep = self.derive()
            if self.table.is_finished():
                return True
            elif not self.table.is_valid():
                self.revert(deep)
            else:
                result = self.bfs()
                if result:
                    return True
                else:
                    self.revert(deep)
        return False
 
    def __str__(self):
        return str(self.table)
 
puzzle = '''
? ? ? ? ? 7 ? 8 2
5 ? 7 ? ? ? 4 ? ?
? ? ? 2 5 ? ? ? ?
8 ? 9 1 7 ? ? ? ?
? 7 ? 5 ? 3 6 ? 8
? 5 3 ? ? ? ? 9 1
2 ? ? ? ? ? 3 ? 6
? ? ? 3 ? 2 ? ? ?
? 8 5 ? 6 ? ? ? ?
'''
sudoku = Sudoku()
sudoku.load(puzzle)
sudoku.bfs()
print sudoku

9 6 1 4 3 7 5 8 2
5 2 7 6 1 8 4 3 9
4 3 8 2 5 9 1 6 7
8 4 9 1 7 6 2 5 3
1 7 2 5 9 3 6 4 8
6 5 3 8 2 4 7 9 1
2 1 4 9 8 5 3 7 6
7 9 6 3 4 2 8 1 5
3 8 5 7 6 1 9 2 4
Python资源分享qun 784758214 ,内有安装包，PDF，学习视频，这里是Python学习者的聚集地，零基础，进阶，都欢迎