Chương trình để kiểm tra xem chúng ta có thể điền vào ô vuông nơi mỗi hàng và cột sẽ chứa các phần tử riêng biệt trong Python hay không

Giả sử chúng ta có một ma trận n × n chứa các giá trị từ 0 đến n. Ở đây 0 đại diện cho một ô vuông chưa được điền, chúng ta phải kiểm tra xem chúng ta có thể điền vào các ô trống không sao cho trong mỗi hàng và mỗi cột, mỗi số từ 1 đến n xuất hiện đúng một lần.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là True, vì chúng ta có thể đặt ma trận thành

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm find_empty_cell (). Điều này sẽ lấy ma trận, n

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • đối với j trong phạm vi từ 0 đến n, thực hiện

    • nếu ma trận [i, j] giống 0 thì

      • return (i, j)

• return (-1, -1)

• Định nghĩa một hàm is_feasible (). Điều này sẽ lấy ma trận, i, j, x

• nếu x ở hàng thứ i của ma trận thì

  • trả về Sai

• nếu x ở cột thứ j trong bất kỳ hàng nào của ma trận thì

  • trả về Sai

    
    

• trả về True

• Định nghĩa một hàm is_complete (). Điều này sẽ lấy ma trận, n

• đối với mỗi hàng trong ma trận, thực hiện

  • nếu hàng có một số phần tử trùng lặp thì

    • trả về Sai

  • đối với col trong phạm vi 0 đến n, thực hiện

    • nếu col có một số phần tử trùng lặp thì

      • trả về Sai

  • trả về True

  • Từ phương thức chính, hãy làm như sau -

  • n:=số hàng của ma trận

  • (i, j) =find_empty_cell (matrix, n)

  • nếu (i, j) giống với (-1, -1) thì

    • nếu is_complete (ma trận, n) là true, thì

      • trả về True

    • nếu không,

      • trả về Sai

  • đối với x trong phạm vi từ 1 đến n + 1, thực hiện

    • nếu is_feasible (matrix, i, j, x) là true thì

      • ma trận [i, j]:=x

      • nếu giải quyết (ma trận) là đúng, thì

        • trả về True

      • ma trận [i, j]:=0

  • trả về Sai

• 
  

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

True