โปรแกรมตรวจสอบว่าเราสามารถเติมช่องสี่เหลี่ยมโดยที่แต่ละแถวและคอลัมน์จะมีองค์ประกอบที่แตกต่างกันใน Python . หรือไม่

สมมติว่าเรามีเมทริกซ์ n × n หนึ่งตัวที่มีค่าตั้งแต่ 0 ถึง n ในที่นี้ 0 หมายถึงช่องสี่เหลี่ยมที่ไม่มีการเติม เราต้องตรวจสอบว่าเราสามารถเติมช่องสี่เหลี่ยมว่างได้หรือไม่ โดยที่ในแต่ละแถวและแต่ละคอลัมน์ ทุกตัวเลขตั้งแต่ 1 ถึง n ปรากฏขึ้นเพียงครั้งเดียว

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น True เนื่องจากเราสามารถตั้งค่าเมทริกซ์เป็น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน find_empty_cell() นี่จะใช้เมทริกซ์ n

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • สำหรับ j ในช่วง 0 ถึง n ทำ

    • ถ้า matrix[i, j] เท่ากับ 0 แล้ว

      • กลับ (i, j)

• ผลตอบแทน(-1, -1)

• กำหนดฟังก์ชัน is_feasible() นี่จะใช้เมทริกซ์, i, j, x

• ถ้า x ในแถวของเมทริกซ์แล้ว

  • คืนค่าเท็จ

• ถ้า x ในคอลัมน์ jth ในแถวของเมทริกซ์ใดๆ แล้ว

  • คืนค่าเท็จ

    
    

• คืนค่า True

• กำหนดฟังก์ชัน is_complete() นี่จะใช้เมทริกซ์ n

• สำหรับแต่ละแถวในเมทริกซ์ ทำ

  • หากแถวมีองค์ประกอบซ้ำกัน

    • คืนค่าเท็จ

  • สำหรับ col ในช่วง 0 ถึง n ให้ทำ

    • หาก col มีองค์ประกอบที่ซ้ำกัน

      • คืนค่าเท็จ

  • คืนค่า True

  • จากวิธีหลักให้ทำดังต่อไปนี้ -

  • n :=จำนวนแถวของเมทริกซ์

  • (i, j) =find_empty_cell(เมทริกซ์, n)

  • ถ้า (i, j) เหมือนกับ (-1, -1) แล้ว

    • ถ้า is_complete(matrix, n) เป็นจริง แล้ว

      • คืนค่า True

    • มิฉะนั้น

      • คืนค่าเท็จ

  • สำหรับ x ในช่วง 1 ถึง n + 1 ทำ

    • ถ้า is_feasible(matrix, i, j, x) เป็นจริง แล้ว

      • เมทริกซ์[i, j] :=x

      • ถ้าการแก้(เมทริกซ์) เป็นจริงแล้ว

        • คืนค่า True

      • เมทริกซ์[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