यह जांचने के लिए कार्यक्रम कि क्या हम पायथन में एन क्वीन्स समाधान प्राप्त कर सकते हैं या नहीं

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है जहां 0 खाली सेल का प्रतिनिधित्व कर रहा है और 1 उस सेल में शतरंज की रानी का प्रतिनिधित्व कर रहा है। हमें यह जांचना है कि क्या हम इस बोर्ड को भर सकते हैं और एक वैध रानी समाधान प्राप्त कर सकते हैं या नहीं। जैसा कि हम जानते हैं कि n क्वीन्स पहेली n क्वीन्स को n × n शतरंज की बिसात पर रखने के लिए कहती है ताकि कोई भी दो शतरंज क्वीन एक दूसरे पर हमला न कर सकें।

तो, अगर इनपुट पसंद है

तो आउटपुट ट्रू होगा, क्योंकि एक सॉल्यूशन इस तरह है -

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

• फ़ंक्शन को परिभाषित करें isSafe() । यह बोर्ड लेगा, i, j

• r के लिए 0 से लेकर बोर्ड के आकार तक के लिए, करें

  • यदि r, i के समान नहीं है और बोर्ड[r, j] 1 के समान है, तो

    • झूठी वापसी

• आर:=मैं + 1, सी:=जे + 1

• जबकि r <बोर्ड की पंक्ति का आकार और c <बोर्ड का स्तंभ आकार, करें

  • अगर बोर्ड [आर, सी] 1 के समान है, तो

    • झूठी वापसी

  • आर:=आर + 1, सी:=सी + 1

• r:=i + 1, c :=j - 1

• जबकि r <बोर्ड की पंक्ति का आकार और c>=0, करते हैं

  • अगर बोर्ड [आर, सी] 1 के समान है, तो

    • झूठी वापसी

  • r :=r + 1, c :=c - 1

• आर:=मैं -1, सी:=जे + 1

• जबकि r>=0 और c <बोर्ड का कॉलम आकार, करें

  • अगर बोर्ड [आर, सी] 1 के समान है, तो

    • झूठी वापसी

  • r :=r-1, c :=c + 1

• r :=i-1, c :=j-1

• जबकि r>=0 और c>=0, करें

  • अगर बोर्ड [आर, सी] 1 के समान है, तो

    • झूठी वापसी

  • r :=r-1, c :=c-1

• सही लौटें

• मुख्य विधि से निम्न कार्य करें -

• आर:=0, सी:=0

• स्टैक :=एक नया स्टैक

• जबकि r <बोर्ड की पंक्ति का आकार, करें

  • अगर 1 बोर्ड में है[r], तो

    • आर:=आर + 1

    • अगले पुनरावृत्ति के लिए जाएं

  • अन्यथा,

    • पाया :=असत्य

    • जबकि c <बोर्ड का कॉलम साइज, करें

      • यदि isSafe(board, r, c) सत्य है, तो

        • बोर्ड [आर, सी] :=1

        • [r, c] स्टैक में डालें

        • पाया :=सच

        • लूप से बाहर आएं

      • सी:=सी + 1

    • अगर पाया गया तो सच है, तो

      • सी:=0, आर:=आर + 1

    • अन्यथा,

      • अगर स्टैक खाली है, तो

        • झूठी वापसी

      • एम:=स्टैक से शीर्ष तत्व हटाएं

      • आर:=एम [0], सी:=एम [1] + 1

      • बोर्ड [आर, सी -1]:=0

• सही लौटें

उदाहरण

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

class Solution:
   def solve(self, board):
      def isSafe(board, i, j):
         for r in range(len(board)):
            if r != i and board[r][j] == 1:
               return False
         r, c = i + 1, j + 1
         while r < len(board) and c < len(board[0]):
            if board[r][c] == 1:
               return False
            r += 1
            c += 1
         r, c = i + 1, j - 1
         while r < len(board) and c >= 0:
            if board[r][c] == 1:
               return False
            r += 1
            c -= 1
         r, c = i - 1, j + 1
         while r >= 0 and c < len(board[0]):
            if board[r][c] == 1:
               return False
            r -= 1
            c += 1
         r, c = i - 1, j - 1
         while r >= 0 and c >= 0:
            if board[r][c] == 1:
               return False
            r -= 1
            c -= 1
         return True
      r = c = 0
      stack = []
      while r < len(board):
         if 1 in board[r]:
            r += 1
            continue
         else:
            found = False
            while c < len(board[0]):
               if isSafe(board, r, c):
                  board[r][c] = 1
                  stack.append([r, c])
                  found = True
                  break
               c += 1
            if found:
               c = 0
               r += 1
            else:
               if not stack:
                  return False
               m = stack.pop()
               r, c = m[0], m[1] + 1
               board[r][c - 1] = 0
      return True
ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [0, 0, 0, 0, 0],
   [0, 0, 0, 0, 1],
   [0, 0, 0, 0, 0],
   [0, 0, 0, 1, 0]
]
print(ob.solve(matrix))

इनपुट

[ [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1],
[0, 0, 0, 0, 0], [0, 0, 0, 1, 0] ]

आउटपुट

True