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