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

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

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

1.先按照“行、列、组”三个约束来限定单元格的可选值，如果可选值只剩下一个就确定，直到找不到只有一个值的单元格。
2.检查是否出现了某个单元格可选值为空，表示猜测的值不正确，就尝试下一个可选值。
3.采用了命令模式（CommandDesignPattern）记录每次变更，如果搜索失败就调用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 valuedef some(nested_list, fn):    for value in flatten(nested_list):        if fn(value):            return value    return Noneclass 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 2000x, 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 25 ? 7 ? ? ? 4 ? ?? ? ? 2 5 ? ? ? ?8 ? 9 1 7 ? ? ? ?? 7 ? 5 ? 3 6 ? 8? 5 3 ? ? ? ? 9 12 ? ? ? ? ? 3 ? 6? ? ? 3 ? 2 ? ? ?? 8 5 ? 6 ? ? ? ?'''sudoku = Sudoku()sudoku.load(puzzle)sudoku.bfs()print sudoku

2.www.iplaypy.com python教程

9 6 1 4 3 7 5 8 25 2 7 6 1 8 4 3 94 3 8 2 5 9 1 6 78 4 9 1 7 6 2 5 31 7 2 5 9 3 6 4 86 5 3 8 2 4 7 9 12 1 4 9 8 5 3 7 67 9 6 3 4 2 8 1 53 8 5 7 6 1 9 2 4

编橙之家文章，