Neunomizuの日記

俺だけが俺だけじゃない

# 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;
      }
    }
  }
};