ボードがPythonで有効なNクイーンソリューションであるかどうかを確認するプログラム

チェス盤を表すnxn行列があるとします。 1と0がいくつかあります。ここで、1はクイーンを表し、0は空のセルを表します。ボードがN-Queenパズルの有効な解決策であるかどうかを確認する必要があります。私たちが知っているように、ボードは、2人のクイーンが互いに攻撃していない有効なNクイーンソリューションのソリューションです。

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

その場合、出力はTrueになります

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

• n：=行列の行数
• rows：=新しいセット、cols：=新しいセット、diags：=新しいセット、rev_diags：=新しいセット
• 0からnの範囲のiについては、
  • 0からnの範囲のjについては、
    • matrix [i、j]が1の場合、
      • 行にiを挿入
      • jを列に挿入
      • diagsに（i --j）を挿入します
      • rev_diagsに（i + j）を挿入します
• 行のサイズ、列のサイズ、診断のサイズ、rev_diagsのサイズがnと同じ場合はtrueを返し、それ以外の場合はfalseを返します

理解を深めるために、次の実装を見てみましょう。

例

class Solution:
   def solve(self, matrix):
      n = len(matrix)

      rows = set()
      cols = set()
      diags = set()
      rev_diags = set()

      for i in range(n):
         for j in range(n):
            if matrix[i][j]:
               rows.add(i)
               cols.add(j)
               diags.add(i - j)
               rev_diags.add(i + j)

      return len(rows) == len(cols) == len(diags) == len(rev_diags) == n

ob = Solution()
matrix = [
   [0, 0, 0, 1, 0],
   [0, 1, 0, 0, 0],
   [0, 0, 0, 0, 1],
   [0, 0, 1, 0, 0],
   [1, 0, 0, 0, 0]
]
print(ob.solve(matrix))

入力

matrix = [    
   [0, 0, 0, 1, 0],    
   [0, 1, 0, 0, 0],    
   [0, 0, 0, 0, 1],    
   [0, 0, 1, 0, 0],    
   [1, 0, 0, 0, 0]
]

出力

True