-1

私は再帰コーディングを学んでいて、自分自身のテストである 8 クイーン パズルを試しました。各ステップで競合があるかどうかを確認し、競合がある場合はバックトラックします。しかし、私のコードは時期尚早にバックトラックを停止しているようです。

まず、私は持っています：

0000
0000
0000
0000

次に、次のように変更されます。

1000
0000
0000
0000

その後、次のように変更されます。

1100
0000
0000
0000

これで、競合関数は True を返し、関数は停止します。なぜそれが呼び出さsolve_queen(grid)れないのですか：

1010
0000
0000
0000

for2 つのループに問題があると思いますが、どこで問題が発生したのsolve_queen(grid)か正確にはわかりません。

私のコードは次のとおりです。

import copy

q4_zero = [[0,0,0,0],
           [0,0,0,0],
           [0,0,0,0],
           [0,0,0,0]]


def format_failed(grid):
    if len(grid) != len(grid[0]):
        return True
    elif len(grid) < 4:
        return True
    return False

def row_conflict(grid):
    for row in grid:
        if row.count(1) > 1:
            return True
    return False 

def col_conflict(grid):
    new_grid = [[r[col] for r in grid] for col in range(len(grid[0]))]
    return row_conflict(grid)

def oblique_conflict(grid):
    i_lst = []
    j_lst = []
    row_count = len(grid)
    for i in xrange(row_count):
        if grid[i].count(1) > 0:
            j = grid[i].index(1)
            i_lst.append(i)
            j_lst.append(j)

    for k in xrange(len(i_lst)):
        for m in xrange(len(i_lst) - 1):
            if abs(i_lst[m] - i_lst[m + 1]) == abs(j_lst[m] - j_lst[m + 1]):
                return True

    return False


def conflict(grid):
    if format_failed(grid):
        return True
    elif row_conflict(grid):
        return True
    elif col_conflict(grid):
        return True
    elif oblique_conflict(grid):
        return True
    return False


def solve_queen(__grid):

    res = conflict(__grid)

    if res is True:
        return res

    grid = copy.deepcopy(__grid)
    N = len(grid)

    for i in xrange(N):
        for j in xrange(N):
            if grid[i][j] == 0:
                grid[i][j] = 1
                final_answer = solve_queen(grid)
                if final_answer is not True:
                    return final_answer

                return True

    return grid

print solve_queen(q4_zero)
4

3 に答える 3

1 
for i in xrange(N):
        for j in xrange(N):
            if grid[i][j] == 0:
                grid[i][j] = 1
                final_answer = solve_queen(grid)
                if final_answer is not True:
                    return final_answer

                return True

solve_queen(grid)次の場合に返されると仮定しますTrue（実際にそうgridです）：

1100
0000
0000
0000

だから、あなたは設定しfinal_answer = Trueます。
は満たされていないためfinal_answer is not True、この行をスキップして次の行に直接進みます。

return True

したがって、バックトラッキング ソリューションは、この行が原因で最初の失敗の後に再帰を実際に停止しています。

何をすべきか？
ヒント: 基本句を事前に定義する必要があります - 再帰が成立するとき (ヒント: n 個のクイーンを配置した後 - この場合は答えを返し
ます。解決策が間違っているとわかった場合は、それを壊さずに繰り返し続けてください。Trueすべての可能性を使い果たした場合にのみaを返す必要があります (したがって、return Trueステートメントはforループの範囲外にする必要があります)。

于 2012-07-17T10:47:50.457 に答える
1

グリッド セルをゼロに戻すことはありません。では、バックトラッキングはどのように機能するのでしょうか?

さらに、にネストされたループがありますsolve_queen()がsolve_queen()、再帰関数であると想定されています。ループを使用するか、再帰を使用してください。

その上、あなたには停止状態がありませんsolve_queen()。とは別に、いつ停止するかを通知conflict()する関数が必要です。is_solved()

if not is_solved(grid):
    return solve_queen(grid)
else return grid

ちなみに、クイーン問題は整数の配列としてより効率的に表されます。ここで、インデックスは行を表し、値は列を表します。たとえば、grid[3] は、行 4 のクイーンの関連する列を示します。

この表現を使用すると、競合のチェックがはるかに簡単になります。さらに、スペースを節約できます。これは、4 クイーンから 100 億にすると便利です。;-)

最後に、再帰とバックトラッキングについてよく読んでください。これらの概念のいずれかを実際に理解しているとは思えません。

于 2012-07-17T10:49:40.660 に答える
0

これが役立つかどうかはわかりませんが...別のデータ表現で試しましたか?

8 クイーンの問題では、8x8 グリッド全体は必要ありません。各クイーンは異なる行に配置されるため、クイーンの列を持つ 8 配列が必要です。

私は Python を知らないので、その点であなたを助けることはできませんが、データ形式を変更すると問題が解決する可能性があります。

于 2012-07-17T10:14:15.843 に答える