Chương trình tìm số bước để giải câu đố 8 trong python

Giả sử chúng ta có một bảng 3x3 trong đó tất cả các số nằm trong phạm vi từ 0 đến 8 và không có số lặp lại ở đó. Bây giờ, chúng ta có thể hoán đổi số 0 với một trong 4 người hàng xóm của nó và chúng ta đang cố gắng giải nó để có được tất cả các trình tự đã sắp xếp, chúng ta phải tìm số bước tối thiểu cần thiết để đạt được mục tiêu.

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

3	1	2
4	7	5
6	8	0

thì đầu ra sẽ là 4

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

Xác định một hàm find_next (). Điều này sẽ lấy nút
di chuyển:=một bản đồ xác định các di chuyển dưới dạng danh sách tương ứng với từng giá trị {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 ],}
kết quả:=một danh sách mới
pos_0:=giá trị đầu tiên của nút
đối với mỗi bước di chuyển [pos_0], thực hiện
- new_node:=một danh sách mới từ nút
- hoán đổi new_node [move] và new_node [pos_0]
- chèn một bộ giá trị mới từ new_node vào cuối kết quả
trả về kết quả
Xác định một hàm get_paths (). Điều này sẽ có hiệu lực
cnt:=0
Thực hiện vô hạn những điều sau đây, hãy thực hiện
- current_nodes:=một danh sách có giá trị giống như cnt
- nếu kích thước của current_nodes bằng 0, thì
  - trả về -1
- đối với mỗi nút trong current_nodes, hãy thực hiện
  - next_moves:=find_next (nút)
  - đối với mỗi lần di chuyển trong next_moves, hãy thực hiện
    - nếu di chuyển không có trong dict, thì
      - dict [move]:=cnt + 1
    - nếu di chuyển giống với (0, 1, 2, 3, 4, 5, 6, 7, 8) thì
      - trả về cnt + 1
    - cnt:=cnt + 1
Từ phương thức chính, hãy làm như sau:
dict:=một bản đồ mới, san phẳng:=một danh sách mới
đối với tôi trong phạm vi 0 đến số hàng của bảng, hãy thực hiện
- san phẳng:=flatten + board [i]
flatten:=một bản sao của flatten
dict [làm phẳng]:=0
nếu san bằng giống như (0, 1, 2, 3, 4, 5, 6, 7, 8), thì
- trả về 0
trả về get_paths (dict)

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

Đầu vào

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

Chương trình tìm số bước để giải câu đố 8 trong python

Ví dụ

Đầu vào

Đầu ra