N-Queens II
クイーンは、どれだけ離れていても、同じ行、同じ列、および2本の対角線上にあるすべてのマスを攻撃します。整数 n が与えられたとき、どの2つのクイーンも互いに攻撃しないように、n × n の盤面に n 個のクイーンを配置する方法の数を返してください。
1つでもマスが異なる盤面は、鏡像も含め、それぞれ別の配置として数えます。
関数
- ninteger
- 盤面のサイズとクイーンの数
- 戻り値integer
- 互いに攻撃し合わないようにクイーンを配置する方法の数
制約
1 ≤ n ≤ 12n = 12の答えは14,200なので、32ビット整数に収まります。
例
- 入力
- n = 4
- 出力
- 2
- 説明
- 各行のクイーンの列を上から下へ書くと、盤面は
1, 3, 0, 2と2, 0, 3, 1です。これは鏡像ですが、2つとして数えます。それ以外の配置では、同じ列または対角線上に2つのクイーンが置かれます。
- 入力
- n = 3
- 出力
- 0
- 説明
- 上段の隅にクイーンを置くと、中段に安全なマスが1つ残り、その後、下段には安全なマスがなくなります。上段の中央にクイーンを置くと、中段全体が攻撃されます。
発展問題
盤面を回転または反転しても同一にならない盤面だけを数えられますか？ n = 8 の場合、92 個の盤面はそのような 12 個のグループに分類されます。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
同じ行にいる2つのクイーンは互いに攻撃し合うため、各行にはクイーンがちょうど1つずつ置かれます。それがわかったら、あとは何を選べばよいでしょうか？
盤面を上から一行ずつ埋めていきます。新しいクイーンが攻撃されている場合は、下に何を追加しても解決できないため、その時点でその盤面を破棄します。盤面全体を見ずにマスを判定するには、すでにクイーンが置かれている列と対角線を覚えておきます。一方の対角線方向では、どのマスでも
row + colが同じになり、もう一方ではrow - colが同じになります。place(row)を記述します。これは、ここから完成できる盤面の数を返します。row == nの場合は 1 を返します。それ以外の場合は、列、row + cの対角線、row - cの対角線がすべて空いている列cをすべて試します。3つに印を付け、place(row + 1)を累計に加えてから、印を消します。答えはplace(0)です。
解説
同じ行にクイーンが2つあると必ず互いに攻撃するため、盤面は各行につき1列、つまりn^n通りとなり、n = 12では約8.9 × 10^12通りです。代わりに行ごとに盤面を作り、クイーンが攻撃される状態になった時点で部分的な盤面を破棄し、使用済みの列と対角線に印を付ければ、マスの確認に必要な検索は3回で済みます。
各行にクイーンを1つずつ配置して、すべての配置を試す
正しいが、最大のテストでは終わらない
考え方
配置をリスト cols として表し、各行のクイーンの列を記録して、走行距離計のようにすべての n^n 個のリストを順に調べます。行 i < j のクイーンは、cols[i] == cols[j] または |cols[i] - cols[j]| == j - i のとき互いに攻撃します。対角線上では、行が1つ進むごとに列も1つ移動するためです。各リストは1回ずつ調べられるので、見落とされる盤面も、重複して数えられる盤面もありません。
途中で処理を打ち切ることはありません。最初の2行で衝突があっても、n^(n-2) 個のリストが残ります。n = 8 の場合、92個の盤面に対して16,777,216個のリストを調べます。n = 12 の場合は 8.9 × 10^12 個で、1回あたり1ナノ秒として約2.5時間かかります。
アルゴリズム
colsのすべての値を 0 にして始めます。- 行のペア
i < jのどれについても、cols[i] == cols[j]または|cols[i] - cols[j]| == j - iが成り立たない場合、カウントに 1 を加えます。 - オドメーターのように進めます。最後の行から上に向かって、
n-1になっている各要素を 0 にリセットし、その後、n-1未満である最初の要素に 1 を加えます。 - すべての要素が
n-1だった場合、停止してカウントを返します。
def totalNQueens(n):
def is_valid(cols):
# cols[r] is the column of the queen in row r, so rows never clash.
for i in range(n):
for j in range(i + 1, n):
if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
return False
return True
cols = [0] * n
count = 0
while True:
if is_valid(cols):
count += 1
# Move to the next placement, like an odometer with n digits in base n.
row = n - 1
while row >= 0 and cols[row] == n - 1:
cols[row] = 0
row -= 1
if row < 0:
return count
cols[row] += 1列と対角線の集合を使ったバックトラッキング
考え方
クイーンを行ごとに配置し、置くたびにそれぞれを確認します。下の行をどれだけ埋めても、攻撃されているクイーンを救うことはできないため、そのマスは飛ばします。安全なクイーンを置いたら次の行へ再帰し、呼び出しから戻るときに取り除きます。行 n に到達すると、盤面を1つ数えます。
マス (row, c) を攻撃できるのは3本の線だけです。列、その / 対角線（row + c が一定）、そして \ 対角線（row - c が一定。0からインデックスを付けるために n-1 を加えます）です。フラグ配列 cols、diag、anti を使うと、安全性の判定を3回の参照で行えます。それぞれの線にはクイーンを最大1つしか置けないため、戻るときにフラグをクリアすれば、配列は正確に元の状態に戻ります。
行 k で選べる列は最大 n - k 個なので、探索量は O(n!) で抑えられ、空間計算量は O(n) です。
アルゴリズム
- サイズが
nのフラグ配列colsと、サイズが2n-1のdiagおよびantiを作成し、すべてオフにします。 place(row):row == nの場合、1を返します。- 各列
cについて、cols[c]、diag[row + c]、またはanti[row - c + n - 1]がオンなら、その列をスキップします。 - そうでなければ、3つのフラグをオンにし、
place(row + 1)を合計に加えてから、フラグをオフにします。 - 合計を返します。答えは
place(0)です。
def totalNQueens(n):
cols = [False] * n # cols[c]: column c holds a queen
diag = [False] * (2 * n - 1) # diag[r + c]: that / diagonal holds a queen
anti = [False] * (2 * n - 1) # anti[r - c + n - 1]: that \ diagonal holds a queen
def place(row):
if row == n:
return 1 # a queen in every row: one complete board
count = 0
for c in range(n):
if cols[c] or diag[row + c] or anti[row - c + n - 1]:
continue # attacked: three lookups, no scan of the board
cols[c] = diag[row + c] = anti[row - c + n - 1] = True
count += place(row + 1)
cols[c] = diag[row + c] = anti[row - c + n - 1] = False # take it back
return count
return place(0)ビットマスクを使ったバックトラッキング
考え方
フラグを使った探索では、各行のn個すべての列を引き続き調べますが、ビットマスクなら空いている列へ直接進めます。ビットcは、埋めている行の列cを表します。colsには使用済みの列が、leftとrightにはそれぞれの対角線上で攻撃されるマスが格納されます。すると、fullを下位nビットとして、free = ~(cols | left | right) & fullとなり、free & -freeは最も下位にある空きマスです。1行下では、列は使用済みのままで、各対角線からの攻撃位置は1列分ずれます。
n = 4で最初のクイーンをbit = 0010に置くと、行1ではfree = 1000となります。他の列を調べずに、列3が見つかります。n = 12では、マスを10,103,868回調べる代わりに、ループの反復を856,188回行います。Rコードでは再帰を使わず、一度に盤面の部分状態を1行分まとめて生成します。
アルゴリズム
full = (1 << n) - 1を設定します。count(cols, left, right)：cols == fullの場合は、1を返します。free = ~(cols | left | right) & fullを計算します。freeが0でない間、bit = free & -freeを取り出し、freeから取り除いて、count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)を合計に加えます。- 合計を返します。答えは
count(0, 0, 0)です。
def totalNQueens(n):
full = (1 << n) - 1 # bit c stands for column c of the current row
def count(cols, left, right):
# cols: columns taken. left, right: squares of this row hit along a diagonal.
if cols == full:
return 1 # every column used: n queens placed
total = 0
free = full & ~(cols | left | right)
while free:
bit = free & -free # the lowest free square
free -= bit
# Moving down a row shifts each diagonal attack one column over.
total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
return total
return count(0, 0, 0)
落とし穴と境界ケース
n-1を加えずに、row - cでantiをインデックス指定する。Javaでは例外が発生し、Cでは配列の範囲外を読み取り、Pythonのanti[-2]は別の対角線のフラグを何事もなく読み取る。- 対角線用配列のサイズを
2n-1ではなくnにする。row + cは2n-2に達する。 - 再帰呼び出しの後にフラグをクリアしない。後続の分岐で、すでに取り除かれたクイーンがあるものとして扱われ、カウントが減る。
freeに& fullを含めない。~xは列n-1より上のビットを立てるため、ループは盤面外のマスを選ぶ。PythonやRubyではfreeが負の値になり、ループが終わらない。
よくある質問3
N-Queens II の時間計算量はどれくらいですか？
バックトラッキングの計算量は O(n!) で上限が定まります。最初の行には n 個の選択肢があり、次の行には最大で n-1 個、以降も同様です。枝刈りによって実際の処理量は大幅に減り、n = 12 の場合、部分的な盤面は 856,189 個です。空間計算量は O(n) です。
N-QueensとN-Queens IIの違いは何ですか？
N-Queensはテキストの行で描かれたすべての盤面を返します。N-Queens IIはその数だけを返します。探索方法は同じですが、数を数えるだけなら盤面を保存しないため、ビットマスク版に適しています。
対称性を利用してN-Queens IIを高速化できますか？
盤面を左右反転すると別の有効な盤面になるため、最初のクイーンが列 0 から n/2 - 1 にある盤面の数を数えて、それを2倍します。n が奇数の場合は、最初のクイーンが中央の列にある盤面を一度だけ加えます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def totalNQueens(n):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
n = 4
期待される出力
2