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()