Browsing by Author "Chen, Shiuan-Yi"

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