Pythonで各行と列が異なる要素を保持する正方形を埋めることができるかどうかを確認するプログラム

0からnまでの値を含む1つのn×n行列があるとします。ここで、0は塗りつぶされていない正方形を表します。空の正方形を塗りつぶして、各行と各列に1からnまでのすべての数字が1回だけ表示されるかどうかを確認する必要があります。

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

行列を

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

• 関数find_empty_cell（）を定義します。これは行列を取ります、n

• 0からnの範囲のiの場合、実行

  • 0からnの範囲のjについては、次のようにします

    • matrix [i、j]が0と同じ場合、

      • return（i、j）

• return（-1、-1）

• 関数is_feasible（）を定義します。これは行列、i、j、xを取ります

• 行列のi番目の行にxがある場合、

  • Falseを返す

• 行列の任意の行のj番目の列にxがある場合、

  • Falseを返す

    
    

• Trueを返す

• 関数is_complete（）を定義します。これは行列を取ります、n

• 行列の各行について、次のようにします

  • 行に重複する要素がある場合は、

    • Falseを返す

  • 0からnの範囲の列については、実行してください

    • colに重複する要素がある場合は、

      • Falseを返す

  • Trueを返す

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

  • n：=行列の行数

  • （i、j）=find_empty_cell（matrix、n）

  • （i、j）が（-1、-1）と同じ場合、

    • is_complete（matrix、n）がtrueの場合、

      • Trueを返す

    • それ以外の場合

      • Falseを返す

  • xが1からn+1の範囲の場合、実行

    • is_feasible（matrix、i、j、x）がtrueの場合、

      • matrix [i、j]：=x

      • Solve（matrix）がtrueの場合、

        • Trueを返す

      • matrix [i、j]：=0

  • Falseを返す

• 
  

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

例

class Solution:
   def solve(self, matrix):
      n = len(matrix)
      def find_empty_cell(matrix, n):
         for i in range(n):
            for j in range(n):
               if matrix[i][j] == 0:
                  return (i, j)
         return (-1, -1)
      def is_feasible(matrix, i, j, x):
         if x in matrix[i]:
            return False
         if x in [row[j] for row in matrix]:
            return False
         return True
      def is_complete(matrix, n):
         for row in matrix:
            if set(row) != set(range(1, n + 1)):
               return False
         for col in range(n):
            if set(row[col] for row in matrix) != set(range(1, n + 1)):
               return False
         return True
      (i, j) = find_empty_cell(matrix, n)

      if (i, j) == (-1, -1):
         if is_complete(matrix, n):
            return True
         else:
            return False
      for x in range(1, n + 1):
         if is_feasible(matrix, i, j, x):
            matrix[i][j] = x
            if self.solve(matrix):
               return True
            matrix[i][j] = 0
      return False
ob = Solution()
matrix = [
   [0, 0, 2],
   [2, 0, 1],
   [1, 2, 3]
]
print(ob.solve(matrix))

入力

matrix = [
   [0, 0, 2],
   [2, 0, 1],
   [1, 2, 3] ]

出力

True