Nonogram解題方法之研究與實作

The Study and Implementation of the Methods for Solving Nonogram Puzzles

陳璿伊(Chen Shiuan-Yi)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程學系/碩士(2016年)

https://doi.org/10.6345/NTNU202204560

摘要

Nonogram是一種邏輯解謎遊戲，在1987年由日本人西尾徹也發明。Nonogram的基本玩法是會先給定一個空白的網格，其中每一行和每一列都給定一組數字當作提示，玩家需根據這些提示找出線索來選擇填滿或留空格子。Nonogram是一種約束滿足問題（Constraint satisfaction problem），也已經有論文證明是NP-complete問題，對於這些不確定是否能在多項式時間內解決的問題，執行時間和答案的正確性都是研究演算法效率和可靠度的最重要的指標。
目前一些相關論文提出了不同方法來實作，大多傾向於從空白盤面根據提示線索來找尋答案，利用邏輯規則先推導出部分格子的答案，最後再使用Backtracking方法來窮舉求解。本研究提出的解題方法是仿效破解n皇后問題的Random-restart hill climbing作法，先將所有滿足列提示的線段隨機排列，再去移動各線段以滿足所有行提示的限制。若陷入局部最佳解則會重啟盤面，再由另一種起始盤面來移動線段，找出滿足所有行提示的盤面。

關鍵字

以數繪畫 ； 約束滿足問題 ； NP完全 ； 回溯法 ； 隨機重啟爬山法

並列摘要

Nonogram is a logic puzzle game, invented in 1987 by a Japanese named Tetsuya Nishio. The basic method of playing Nonogram puzzle is that, at the beginning a fixed-sized blank board will be given, where each row and each column will be given a set of numbers (clues) as a reminder to the players who need these clues to set or unset the squares. Nonogram is a Constraint satisfaction problem, which has also been proven to be an NP-complete problem. We are uncertain whether it can be solved in polynomial time, but the execution time and the correctness of the answer are the most important indications in the study of efficiency and reliability for designing its algorithms.
At present, some relevant papers have proposed different methods to solve the problem. Most of them tend to find the answer based on the prompted clues from a blank board using the logic rules to deduce the set/unset states to part of the squares, and finally using the Backtracking method to solve all the squares exhaustively. Problem-solving approach proposed in this study is to follow the example of n queens problem using Random-restart hill climbing method. First of all, we randomly arrange all lines so that they meet the requirements of all the row clues. Then we randomly select a line and horizontally move it to a new position in order to further meet the requirements of the column clues. This process will be repeated many times. If it finally falls into local optimal solution, we will again restart filling the board randomly, and then move the lines to new positions, until we find out a solution that meets the requirements of all the column clues.

並列關鍵字

Nonogram ； Constraint satisfaction problem ； NP-complete ； Backtracking ； Random-restart hill climbing

參考文獻

[1] 尤瓊雪，一個有效解決日本益智遊戲「發現小花」的演算法，國立交通大學資訊科學與工程研究所碩士論文，2007。

[2] 陳建志，進化式演算法於邏輯拼圖之研究，國立屏東教育大學資訊科學系碩士論文，2008。

[3] 葉家郡、黃國展，Nonogram解題加速方法探討，科技部大專學生研究計畫，2014。

[4] I-Chen Wu, Der-Johng Sun, Lung-Ping Chen , Kan-Yueh Chen, Ching-Hua Kuo, Hao-Hua Kang, Hung-Hsuan Lin, “An Efficient Approach to Solving Nonograms,” IEEE Transactions on Computational Intelligence and AI in Games (SCI), 2013.

[5] 張嘉豪、林怡秀，增進Nonogram解題效率人工智慧與演算法之研究與應用，國立臺灣師範大學資訊工程學系專題，2016。