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

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家，仅供参考

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

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,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 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

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!