PythonでNクイーン問題の解が存在するかどうかを判定するプログラム

Nクイーン問題とは

0が空きマス、1がそのマスに配置されたチェスのクイーンを表す2値行列(バイナリマトリックス)が与えられているとします。この盤面を完成させ、有効なNクイーンの解が得られるかどうかを判定するのが本記事の目的です。ご存知の通り、Nクイーンパズルとは、n × n のチェス盤上に n 個のクイーンを、どの2つのクイーンも互いに攻撃し合わないように配置するという古典的な組合せ最適化問題です。

例として、次のような入力が与えられた場合を考えます。

この場合、出力は True になります。既に置かれた3つのクイーンを動かさずに、残りのマスを埋めることで、以下のような完全な解が構成できるからです。

解法のアプローチ

この問題は、スタックを用いたバックトラッキング(探索の巻き戻し)によって解きます。大まかな流れは以下の通りです。

1. 安全性チェック関数 isSafe() の定義

まず、指定したマス (i, j) にクイーンを置いても安全かどうかを判定する関数 isSafe() を定義します。引数は board(盤面)、i(行インデックス)、j(列インデックス)です。

• r を 0 から盤面のサイズ未満まで繰り返します。

  • r が i と異なり、board[r][j] が 1 である場合(同じ列に別のクイーンが存在する場合)は False を返します。

• r := i + 1、c := j + 1 とし、右下方向への斜めチェックを行います。

• r が行数未満 かつ c が列数未満である間、以下を繰り返します。

  • board[r][c] が 1 なら False を返します。

  • r := r + 1、c := c + 1

• r := i + 1、c := j − 1 とし、左下方向への斜めチェックを行います。

• r が行数未満 かつ c が 0 以上である間、以下を繰り返します。

  • board[r][c] が 1 なら False を返します。

  • r := r + 1、c := c − 1

• r := i − 1、c := j + 1 とし、右上方向への斜めチェックを行います。

• r が 0 以上 かつ c が列数未満である間、以下を繰り返します。

  • board[r][c] が 1 なら False を返します。

  • r := r − 1、c := c + 1

• r := i − 1、c := j − 1 とし、左上方向への斜めチェックを行います。

• r が 0 以上 かつ c が 0 以上である間、以下を繰り返します。

  • board[r][c] が 1 なら False を返します。

  • r := r − 1、c := c − 1

• すべてのチェックを通過したら True を返します。

2. メインメソッドでのバックトラッキング処理

• r := 0、c := 0 と初期化し、stack := 新しいスタックを用意します。

• r が盤面の行数未満である間、以下を繰り返します。

  • board[r] に 1 が含まれる場合(既にクイーンが置かれている行の場合)は、r := r + 1 として次の反復へ進みます。

  • それ以外の場合は以下を実行します。

    • found := False とします。

    • c が列数未満である間、以下を繰り返します。

      • isSafe(board, r, c) が真であれば、board[r][c] := 1 とし、[r, c] をスタックに積み、found := True としてループを抜けます。

      • c := c + 1

    • found が真であれば、c := 0、r := r + 1 として次の行へ進みます。

    • それ以外の場合(その行に置ける場所が見つからなかった場合)は、バックトラックを行います。

      • スタックが空であれば、解は存在しないので False を返します。

      • m := スタックの先頭要素を取り出します。

      • r := m[0]、c := m[1] + 1 とし、board[r][c − 1] := 0 として直前に置いたクイーンを取り除きます。

• すべての行にクイーンを配置できたら True を返します。

実装例

それでは、理解を深めるために実際の実装を見てみましょう。

class Solution:
   def solve(self, board):
      def isSafe(board, i, j):
         for r in range(len(board)):
            if r != i and board[r][j] == 1:
               return False
         r, c = i + 1, j + 1
         while r < len(board) and c < len(board[0]):
            if board[r][c] == 1:
               return False
            r += 1
            c += 1
         r, c = i + 1, j - 1
         while r < len(board) and c >= 0:
            if board[r][c] == 1:
               return False
            r += 1
            c -= 1
         r, c = i - 1, j + 1
         while r >= 0 and c < len(board[0]):
            if board[r][c] == 1:
               return False
            r -= 1
            c += 1
         r, c = i - 1, j - 1
         while r >= 0 and c >= 0:
            if board[r][c] == 1:
               return False
            r -= 1
            c -= 1
         return True
      r = c = 0
      stack = []
      while r < len(board):
         if 1 in board[r]:
            r += 1
            continue
         else:
            found = False
            while c < len(board[0]):
               if isSafe(board, r, c):
                  board[r][c] = 1
                  stack.append([r, c])
                  found = True
                  break
               c += 1
            if found:
               c = 0
               r += 1
            else:
               if not stack:
                  return False
               m = stack.pop()
               r, c = m[0], m[1] + 1
               board[r][c - 1] = 0
      return True
ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [0, 0, 0, 0, 0],
   [0, 0, 0, 0, 1],
   [0, 0, 0, 0, 0],
   [0, 0, 0, 1, 0]
]
print(ob.solve(matrix))

入力

[ [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1],
[0, 0, 0, 0, 0], [0, 0, 0, 1, 0] ]

出力

True

まとめ

このアルゴリズムのポイントは、次の2点です。

• 既存のクイーンを尊重: 既に 1 が含まれる行はスキップするため、入力として与えられたクイーンの位置は一切変更されません。
• スタックによるバックトラッキング: ある行でクイーンを置けるマスが見つからない場合、スタックから直前の配置を取り出して取り消し、次の候補列から再探索します。これにより、解が存在しないケースも正しく False と判定できます。

計算量の観点では、最悪の場合 O(n!) 程度の探索が必要になりますが、isSafe() による早期の枝刈りにより、実際の探索範囲は大幅に削減されます。Nクイーン問題はバックトラッキングの学習教材として非常に優れており、今回のように「部分的に埋まった盤面を完成させられるか」という応用問題にもそのまま応用できます。