पायथन में 8-पहेली को हल करने के लिए चरणों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक 3x3 बोर्ड है जहां सभी संख्याएं 0 से 8 की सीमा में हैं और कोई दोहराई जाने वाली संख्या नहीं है। अब, हम 0 को उसके 4 पड़ोसियों में से एक के साथ स्वैप कर सकते हैं, और हम सभी व्यवस्थित अनुक्रम प्राप्त करने के लिए इसे हल करने का प्रयास कर रहे हैं, हमें लक्ष्य तक पहुंचने के लिए आवश्यक न्यूनतम चरणों की संख्या ज्ञात करनी होगी।

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

तो आउटपुट 4

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

• एक फ़ंक्शन को परिभाषित करें find_next() । यह नोड लेगा
• चालें:=एक नक्शा परिभाषित करने वाला प्रत्येक मान के अनुरूप सूची के रूप में चलता है {0:[1, 3],1:[0, 2, 4],2:[1, 5],3:[0, 4 , 6], 4:[1, 3, 5, 7], 5:[2, 4, 8], 6:[3, 7], 7:[4, 6, 8], 8:[5, 7 ],}
• परिणाम:=एक नई सूची
• pos_0 :=नोड का पहला मान
• चाल में प्रत्येक चाल के लिए[pos_0], करें
  • new_node :=नोड से एक नई सूची
  • स्वैप new_node[move] और new_node[pos_0]
  • परिणामों के अंत में new_node से एक नया टपल डालें
• परिणाम लौटाएं
• एक फ़ंक्शन को परिभाषित करें get_paths() । यह निर्देश लेगा
• सीएनटी:=0
• निम्नलिखित को असीम रूप से करें, करें
  • current_nodes :=एक सूची जहां मान cnt के समान है
  • यदि current_nodes का आकार 0 के समान है, तो
    • वापसी -1
  • current_nodes में प्रत्येक नोड के लिए, करें
    • अगला_चाल :=find_next(नोड)
    • नेक्स्ट_मूव्स में प्रत्येक चाल के लिए, करें
      • यदि निर्देश में चाल मौजूद नहीं है, तो
        • dict[move] :=cnt + 1
      • यदि चाल समान है (0, 1, 2, 3, 4, 5, 6, 7, 8) , तो
        • सीएनटी + 1 लौटाएं
      • सीएनटी:=सीएनटी + 1
• मुख्य विधि से निम्न कार्य करें:
• तानाशाही:=एक नया नक्शा, समतल करें:=एक नई सूची
• मैं के लिए 0 से लेकर बोर्ड की पंक्ति गणना तक, करते हैं
  • चपटा:=समतल + बोर्ड[i]
• समतल :=समतल की एक प्रति
• dict[flatten] :=0
• यदि समतल (0, 1, 2, 3, 4, 5, 6, 7, 8) के समान है, तो
  • वापसी 0
• रिटर्न get_paths(dict)

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

उदाहरण

class Solution:
   def solve(self, board):
      dict = {}
      flatten = []
      for i in range(len(board)):
         flatten += board[i]
      flatten = tuple(flatten)

      dict[flatten] = 0

      if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
         return 0

      return self.get_paths(dict)

   def get_paths(self, dict):
      cnt = 0
      while True:
         current_nodes = [x for x in dict if dict[x] == cnt]
         if len(current_nodes) == 0:
            return -1

         for node in current_nodes:
            next_moves = self.find_next(node)
            for move in next_moves:
               if move not in dict:
                  dict[move] = cnt + 1
               if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
                  return cnt + 1
         cnt += 1

   def find_next(self, node):
      moves = {
         0: [1, 3],
         1: [0, 2, 4],
         2: [1, 5],
         3: [0, 4, 6],
         4: [1, 3, 5, 7],
         5: [2, 4, 8],
         6: [3, 7],
         7: [4, 6, 8],
         8: [5, 7],
      }

      results = []
      pos_0 = node.index(0)
      for move in moves[pos_0]:
         new_node = list(node)
         new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
         results.append(tuple(new_node))

      return results
ob = Solution()
matrix = [
   [3, 1, 2],
   [4, 7, 5],
   [6, 8, 0]
]
print(ob.solve(matrix))

इनपुट

matrix = [  
[3, 1, 2],  
[4, 7, 5],  
[6, 8, 0] ]

आउटपुट

4