बोर्ड वैध N-क्वीन समाधान है या नहीं जांचने का पायथन प्रोग्राम

मान लीजिए हमारे पास एक n x n मैट्रिक्स है जो एक शतरंज बोर्ड को दर्शाता है। कुछ 1 और 0 हैं, जहां 1 एक क्वीन को दर्शाता है और 0 एक खाली सेल को दर्शाता है। हमें जांचना है कि क्या बोर्ड N-क्वीन पहेली का वैध समाधान है या नहीं। जैसा कि हम जानते हैं एक बोर्ड वैध N-क्वीन समाधान है जहां कोई दो क्वीन एक-दूसरे पर हमला नहीं कर रही हैं।

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

तो आउटपुट True होगा।

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

• n := मैट्रिक्स की पंक्ति संख्या
• rows := एक नया सेट, cols := एक नया सेट, diags := एक नया सेट, rev_diags := एक नया सेट
• i को 0 से n तक के लिए, करें
  • j को 0 से n तक के लिए, करें
    • यदि matrix[i, j] 1 है, तो
      • i को rows में डालें
      • j को cols में डालें
      • (i - j) को diags में डालें
      • (i + j) को rev_diags में डालें
• सत्य लौटाएं जब rows, cols, diags, rev_diags का आकार n के समान हो, अन्यथा असत्य

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

उदाहरण

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        rows = set()
        cols = set()
        diags = set()
        rev_diags = set()
        for i in range(n):
            for j in range(n):
                if matrix[i][j]:
                    rows.add(i)
                    cols.add(j)
                    diags.add(i - j)
                    rev_diags.add(i + j)
        return len(rows) == len(cols) == len(diags) == len(rev_diags) == n

ob = Solution()
matrix = [
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0]
]
print(ob.solve(matrix))

इनपुट

matrix = [
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0]
]

आउटपुट

True