一個有效解決日本益智遊戲「發現小花」的演算法

Abstract

日本益智遊戲「發現小花」是風行於日本與荷蘭的邏輯遊戲之一，而「該謎題是否能解」是一個難以回答的問題，甚至是一個非決定性多項式時間-完全（NP-complete）問題。目前已有一些相關論文提出，有的是利用基因演算法解決，但是可能造成錯誤的答案出現；而有的是利用深先搜尋演算法，該演算法是一種暴力搜尋法，所以執行速度很慢；因此，在這篇論文裡，我們想要提出一種演算法來盡可能快速的解決所有謎題，這個演算法不只加速了深先搜尋法的速度，更確保了謎題解答的正確性。在這個遊戲裡，很多謎題是緊密而連續的圖形，我們可因此推導出一些邏輯規則，按照這些規則去填出那些可以馬上決定位置的格子；然而，並非所有謎題都可以依邏輯規則完全解出，像是有些隨意產生的謎題需要另一種方法來輔助，在這種情況下，我們使用深先搜尋演算法，但為了加快執行速度，分支界限法的觀念被引進，其目的是提早終止那些不合法的路徑。實驗的結果顯示，我們的演算法成功地解決日本益智遊戲「發現小花」，而執行速度也比一般的深先搜尋法來得快速。

Japanese puzzle is one of logical games popular in Japan and Netherlands. The question “Is this puzzle solvable?” is difficult to answer, even is an NP-complete problem. At present, there have been some related papers proposed. Some use genetic algorithm (GA), but the solution may be wrong. Some use depth first search (DFS) algorithm. The DFS algorithm is an exhaustive search, so the execution speed is slow. Hence, in this thesis, we want to propose an algorithm to solve puzzles as quickly as possible. The algorithm not only accelerates the speed of DFS but also ensures the correctness of the solution of a puzzle. In this puzzle game, many puzzles are compact and contiguous pictures. Based on this, we can deduce some logical rules, and use these rules to paint those cells whose positions can be determined immediately. However, not all puzzles can be solved completely by logical rules. In this situation, we use the DFS algorithm to complete the puzzle solving. In order to speed up the process, the “branch and bound” technique is used to do early termination for those impossible paths. Experimental results show that our algorithm can solve Japanese puzzles successfully, and the processing speed is significantly faster than that of DFS.