معالجة 8 لغز عبر BFS

Question

لقد سمعت أن مشكلة 8 ألغاز يمكن تناولها عبر BFS، لكنني لا أفهم كيف. أريد أن أعرف الخطوات المتوسطة التي أحتاج إلى الحصول عليها من لوحة مثل هذا:

3 1 2
6 4 5
0 7 8

ل

1 2 3
4 5 6
7 8 0 

هي الخطوات المتوسطة "مستويات" على البحث BFS؟

بالمناسبة، هذا هو الواجبات المنزلية الأساسية، لا يهمني الفتحة.

Answer 1

هذا هو قالب كبير لأي بحث BFS

function next_boards(board)
   yields a set of reachable in one move from the current board

queue = [start_board]

while true:
   current = queue.pop()
   if current = goal: break

   queue.push for all next_boards(current)

لاحظ أننا لا نفعل أي شيء يتوهم مثل التحقق من الدورات أو أي شيء. إذا كنا، نغير قائمة الانتظار إلى مكدس، وتحصل على DFS.