通过BFS解决8个难题

Question

我听说8-puzzle问题可以通过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。