n クイーン アルゴリズムとも呼ばれる8 クイーン パズルを解こうとしています。
私の関数は、NxN ボードに N 個のクイーンを配置する正当な方法がいくつあるかをカウントする必要があります。
私はほとんどそれを手に入れましたが、それを機能させるためにいくつかの醜いパッチを適用する必要がありました. 直してもらえますか？
私がしたことの簡単な説明: NxN テーブルに N 個のクイーンを設定する合法的な方法がいくつあるかを調べようとして、(N-1)xN ケースで再帰を使用して解決しようとしていました (最初の列を削除) 事実については同じ列に 2 つのクイーンを配置することはできません。リストの長さ N を使用します。各セルは列を表し、各列にはクイーンが設定されている行番号を設定します。
例えば、
[0, 4, 7, 5, 2, 6, 1, 3]
という意味です：
- 列 0 – 行 0 に配置されたクイーン
- 列 1 – 行 4 に配置されたクイーン
- 列 2 – 行 7 に配置されたクイーン
- 列 3 – 行 5 に配置されたクイーン
- 列 4 – 行 2 に配置されたクイーン
- 列 5 – 行 6 に配置されたクイーン
- 列 6 – 行 1 に配置されたクイーン
- 列 7 – 行 3 に配置されたクイーン
私を悩ませているのは、違法なクイーンの配置を省略する方法がわからないことです. それを機能させるために、私は という名前のグローバル変数を使用し、sum再帰が合法である完全に配置されたクイーンの配置に達した場合にのみインクリメントします。
def is_available(n, table, column, N):
return not any(t in (n, n - i, n + i)
for t, i in zip(table, range(column, 0, -1)))
def queens_sum(N):
table = [0]*N
global sum
sum = 0
solve(N, table, 0, len(table))
return sum
def solve(N, table, column, end):
global sum
if column == end:
sum += 1
return None
for n in range(N):
# if no other queen can attack here, place a queen in this row
if is_available(n, table, column, N):
table[column] = n
# Omit the current column at the start
solve(N, table, column+1, end)
#else: we can't place queen here, we should abort this direction
# do nothing
N = 8私が得る..したがって、sum = 92それが機能することはわかっていますが、このグローバルカウンターは避けたいです。
手伝ってくれますか？