2

私の数独ソルバーは、正しいものを返すことを除いて、本来あるべきことを正確に実行します。返される直前に何をすべきか (正しく解決されたグリッド) を出力しますが、その後は少し実行を続けているようで、None を返します。何が起こっているのかわかりません。

グリッドはリストのリストです。check_sudoku は、グリッドが有効 (解決されているかどうか) である場合に True を返し、それ以外の場合は False を返すと仮定します。

def solve_sudoku(grid, row=0, col=0):
    "Searches for valid numbers to put in blank cells until puzzle is solved."
    # Sanity check
    if not check_sudoku(grid): 
        return None
    # Sudoku is solved
    if row > 8: 
        return grid
    # not a blank, try next cell
    elif grid[row][col] != 0:
        next_cell(grid, row, col)
    else:
        # try every number from 1-9 for current cell until one is valid
        for n in range(1, 10):
            grid[row][col] = n
            if check_sudoku(grid):
                next_cell(grid, row, col)
        else:
            # Sudoku is unsolvable at this point, clear cell and backtrack
            grid[row][col] = 0
            return

def next_cell(grid, row, col):
    "Increments column if column is < 8 otherwise increments row"
    return solve_sudoku(grid, row, col+1) if col < 8 else solve_sudoku(grid, row+1, 0)
4

2 に答える 2

3

再帰を呼び出しnext_cellていますが、その値を返すことはありません。

于 2012-07-14T18:38:43.397 に答える
2

これが実際に何か有用なものを返すことは決してないように思えます。あなたの に初めて入るときsolve_sudoku、グリッドが解決されているかどうかを確認し、解決されている場合はそれを返します。その後、一連の再帰を開始し、最終的には関数の終わりに向かって戻ってきて、None を返します。何があっても、常に None を返しています。grid最終的に得られるのは、最初に渡した変更された引数だけです。

def solve_sudoku(grid, row=0, col=0):
    # possible return at the first entry point
    if not check_sudoku(grid): 
        return None

    # only time you would ever NOT get None
    if row > 8: 
        return grid

    ...recurse...

    # come back out when the stack unwinds,
    # and there is no return value other than None

私が推測しているのは、途中で値を出力していて、それが発生した瞬間に解決されたグリッドが適切に表示されていることですが、それが完了したときに関数が適切に完全にブレークアウトするように設定されていません。ある程度の範囲を使い果たすまでループし続け、余分な作業がたくさん表示されます。

重要なことは、再帰呼び出しの戻り値を確認することです。解決されていない場合、または解決されている場合は None を返しますgrid。現状では、呼び出しスコープでの再帰の結果を気にすることはありません。

あなたの特定のコードに関するすべての詳細を持っているわけではないので、ここに簡単な等価物があります:

def solver(aList):
    if aList[0] == 10:
        print "SOLVED!"
        return None

    print "NOT SOLVED..."
    return next(aList)

def next(aList):
    # do some stuff
    # check some stuff
    aList[0] += 1
    return solver(aList)


if __name__ == "__main__":
    data = [0]
    solver(data)
    print data

への間接的な再帰呼び出しでchecker() -> solver()は、その値がチェーンのずっと上に返されることに注意してください。この場合None、解決された手段を意味し、それ以外の場合は再帰を続ける必要があります。再帰スタックのある時点で、ソリューションが解決されることがわかっています。そのことをすぐにトップに伝える必要があります。

通信は次のようになります。

aList == [0]
solver(aList)
  next(...)
    next(...)
      next(...)
        next(...) 
          #SOLVED
        <- next(...)
      <- next(...)
    <- next(...)
  <- next(...)
<-solver(aList)
aList == [10]

そして、私の単純な例に適用すると、あなたのバージョンは次のようになります。

aList == [0]
solver(aList)
  next(...)
    next(...)
      # SOLVED
      next(...)
        next(...) 
          ...
        <- next(...)
      <- next(...)
    <- next(...)
  <- next(...)
<-solver(aList)
aList == [10]
于 2012-07-14T19:14:47.147 に答える