N-Queens II
チェス盤上のクイーンは、どれだけ離れていても、同じ行、同じ列、および両方の対角線上にあるすべてのマスを攻撃します。整数 n が与えられます。互いに攻撃し合わないように、n × n の盤上に n 個のクイーンを置く方法の数を返してください。
一方ではあるマスにクイーンがあり、もう一方ではそのマスが空いている場合、2つの方法は異なります。そのため、盤とその鏡像は見た目が同じでも、別々の方法として数えます。
関数
- ninteger
- 盤面の大きさとクイーンの数
- 戻り値integer
- 互いに攻撃し合わないようにクイーンを配置する方法の数
制約
1 ≤ n ≤ 12n = 12の答えは14,200なので、32ビット整数に収まります。
例
- 入力
- n = 4
- 出力
- 2
- 説明
- 各行のクイーンの列を上から下へ書くと、2つの盤面は
1, 3, 0, 2と2, 0, 3, 1です。それぞれはもう一方の鏡像であり、2通りとして数えます。それ以外の選び方では、2つのクイーンが同じ列または対角線上に配置されます。
- 入力
- n = 3
- 出力
- 0
- 説明
- 左上隅に女王を置くと、中段の右端だけが残り、下段には安全なマスがありません。右上隅も同じように失敗し、上段の中央に女王を置くと、中段の3つのマスすべてが攻撃されます。したがって、うまくいく盤面はありません。
提出時に隠しテスト+10件
発展問題
盤面を回転・反転した後も異なる盤面だけを数えられますか？ 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)です。
解説
各行に1つずつ列を選ぶことで配置が決まります。同じ行にいる2つのクイーンは必ず互いを攻撃するからです。それでも選択肢は n^n 通りあり、n = 12 の場合は約 8.9 × 10^12 通りなので、すべてを列挙することはできません。これを解決する方法は2つあります。行ごとに盤面を作り、クイーンが攻撃される状態になった時点で部分的な盤面を破棄すれば、n = 12 の場合、探索する部分的な盤面を100万未満に減らせます。また、使用済みの列と対角線を記録しておけば、マスの確認にかかるのは、これまでに配置したすべてのクイーンを調べる代わりに、3回の参照だけです。
各行にクイーンを1つずつ置いて、すべての配置を試してみましょう
正しいが、最大のテストでは終わらない
考え方
各行には女王をちょうど1つ配置する必要があるため、配置はリスト cols で表されます。ここで cols[r] は行 r にある女王の列です。各要素には n 個の列のいずれかを指定できるため、リストは n^n 個あります。走行距離計が数えるように、すべてのリストを順に試します。最後の要素を1増やし、それが n-1 を超えたら0に戻して、その前の要素に繰り上げます。
各リストについて、行 i < j のすべての組み合わせを比較します。同じ列にある場合、つまり cols[i] == cols[j] の場合、または同じ対角線上にある場合、2つの女王は互いに攻撃し合います。対角線上では、1行下に移動すると列が左右どちらかに1つ移動するため、列の差が行の差と等しいときに限り、2つの女王は同じ対角線上にあります。つまり |cols[i] - cols[j]| == j - i です。すべての組み合わせで条件を満たしたリストが、盤面の有効な配置です。すべてのリストを調べるため、見落としも二重に数えることもありません。
早期に処理を止めないため、時間がかかります。最初の2行で2つの女王が同じ対角線上にあれば、その盤面はすでに条件を満たしませんが、それでも走行距離計は残りの行を埋める n^(n-2) 通りすべてを試します。n = 8 の場合、92個の盤面を見つけるために16,777,216個のリストを調べます。n = 12 の場合は、約 8.9 × 10^12 個のリストになります。1リストあたり1ナノ秒でも、約2.5時間かかります。
アルゴリズム
colsをすべて0にして始めます。つまり、すべてのクイーンを列0に置きます。- 行のすべての組み合わせ
i < jを確認します。cols[i] == cols[j]または|cols[i] - cols[j]| == j - iの場合、そのリストは無効です。 - どの組み合わせも互いに攻撃し合わない場合、カウントに1を加えます。
- オドメーターのように
colsを進めます。最後の行から上に向かって、n-1を保持している各要素を0にリセットし、その後、そうでない最初の要素に1を加えます。 - すべての要素が
n-1だった場合、n^n個すべてのリストを確認したことになります。カウントを返します。
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 に到達した呼び出しでは、安全なクイーンを n 個配置できており、盤面を1つ数えます。これがバックトラッキングで、探索を大幅に枝刈りします。n = 12 の場合、完全な盤面 8.9 × 10^12 個ではなく、部分盤面を856,189個訪れます。
もう一つの要点は、マスをすばやく判定することです。下の行は空で、新しいクイーンの行にもほかのクイーンはいないため、マス (row, c) を攻撃できるのは、列、その / 対角線、その \ 対角線の3つだけです。同じ / 対角線上にあるすべてのマスでは、row + c が同じ値になり、その範囲は0から 2n-2 です。同じ \ 対角線上にあるすべてのマスでは、row - c が同じ値になり、その範囲は -(n-1) から n-1 です。そのため n-1 を加えて、0から 2n-2 までのインデックスにします。フラグ用の配列を3つ用意します。サイズ n の cols と、サイズ 2n-1 の diag および anti です。3つのフラグがすべてオフの場合に限り、そのマスは安全です。これは3回の参照で済むため O(1) です。これまでに配置したすべてのクイーンと比較すると、O(n) かかります。
1本の線上に置けるクイーンは最大1つなので、クイーンを置くと3つのフラグをオンにし、取り除くと再びオフにすることで、配列を元の状態に戻せます。4×4の盤面では、(0, 0) にクイーンを置くと、cols[0]、diag[0]、anti[3] が設定されます。行1の列1は anti[3] 上にあるため、クイーンそのものを調べることなく飛ばされます。
最初の行では n 列を試し、2行目では最大でも n-1 列を試す、と続くため、探索の上限は O(n!) となり、対角線による枝刈りで実際の探索量はそれより大幅に少なくなります。n = 12 の場合、ループでは合計10,103,868個のマスをテストします。再帰の深さは n 回で、配列には約 5n 個のフラグが格納されるため、空間計算量は O(n) です。
アルゴリズム
- すべてオフのフラグ配列を3つ作ります。
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として表し、3つのマスクを保持します。colsはすでに使われている列、leftはこの行で一方の対角線方向から攻撃されているマス、rightはもう一方から攻撃されているマスです。
空いているマスは、次の1つの式で求められます。free = ~(cols | left | right) & full。ここでfullは下位のnビットが1に設定されています。free & -freeで最も下位の空きマスだけを取り出し、それを引くと次のマスに進みます。bitの位置にクイーンを置いて1つ下の行へ進むと、その列は引き続き使用済みですが、各対角線の攻撃は1列ずつ移動します。そのため、次の行にはcols | bit、((left | bit) << 1) & full、(right | bit) >> 1を渡します。元に戻す処理は不要です。各呼び出しはそれぞれ独自の3つの整数を持ちます。cols == fullのとき、n個すべてのクイーンが配置されています。
n = 4とし、最初のクイーンを列1に置きます。bit = 0010です。列0を最も右のビットとして表記します。行1ではcols = 0010、left = 0100、right = 0001となるため、free = 1000です。列3だけが選択肢であり、列0、1、2を調べることなく見つかります。
この探索が訪れる部分盤面は集合版と同じですが、ループの各ステップで必ずクイーンを置くようになりました。n = 12の場合、マスの検査は10,103,868回ではなく856,188ステップとなり、各ステップは少数の整数演算で済みます。実行時間は依然としてO(n!)で上限が決まり、再帰の深さはn回の呼び出しです。Rのコードは再帰を使わずに同じマスクを処理します。各行のすべての部分盤面をベクトルに保持し、1行ずつまとめて増やしていくため、n回の呼び出しではなく、盤面の1つの階層全体をメモリに保持します。
アルゴリズム
full = (1 << n) - 1を、すべてのn列を表すマスクとして設定します。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をインデックスとして使う。Javaでは例外が発生し、Cでは配列の範囲外のメモリを読み取り、Pythonではanti[-2]が別の対角線のフラグを静かに読み取るため、エラーが出ないままカウントが間違います。- 対角線の配列のサイズを
n個にする。n × nの盤面には、それぞれの方向に2n-1本の対角線があります。 - 一方の方向の対角線だけを確認する、または列だけを確認する。どちらの方向の対角線も攻撃します。
- 再帰呼び出しから戻った後にフラグをオフにし忘れる。その後の各分岐で、すでに盤面にないクイーンがあるものとして扱われ、カウントが減ります。
freeの計算で& fullを省く。~xは列n-1より上のビットもすべてセットするため、ループが盤面の外のマスを選びます。また、整数の幅が固定されていないPythonやRubyでは、freeが負の値になり、ループが終わりません。- 鏡像を同じ盤面として扱う。この問題では別々に数えます。
n = 4の場合、盤面は2つあり、互いに鏡像です。 - 小さな盤面を誤って特別扱いする。
n = 1の場合は盤面が1つ、n = 2とn = 3の場合はどちらもありません。特別な処理をしなくても、探索ですべて正しく求められます。
よくある質問4
エイト・クイーン II の時間計算量はどれくらいですか？
バックトラッキングの計算量は上限が O(n!) です。1行目には n 個の選択肢があり、次の行には最大で n-1 個あり、以下同様です。対角線のチェックによって、この上限より大幅に枝刈りされ、n = 12 の場合、部分的な盤面は856,189個になります。解の個数を数える多項式時間の方法は知られていないため、このような探索が標準的な解法です。空間計算量は O(n) です。
正方形がどちらの対角線上にあるかは、どうすればわかりますか？
/方向の対角線に沿って1歩進むと、行に1を足し、列から1を引くため、row + colは変わりません。\方向の対角線に沿って進むと、行と列の両方に1を足すため、row - colは変わりません。それぞれの和が1本の対角線を表し、差にn-1を足すと、0から2n-2までの配列インデックスになります。
N-Queens と N-Queens II の違いは何ですか？
N-Queensでは、テキストの行として描画されたすべての盤面を求めます。N-Queens IIでは、その数だけを求めます。探索方法は同じバックトラッキングですが、数を数えるだけなら盤面をメモリに保持する必要はなく、列と対角線の集合だけで済むため、より高速で軽量です。そのため、ここではビットマスク版が自然な選択となります。
対称性を使って N-Queens II を高速化できますか？
はい。盤面を左右反転すると別の有効な盤面になるため、最初のクイーンが左半分にある盤面は、最初のクイーンが右半分にある盤面と一致します。最初のクイーンが列 0 から n/2 - 1 にある盤面を数えて2倍します。n が奇数の場合は、最初のクイーンが中央の列にある盤面を一度だけ加えます。これで探索量を半分にできます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def totalNQueens(n):
# ここにコードを書いてくださいケース1
ケース2
入力
n = 4
期待値
2