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

概述深度搜索+命令模式 解数独

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

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,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,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,value):        cmd = Command(self.table,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 x,value in zip(range(9),line.strip().split(' ')):                if value != '?':                    self.push(y,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,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

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的深度搜索+命令模式 解数独全部内容，希望文章能够帮你解决深度搜索+命令模式 解数独所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。