PythonでN個のクイーンソリューションを取得できるかどうかを確認するプログラム

0が空のセルを表し、1がそのセルのチェスの女王を表すバイナリ行列があるとします。このボードを埋めて、有効なnqueenソリューションを取得できるかどうかを確認する必要があります。私たちが知っているように、nクイーンのパズルは、2つのチェスクイーンが互いに攻撃できないように、n×nのチェス盤にnのクイーンを配置するように求めます。

したがって、入力が次のような場合

その場合、1つのソリューションは-

これを解決するには、次の手順に従います-

• 関数isSafe（）を定義します。これはボードを取ります、i、j

• 0からボードのサイズまでの範囲のrについては、次のようにします

  • rがiと同じでなく、board [r、j]が1と同じである場合、

    • Falseを返す

• r：=i + 1、c：=j + 1

• r <ボードの行サイズ、c <ボードの列サイズ、do

  • 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を返す

• メインの方法から、次のようにします-

• r：=0、c：=0

• スタック：=新しいスタック

• r <ボードの行サイズ、実行

  • 1がボード[r]にある場合、

    • r：=r + 1

    • 次のイテレーションに行く

  • それ以外の場合

    • 見つかった：=False

    • c <ボードの列サイズ、実行

      • isSafe（board、r、c）がtrueの場合、

        • ボード[r、c]：=1

        • [r、c]をスタックに挿入します

        • 見つかった：=True

        • ループから出てきます

      • c：=c + 1

    • 見つかった場合はtrue、

      • c：=0、r：=r + 1

    • それ以外の場合

      • スタックが空の場合、

        • Falseを返す

      • m：=スタックから最上位の要素を削除する

      • r：=m [0]、c：=m [1] + 1

      • ボード[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