Pythonのバックトラッキング（クイーンズチェックボード）

Question

最終的に私の頭に苦労して何時間もして、最終的にバックトラックの仕組みを理解しました。私はまだ秘密が理解できるように残っていると思いますが。とにかく、私はチェックボードで4クイーン問題を作成しようとしています。実際に私は自分自身に空のチェックボード（実際には4x4）を与えているので、それらのクイーンズが自分自身を攻撃しない4つの場所を見つける必要があります。クイーンは、それが属している行、列と対角線を攻撃する。 ここに私がこれまで行ってきたことがあります（有効なfuncはまだ完成していませんが、それは問題ではありません。

def findNextCell(grid,i,j): 

    for index in range(i,4): 
     for jindex in range(j,4): 
      return index, jindex 

    for index in range(0,4): 
     for jindex in range(0,4): 
      if grid[index][jindex] == 0: 
       return index, jindex 

    return -1,-1 


def isValid(grid, index, jindex, queen): 

    rowOk = all([queen != grid[index][x] for x in range(4)]) 
    if rowOk: 
     columnOk = all([queen != grid[x][jindex] for x in range(4)]) 
     if columnOk: 
      return True 
    return False 

def queenSolve(grid, i=0, j=0, num_queens = 0): 

    i, j = findNextCell(grid, i, j) 
    print grid 
    if num_queens == 4: 
     return True 
    if isValid(grid, i, j, 1): 
     grid[i][j]=1 
     num_queens += 1 
     if (queenSolve(grid, i, j, num_queens)): 
      return True 
     grid[i][j]=0 
    return False 

input = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] 

print queenSolve(input) 

Answer 1

私が見る最初の問題は、このルーチンの最初のネストされたループである：

def findNextCell(grid,i,j): 

    for index in range(i,4): 
     for jindex in range(j,4): 
      return index, jindex 

    for index in range(0,4): 
     for jindex in range(0,4): 
      if grid[index][jindex] == 0: 
       return index, jindex 

    return -1,-1 

これは一掃やったことがなかったいくつかの初期のテストコードのように見える：

for index in range(i,4): 
     for jindex in range(j,4): 
      return index, jindex 

しかし、残念ながら、findNextCell()には常にiとjが返され、それ以上のものは返されません。

これは女王の数を増大さ

num_queens += 1 
if (queenSolve(grid, i, j, num_queens)): 

、成功するか失敗：

>>> findNextCell(0, 1, 2) 
(1, 2) 
>>> findNextCell(0, 3, 2) 
(3, 2) 
>>> findNextCell(0, 1, 1) 
(1, 1) 
>>> 

私が見る次の問題はラインのこのペアです！

if (queenSolve(grid, i, j, num_queens + 1)): 

再帰に女王の数を増やすが、これが失敗した場合、現在の数には影響を与えないことです。代わりに、あなたはおそらく1行をしたいです。

私が見る第3の問題は、これがループではないということです。

i, j = findNextCell(grid, i, j) 
... 
if isValid(grid, i, j, 1): 
    grid[i][j]=1 
    num_queens += 1 
    if (queenSolve(grid, i, j, num_queens)): 
     return True 
    grid[i][j]=0 

あなたは、findNextCell()リターンがマイナス、有効なスペースを使い果たすまで、すべての有効な空間で、現在の女王を配置しようとしなければなりません再帰が成功するまであなたは現在の女王のために1つの場所を試してから、あきらめます。この問題は現在のクイーンでは反復的であり、後続のクイーンでは再帰的です。