華容道是一個有益的智力游戲，游戲規則不再贅述。用計算機求解華容道也是一道不錯的編程練習題，為了尋求最少步數，求解程序一般用廣度優先搜索算法。華容道的一種常見開局如圖 1 所示。

廣度優先搜索算法求解華容道的基本步驟：

1. 準備兩個“全局變量”，隊列 Q 和和集合 S，S 代表“已知局面”。初時 Q 和 S 皆為空。
2. 將初始局面加入隊列 Q 的末尾，并將初始局面設為已知。
3. 當隊列不為空時，從 Q 的隊首取出當前局面 curr。如果隊列為空則結束搜索，表明無解。
4. 如果 curr 是最終局面（曹操位于門口，圖 2），則結束搜索，否則繼續到第 5 步。
5. 考慮 curr 中每個可以移動的棋子，試著上下左右移動一步，得到新局面 next，如果新局面未知（next ∉ S），則把它加入隊列 Q，并設為已知。這一步可能產生多個新局面。
6. 回到第2步。

其中“局面已知”并不要求每個棋子的位置相同，而是指棋子的投影的形狀相同（代碼中用 mask 表示），例如交換圖 1 中的張飛和趙云并不產生新局面，這一規定可以大大縮小搜索空間。

以上步驟很容易轉換為 C++ 代碼，這篇文章重點關注的是第 5 步的實現。

// 第 1 步 
std::unordered_set<Mask> seen; 
std::deque<State> queue; 
  
// 第 2 步 
State initial; 
// 填入 initial，略。 
queue.push_back(initial); 
seen.insert(initial.toMask()); 
  
// 第 3 步 
while (!queue.empty()) 
{ 
  const State curr = queue.front(); 
  queue.pop_front(); 
  
  // 第 4 步 
  if (curr.isSolved()) 
    break; 
  
  // 第 5 步 
  for (const State& next : curr.moves()) 
  { 
    auto result = seen.insert(next.toMask()); 
    if (result.second) 
      queue.push_back(next); 
  } 
} 

在以上原始實現中，curr.move() 將返回一個 std::vector<State> 臨時對象。一種節省開銷的辦法是準備一個 std::vector<State> “涂改變量”，讓 curr.move() 反復修改它，比如改成：

// 第 1 步新增一個 scratch 變量 
std::vector<State> nextMoves; 
  
// 第 3 步 
while (!queue.empty()) 
{ 
  // ... 
  // 第 5 步 
  curr.fillMoves(&nextMoves); 
  for (const State& next : nextMoves) 
  { /* 略 */ } 
} 

還有一種徹底不用這個 std::vector<State> 的辦法，把一部分邏輯以 lambda 的形式傳給 curr.move()，代碼的結構基本不變：

// 第 3 步 
while (!queue.empty()) 
{ 
  // ... 
  // 第 5 步 
  curr.move([&seen, &queue](const State& next) { 
    auto result = seen.insert(next.toMask()); 
    if (result.second) 
      queue.push_back(next); 
  }); 
} 

這樣一來，主程序的邏輯依然清晰，不必要的開銷也降到了最小。

在我最早的實現中，curr.move() 的參數是 const std::function<void(const State&)> &，但是我發現這里每次構造 std::function<void(const State&)> 對象都會分配一次內存，似乎有些不值。因此在現在的實現中 curr.move() 是個函數模板，這樣就能自動匹配lambda參數（通常是個 struct 對象），省去了 std::function的內存分配。

本文完整的代碼見 https://github.com/chenshuo/recipes/…/puzzle/huarong.cc，需用 GCC 4.7 編譯，求解圖 1 的題目的耗時約幾十毫秒。

練習：修改程序，打印每一步移動棋子的情況。

原文鏈接：http://coolshell.cn/articles/10476.html