यह जाँचने के लिए कार्यक्रम कि क्या हम उस वर्ग को भर सकते हैं जहाँ प्रत्येक पंक्ति और स्तंभ में पायथन में अलग-अलग तत्व होंगे

मान लीजिए कि हमारे पास एक n × n मैट्रिक्स है जिसमें 0 से n तक के मान हैं। यहां 0 एक अधूरे वर्ग का प्रतिनिधित्व करता है, हमें यह जांचना है कि क्या हम खाली वर्गों को इस तरह भर सकते हैं कि प्रत्येक पंक्ति और प्रत्येक कॉलम में 1 से n तक की प्रत्येक संख्या ठीक एक बार दिखाई दे।

तो, अगर इनपुट पसंद है

तब आउटपुट ट्रू होगा, क्योंकि हम मैट्रिक्स को

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें find_empty_cell() । यह मैट्रिक्स लेगा, n

• मेरे लिए 0 से n की सीमा में, करें

  • j के लिए 0 से n की सीमा में, करें

    • यदि मैट्रिक्स [i, j] 0 के समान है, तो

      • वापसी (i, j)

• वापसी(-1, -1)

• फ़ंक्शन को परिभाषित करें is_feasible() । यह मैट्रिक्स लेगा, i, j, x

• यदि x मैट्रिक्स की छठी पंक्ति में है, तो

  • झूठी वापसी

• यदि x मैट्रिक्स की किसी भी पंक्ति में jth कॉलम में है, तो

  • झूठी वापसी

    
    

• सही लौटें

• फ़ंक्शन को परिभाषित करें is_complete() । यह मैट्रिक्स लेगा, n

• मैट्रिक्स में प्रत्येक पंक्ति के लिए, करें

  • यदि पंक्ति में कुछ डुप्लिकेट तत्व हैं, तो

    • झूठी वापसी

  • 0 से n के बीच के कॉलम के लिए, करें

    • अगर कर्नल में कुछ डुप्लीकेट एलिमेंट हैं, तो

      • झूठी वापसी

  • सही लौटें

  • मुख्य विधि से निम्न कार्य करें -

  • n :=मैट्रिक्स की पंक्ति गणना

  • (i, j) =find_empty_cell (मैट्रिक्स, n)

  • अगर (i, j) (-1, -1) के समान है, तो

    • अगर is_complete(matrix, n) सत्य है, तो

      • सही लौटें

    • अन्यथा,

      • झूठी वापसी

  • 1 से n + 1 की श्रेणी में x के लिए, करें

    • यदि is_feasible(matrix, i, j, x) सत्य है, तो

      • मैट्रिक्स [i, j] :=x

      • यदि हल (मैट्रिक्स) सत्य है, तो

        • सही लौटें

      • मैट्रिक्स [i, j] :=0

  • झूठी वापसी

• 
  

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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