# LeetCode Hard 52. N-Queens II
tags: leetcode
問題
n-queens
パズルはどの2つのクイーンもお互いに攻撃できない位置にnxn
のチェス盤にn
個のクイーンを配置する問題です整数
n
を与えられた時,n-queens
パズルへの異なる解答の数を返せ
解法
有名な問題ですね
"N-Queens II"という題名からおそらく"I"が存在するということが考えられます
ではこの問題を解こうと思いますが, 全探索すると時間計算量が$O(n^{n})$になってしまいます
これではまずいので何か方法がないのかと考えるとバックトラック(backtracking)という方法があることに気づきます
Backtracking
バックトラックとは探索において, 明らかに答えにならないと判明した解の候補をそれ以上探索しないというアルゴリズムです
下のように答えにならない解を早く見つければ見つけるほど, 無駄な計算を省くことが出来ます
N-Queensの解き方(recursive)
iterativeに解く方法もありますが, ここでは実装が単純なのでrecursiveに解きます
- 片側から配置します
- これによって横もしくは縦について考える必要がなくなります
- 片側から順番に入れているので重複してコマを置くことがなくなります
- 私の実装では左の列から右の列に向かって配置することにします
- 配列で横, 斜め上, 斜め下での置けない要素を保存します(
true
ならばまだ置けるということにします)cols[i] := 上からi番目にコマが置かれている
dpos[i + j] := 斜め上に伸びる直線状にコマが置かれている
- 左下から右上まで伸びる直線上のコマは
(n-1, 0)
,(n-2, 1)
,(n-3, 2)
,...のように行+列=一定
となります
- 左下から右上まで伸びる直線上のコマは
dneg[N-1 + depth - i] := 斜め下に伸びる直線状にコマが置かれている
- 左上から右下まで伸びる直線状のコマは
(0, 0)
,(1, 1)
,...のように行-列=一定
となります
- 左上から右下まで伸びる直線状のコマは
- これを
row = 行
を0から初めます- 基底は行と列の大きさが同じになるときです
- もし, 探索においてクイーンがお互いに攻撃できる位置にあるときはそれ以上再帰関数を実行しないようにします
- これによって探索を減らすことが出来ます
計算量
計算量は不明です
このような分岐をある情報から選択的に選ぶアルゴリズムをヒューリスティック探索と言い, 単純なアルゴリズムと比べて実行速度を高速化することが可能です
Python
Pythonは関数に渡す値がimuutableであるかmutableであるか気を付けないといけません
ここでは, cnt
をインクリメントする際に数値はimmutableなのでself.cnt
を使いましょう
class Solution: def totalNQueens(self, n: int) -> int: def helper(row, cols, dpos, dneg): if row == len(cols): self.cnt += 1 return for col in range(len(cols)): if cols[col] and dpos[row + col] and dneg[len(cols) - 1 + row - col]: cols[col], dpos[row + col], dneg[len(cols) - 1 + row - col] = False, False, False helper(row + 1, cols, dpos, dneg) cols[col], dpos[row + col], dneg[len(cols) - 1 + row - col] = True, True, True self.cnt = 0 cols = [True] * n dpos = [True] * (2*n-1) dneg = [True] * (2*n-1) helper(0, cols, dpos, dneg) return self.cnt
C++
class Solution { public: int totalNQueens(int n) { int cnt = 0; vector<bool> cols(n, true); vector<bool> dpos(2*n-1, true); vector<bool> dneg(2*n-1, true); rec(0, cnt, cols, dpos, dneg); return cnt; } private: void rec(int row, int& cnt, vector<bool>& cols, vector<bool>& dpos, vector<bool>& dneg) { if (row == cols.size()) { ++cnt; return; } for (int col = 0; col < cols.size(); col++) { if (cols[col] && dpos[row + col] && dneg[cols.size() - 1 + row - col]) { cols[col] = dpos[row + col] = dneg[cols.size() - 1 + row - col] = false; rec(row + 1, cnt, cols, dpos, dneg); cols[col] = dpos[row + col] = dneg[cols.size() - 1 + row - col] = true; } } } };