ChromaOracle 透過一種叫做 BFS（廣度優先搜尋）的演算法，找到任何顏色分類謎題的最短解。求解器不靠猜測、也不依賴啟發式，而是系統地探索每一種可能的移動序列——從最短的開始——直到找到一個能解開謎題的序列。這保證了它回傳的解使用了盡可能少的移動步數。下面解釋它的運作原理，既面向好奇的玩家,也面向技術讀者。
把謎題看作搜尋問題
每一個顏色分類謎題——無論是 Water Sort、Ball Sort 還是任何變體——都可以描述為一個搜尋問題。任意時刻的謎題棋盤都是一個「狀態」:所有試管之間的某種具體顏色排列。每一次合法的傾倒或移動都把一個狀態轉換成另一個狀態。求解謎題意味著找到一個移動序列,把起始狀態轉換成目標狀態——也就是每個試管要麼只裝一種顏色、要麼是空的狀態。
把它想像成一張地圖。每個交叉路口是一個狀態。交叉路口之間的每條路是一次移動。起始狀態是你現在的位置,目標狀態是你的目的地。求解器的工作就是找出最短路線。
什麼是廣度優先搜尋?
廣度優先搜尋是一種以非常特定的順序探索這張狀態地圖的方法:它先檢查所有距離起點一步的狀態,再檢查所有距離起點兩步的狀態,然後是三步,依此類推。它逐層向四面八方均勻擴散。
這種分層做法正是它能保證最佳性的原因。因為 BFS 在探索任何六步解之前,會先探索所有的五步解。所以它第一次到達目標狀態時,必然是透過最短路徑到達的——不可能存在更短的路徑被它漏掉,因為所有更短的可能性都已經被它檢查過了。
具體過程如下:
- 從初始棋盤狀態開始。
- 生成該狀態的所有合法移動。每一次移動產生一個新的棋盤狀態。
- 檢查這些新狀態中是否有任何一個是已解狀態。如果有,回傳這個移動序列。
- 如果沒有,把所有新狀態加入佇列,然後從佇列中的下一個狀態重複第 2 步。
- 持續下去,直到找到目標,或者所有可達狀態都被探索完。
如果佇列被清空仍未找到解,這個謎題就是無解的——求解器會立即報告。
狀態空間的表示
為了讓 BFS 高效運作,求解器需要一種緊湊表示每個棋盤狀態、並能識別已訪問狀態的方法。ChromaOracle 把每個試管表示為一個顏色堆疊,把整個棋盤表示為這些堆疊的集合。
為了避免兩次探索同一個狀態——這會浪費時間和記憶體——求解器為每個狀態生成一個規範鍵。這個鍵是棋盤的歸一化字串表示,它會把相同的排列視為同一個狀態,而不管試管的左右順序如何。如果兩個棋盤的試管內容相同、只是左右順序不同,它們會產生同樣的鍵,被識別為重複。
這種去重至關重要。沒有它,求解器會把同樣的位置訪問幾百萬次,慢到不可用。有了它,求解器只處理每個唯一狀態一次。
為什麼 BFS 保證給出最短解
這個保證來自探索的順序。BFS 嚴格按狀態距起點的距離(以移動步數衡量)來處理狀態。每個距離為 N 的狀態都會先於任何距離為 N+1 的狀態被處理。因此,求解器第一次到達目標狀態時,必然是透過長度為 N 的路徑——而長度小於 N 的路徑不存在,因為所有更短的路徑都已經被完全探索過。
這是演算法的數學性質,而不是啟發式或近似。BFS 回傳的解可證明是最佳的。
BFS 與 DFS
ChromaOracle 也支援 DFS（深度優先搜尋）作為備選演算法。DFS 運作方式不同:它不是逐層探索,而是沿著一條路徑盡可能深入,然後回溯。
權衡是:
- BFS 找到最短解,但佔用更多記憶體,因為它必須同時儲存當前深度層級的所有狀態。
- DFS 在很多情況下更快地找到一個解,佔用更少記憶體,但這個解未必最短。它回傳的是它撞上的第一條合法路徑,可能比必要的長很多。
對大多數玩家來說,BFS 是正確選擇——你想要最少的步數。DFS 適用於「只要任何解就行,要快」的情況,或者謎題大到 BFS 記憶體不夠的時候。
神秘模式如何運作
ChromaOracle 最與眾不同的功能之一是神秘模式,專為含有隱藏或未知顏色的謎題設計。在許多謎題遊戲中,某些試管位置顯示問號而不是顏色,真正的顏色只在那一層成為試管頂層時才被揭示。
ChromaOracle 透過排列分析來處理這一問題:
- 求解器識別所有標記為未知的位置。
- 它生成所有可能的顏色賦值方案——每種顏色必須以正確的次數出現——也就是與謎題規則一致的全部賦值方式。
- 它使用 BFS 獨立求解每個由此產生的謎題。
- 它分析所有解集,找出無論隱藏顏色實際是什麼都安全的移動。
這被稱為找到「公共前綴」——在所有可能顏色賦值的解中、出現在序列開頭的最長移動子序列。這些移動無論未知項揭示出什麼都保證正確。
這種做法把「不確定性問題」轉化成了「窮舉分析問題」。求解器不靠猜測,而是考慮每一種可能,告訴你哪些移動是無風險的。
效能與實際限制
顏色分類謎題的狀態空間隨試管和顏色數量呈指數增長。一個有五種顏色的簡單謎題可能有幾千個可達狀態。一個有十二種顏色的複雜謎題可能有數百萬個。
ChromaOracle 完全在你的瀏覽器中使用 TypeScript 運行。對大多數謎題——大約十種顏色以內——BFS 在一秒內完成。更大的謎題可能需要幾秒。極大的配置可能超出瀏覽器記憶體限制,這時 DFS 就成了更好的選擇。
求解器是純計算,沒有任何網路呼叫。你的謎題資料從不離開你的裝置,求解速度只取決於你裝置的處理能力。
引擎架構
對技術實現感興趣的讀者,ChromaOracle 的求解器引擎被組織成幾個聚焦的模組:
- Container（容器） —— 把單個試管表示為一個顏色堆疊,處理 push、pop 和頂色查詢。
- Collection（集合） —— 表示完整棋盤,生成當前狀態下所有合法移動,並產生用於去重的規範鍵。
- Search（搜尋） —— 實作 BFS 和 DFS,管理佇列或堆疊以及已訪問狀態的集合。
- Strategy（策略） —— 協調多解分析,找出所有解並為神秘模式計算公共前綴。
- Validation（驗證） —— 在求解開始前檢查謎題配置是否良構。
引擎沒有任何框架依賴。它是純 TypeScript,可獨立測試,可移植到任何 JavaScript 執行時。
常見問題
為什麼 ChromaOracle 在某些謎題上需要更長時間?
求解時間取決於狀態空間的大小,而狀態空間由顏色數、試管數和空位數共同決定。顏色越多、空試管越少,可探索的狀態就越多。一個有十二種顏色、只有一個空試管的謎題,其狀態空間遠大於一個有四種顏色、三個空試管的謎題。
求解器會找不到解嗎?
如果解存在,BFS 總能找到它。如果 BFS 在沒有找到解的情況下完成,這個謎題在數學上無解——沒有任何合法移動序列能到達目標狀態。ChromaOracle 會清楚地報告這一點,讓你知道謎題是不可能的,而不僅僅是難。
BFS 的解一定是最佳的嗎?
是的。BFS 保證給出移動步數最少的解。不存在比 BFS 回傳的解更少步數的合法解。這是演算法的數學性質。
神秘模式如何知道哪些移動是安全的?
神秘模式為隱藏顏色的每一種可能賦值都求解一遍謎題,然後比較所有解。一個移動只有在每一種可能的最佳解中都出現時,才被標記為安全。這意味著這一步無論隱藏顏色是什麼都正確。