Python：递归问题

Question

我正在尝试制作一个可以非常快速地解出棋盘的数独解算器。目前，我的求解器在简单的板上工作，但永远不会在较硬的板上终止。我相信这与我的递归有关，因为简易板不需要递归而硬板需要。感谢任何帮助。

import sys

def rowno(i):
    return i // 9

def colno(i):
    return i % 9

def boxno(i):
    return (i // 9 // 3 )*3 + (i // 3) % 3

def isNeighbor(i, j):
    if rowno(i) == rowno(j) or colno(i) == colno(j) or boxno(i) == boxno(j):
        return True
    else:
        return False

def getFileName():
    if sys.platform == "win32":
            filename = input("Filename? ")
    else:
            filename = sys.argv[-1]
    return filename


solutionlist = []

class Board(object):
    def __init__(self, puzzle):
        self.puzzle = puzzle
        self.board = [Cell(int(value), idx) for idx, value in     enumerate(puzzle)]
        self.change = False

    def printAll(self):
        print [cell.candidates for cell in self.board] 
        #return str(" ")

    def update(self):
        self.change = False
        l = [cell for cell in self.board if len(cell.candidates) == 1]
        for i in l:
            for j in xrange(81):
                if isNeighbor(i.dex, j) and i.dex != j:
                    old = self.board[j].candidates
                    self.board[j].delCandidate(i.value)
                    if len(old) != len(self.board[j].candidates):
                        self.change = True

    def toString(self):
        str1 = ''.join(str(e.value) for e in self.board)
        return str1


    def solved(self):
        for cell in self.board:
            if len(cell.candidates) != 1:
                return False
        return True

    def solve(self):
        self.change = True
        while self.change == True:
            self.update()
        if self.solved():
            solutionlist.append(self.board)
            return
        l = [cell for cell in self.board if len(cell.candidates) > 1]
        for i in l:
            for j in i.candidates:
                newBoard = Board(self.toString())
                curLen = 12
                curCell = -1
                for u in l:
                    if len(u.candidates)<curLen:
                        curLen=len(u.candidates)
                        curCell = u.dex
                for c in newBoard.board[curCell].candidates:
                    newBoard.board[curCell].candidates = [int(c)]
                    newBoard.board[curCell].value = int(c)
                    newBoard.solve()
        return



    def __repr__(self):
        l = [cell.value for cell in self.board] 
        return str(l)


class Cell(object):
    def __init__(self, value, dex):
        self.value = value
        self.dex = dex
        if value == 0:
            self.candidates = [1,2,3,4,5,6,7,8,9]
        else:
            self.candidates = [int(value)]

    def __str__(self):
        return str(self.value)

    def delCandidate(self, value):
        # deletes value from candidate list
        #return self.candidate.remove(value);
        self.candidates = [x for x in self.candidates if x != value]
        if len(self.candidates) == 1:
            self.value = self.candidates[0]
easy =     "700583006006001405052006083300200958500078060648010300060802500003150072215600030"
twosol = "000805200800000401705040009000100702040000000006430000030900000010006080000000000"
hard = "040090008000000070060000120030020000005839060080600700050170600000043000003000200"

#easy solution: 794583216836721495152496783371264958529378164648915327967832541483159672215647839

b = Board(hard)
print b

b.solve()
print "end of the line"
for i in solutionlist:
    print [cell.value for cell in i]
    print "\n"

Answer 1

一个主要问题是 solve 方法中的 for i in l: 行。因为你是递归的，所以你只需要填写一个单元格——递归会处理剩下的事情。因此，不用 for i in l:，只需在最佳候选单元格 (curCell) 上递归：

    l = [cell for cell in self.board if len(cell.candidates) > 1]
    if len(l) > 0:
        newBoard = Board(self.toString())
        curLen = 12
        curCell = -1
        for u in l:
            if len(u.candidates)<curLen:
                curLen=len(u.candidates)
                curCell = u.dex
        for c in newBoard.board[curCell].candidates:
            newBoard.board[curCell].candidates = [int(c)]
            newBoard.board[curCell].value = int(c)
            newBoard.solve()

Python：递归问题

Python: Recursion problems

python

recursion

sudoku