Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106422
Title: Nonogram解題方法之研究與實作
The Study and Implementation of the Methods for Solving Nonogram Puzzles
Authors: 林順喜
Lin, Shun-Shii
陳璿伊
Chen, Shiuan-Yi
Keywords: 以數繪畫
約束滿足問題
NP完全
回溯法
隨機重啟爬山法
Nonogram
Constraint satisfaction problem
NP-complete
Backtracking
Random-restart hill climbing
Issue Date: 2016
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.
URI: http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=%22http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22G060347042S%22.&%22.id.&
http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106422
Other Identifiers: G060347042S
Appears in Collections:學位論文

Files in This Item:
File SizeFormat 
060347042s01.pdf2.48 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.