App「排序拼圖」在出題之前,會先用電腦確認可以解開。「提示」的下一步,也是同一個求解器找到的步驟的第 1 步。這裡介紹那個求解器的機制。

沿著局面與走法往下走

排序拼圖的盤面狀態(哪個容器裡裝著什麼顏色),稱為局面。移動 1 步,就會變成另一個局面。從最初的局面沿著走法往下走,只要抵達排好的局面,走過的路就是答案。

最直接的找法,是把 1 步能到的局面全部、接著 2 步能到的局面全部……一路展開的廣度優先搜尋。一定能找到最少步數的答案,但顏色一多,要檢查的局面就會變得非常龐大。

離排好還有多「遠」的估計值

所以 App 會對每個局面,算出離排好還有多遠的估計值,先檢查看起來比較近的局面。估計值是下面 2 項的合計。

  1. 容器裡顏色的交界數量:從下往上看,顏色改變的地方有幾處。
  2. 底部的重複:同一種顏色如果在好幾個容器的底部,就是那個數量減 1。
123456

這個盤面的話,顏色的交界在第 1 個有 2 處、第 2 個有 2 處、第 3 個有 3 處、第 4 個有 3 處,合計 10。天藍色在第 3 個和第 4 個的底部,所以底部的重複是 1。估計值是 11。在排好的局面裡,交界和重複都沒有了,所以估計值是 0。

估計值不會比最少步數大

這個估計值有一個很好的性質。1 步最多只會讓估計值減少 1。

  • 倒 1 次,被移出的容器的交界最多只會減少 1 處。移過去的地方是同色的上面或空容器,所以交界不會增加也不會減少。
  • 容器變空、底部的重複減少 1 的情況,只發生在移走那個容器最後一段連續顏色的時候,而這時交界不會減少。

也就是說,估計值是 11 的盤面,至少需要 11 步。在各種盤面上檢查了 12 萬多種走法,也沒有任何一步會讓估計值一次減少 2 以上。上面這個盤面的最少步數,剛好就是 11 步。

加權 A* 搜尋

App 會給每個局面打上「到目前為止的步數 + 3 × 估計值」的分數,先檢查分數小的局面。這稱為加權 A*(A-star)搜尋。

  • 權重設為 1(一般的 A* 搜尋)的話,因為估計值是最少步數的下限,一定能找到最少步數的答案。
  • 權重設為 3 的話,會不斷先檢查估計值小的局面,所以能快很多找到答案。代價是,有時會得到比最少步數稍長的答案。

我們用和 App 相同的方式各做 20 道題目,比較了排到好之前檢查的局面數,以及找到的答案步數(★3 的廣度優先搜尋因為局面太多,所以沒有數)。

★1(4 色、空 2)檢查的局面答案的步數
廣度優先搜尋53711.8
A*(權重 1)20311.8
A*(權重 3)3911.9
★2(6 色、空 2)檢查的局面答案的步數
廣度優先搜尋293418.1
A*(權重 1)62218.1
A*(權重 3)6418.8

兩個都是 20 道題目的平均。權重 3 只用了廣度優先搜尋幾十分之一的局面就找到答案,步數只增加了一點點。

減少要檢查的走法的巧思

App 的求解器,還用了下面這些巧思來減少要檢查的局面。

  • 不區分容器的順序:容器裡的內容物一樣的話,就算順序不同,也當作同一個局面。
  • 不檢查沒有意義的走法:把只有 1 種顏色的容器移進空容器的走法(形狀不會改變),以及移進第 2 個以後的空容器的走法(會變成和第 1 個一樣的局面),都排除。
  • 只用「倒」的走法來搜尋:「疊」的題目,也是檢查能不能用倒的走法解開(「倒」與「疊」的差別)。
  • 設定上限:檢查了 6 萬個局面還是找不到的話,就當作「不知道」,這個配法就不使用。

用這個求解器,同時負責製作題目時的「確認能不能解開」(一定能解開的題目怎麼做)和「提示」(提示的用法)。底部顏色的想法,也在先集中哪個顏色?裡介紹過。