আমরা স্কোয়ার পূরণ করতে পারি কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম যেখানে প্রতিটি সারি এবং কলাম পাইথনে স্বতন্ত্র উপাদান ধারণ করবে

ধরুন আমাদের একটি n × n ম্যাট্রিক্স আছে যেখানে 0 থেকে n পর্যন্ত মান রয়েছে। এখানে 0 একটি অপূর্ণ বর্গক্ষেত্রের প্রতিনিধিত্ব করে, আমাদের পরীক্ষা করতে হবে যে আমরা খালি বর্গগুলি পূরণ করতে পারি কি না যাতে প্রতিটি সারিতে এবং প্রতিটি কলামে 1 থেকে n পর্যন্ত প্রতিটি সংখ্যা ঠিক একবার প্রদর্শিত হয়৷

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে True, যেহেতু আমরা ম্যাট্রিক্সকে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন find_empty_cell()। এটি ম্যাট্রিক্স নেবে, n

• 0 থেকে n রেঞ্জের জন্য, করুন

  • 0 থেকে n রেঞ্জে j এর জন্য, করুন

    • যদি ম্যাট্রিক্স[i, j] 0 এর মত হয়, তাহলে

      • রিটার্ন(i, j)

• ফেরত (-1, -1)

• একটি ফাংশন is_feasible() সংজ্ঞায়িত করুন। এটি ম্যাট্রিক্স, i, j, x

  লাগবে

• যদি x ম্যাট্রিক্সের 1র্থ সারিতে থাকে, তাহলে

  • রিটার্ন ফলস

• যদি ম্যাট্রিক্সের যেকোনো সারিতে jth কলামে x হয়, তাহলে

  • রিটার্ন ফলস

    
    

• রিটার্ন ট্রু

• একটি ফাংশন is_complete() সংজ্ঞায়িত করুন। এটি ম্যাট্রিক্স নেবে, n

• ম্যাট্রিক্সের প্রতিটি সারির জন্য, করুন

  • যদি সারিতে কিছু সদৃশ উপাদান থাকে, তাহলে

    • রিটার্ন ফলস

  • 0 থেকে n রেঞ্জের কলের জন্য, করুন

    • যদি col এর কিছু সদৃশ উপাদান থাকে, তাহলে

      • রিটার্ন ফলস

  • রিটার্ন ট্রু

  • প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

  • 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