पायथन में जांचें कि क्या हम वर्ग को भर सकते हैं जहां प्रत्येक पंक्ति और स्तंभ में विशिष्ट तत्व हों

मान लीजिए हमारे पास एक n×n मैट्रिक्स है जिसमें 0 से n तक के मान हैं। यहां 0 एक अनभरा सेल दर्शाता है। हमें जांचना है कि क्या हम खाली सेल भर सकते हैं ताकि प्रत्येक पंक्ति और प्रत्येक स्तंभ में 1 से n तक की हर संख्या ठीक एक बार आए।

उदाहरण के लिए, यदि इनपुट मैट्रिक्स है:

0	0	2
2	0	1
1	2	3

तो आउटपुट True होगा, क्योंकि हम मैट्रिक्स को इस प्रकार भर सकते हैं:

3	1	2
2	3	1
1	2	3

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (बैकट्रैकिंग):

find_empty_cell(matrix, n) फ़ंक्शन परिभाषित करें जो पहला खाली सेल (0) ढूंढता है।
is_feasible(matrix, i, j, x) फ़ंक्शन परिभाषित करें जो जांचता है कि क्या x को (i,j) पर रखना मान्य है (पंक्ति और स्तंभ में डुप्लिकेट नहीं)।
is_complete(matrix, n) फ़ंक्शन परिभाषित करें जो जांचता है कि क्या मैट्रिक्स पूरी तरह भरा है और प्रत्येक पंक्ति/स्तंभ में 1 से n तक सभी संख्याएं हैं।
मुख्य विधि से:
- n := len(matrix)।
- (i, j) = find_empty_cell(matrix, n)।
- यदि (i, j) == (-1, -1) (कोई खाली सेल नहीं):
  - यदि is_complete(matrix, n) सत्य है तो True लौटाएं, अन्यथा False।
- x को 1 से n तक लूप में चलाएं:
  - यदि is_feasible(matrix, i, j, x) सत्य है:
    - matrix[i][j] = x।
    - यदि solve(matrix) रिकर्सिवली सत्य लौटाता है, तो 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