什麼是 nonogram
看 wikipedia 這張圖應該就很清楚了。nonogram 是個單人用紙筆玩的邏輯遊戲，題目是一個 m*n 大小的方格及左邊跟上面的數字，遊戲目的是根據這些數字提示，解出中間的圖形來。數字表示黑色色塊的數量，譬如第五橫列的 3 3 4 表示那一列中，由左至右有連續 3 個黑色，之後又有 3 個黑色，之後又有 4 個黑色。連續的黑色色塊之間至少有一個白色隔開。
很容易能理解，nonogram 出題很簡單，隨便畫出中間的圖，算出旁邊的數字就是一題，但 nonogram 的題目隨便出的話，很容易有不止一組解，也很可能難以解出。就像 sudoku 一樣，人們在設計 nonogram 題目時，常會要求要能夠用邏輯推理解題，而且只有唯一解才是好題目。
Nonogram 這種 puzzle 似乎沒有統一的名字，只有各公司給的產品名稱，因為商標的關係，很多公司推出 nonogram 的遊戲時會另外再取名字。因此 nonogram 有超過十幾種稱呼，除了 nonogram 之外，常見的稱呼還有 Griddler、Picross、Paint by Numbers、甚至有的人直接用 "Japanese Puzzles" 來稱呼 nonogram。nonogram 也沒有統一的中文譯名。
相似或相關的問題
Nonogram 是黑白、2D、矩形的盤面。有許多類似的 puzzle 是用一樣的玩法規則，但加一些變化。譬如變成彩色(Picross)、變成3D(Picross 3D)、或變成六角形(Triddlers)。也有一種玩法是數字提示只給總合，不像 nonogram 會給出每一段的長度。
值得一提的是最後這種變形，學術上叫做 Discrete Tomography，是 Tomography 的特例。Tomography 是醫學或一些應用科學實際會遇到的問題，有相當多的研究。譬如用 X 光照相，根據陰影的濃度大概可以知道穿過多厚的東西，如何從不同方向照的相片，反推出被照物體的 3D 結構。
nonogram 的人類解法
一般的解法都是一次以一直行或一橫列，只看該行或該列，利用數字提示加上已知部分的黑或白，通過邏輯推理求出更多的色塊。也可以用試誤法、窮舉法等比較暴力的解法。會需要一次觀察多行/列才能解的題目算是難度相當高的。
很多網站的解法教學都只講了最基本的，剩下就讓人自行領略 en.wikipedia 算是把這些基本方法列得比較詳細的。很少看到網站介紹比較進階的解法，推薦 webpbn 的這篇 Advanced Puzzle Solving Techniques。
nonogram 的難度
一般在報紙或書本上的 nonogram 題目，為了畫出好看的圖形、為了讓人解得出來，其實都不會太難。若是整個盤面隨機填黑白色塊，不限一定要用邏輯推理來解題，難度就會高非常多。也就是說，盤面的大小跟難度不一定有關係，雜誌上的 80x80 盤面可能很簡單，30x30的 random 盤面可能就很難，用電腦解可能要數分鐘、小時、甚至更久。
在 1996 年，有論文證明了 nonogram 是 NP-complete 問題。在該論文中，也同時證明了，如果已知 nonogram 的其中一組解，求是否有第二組解，也是 NP-complete 問題。
哪裡可以玩 nonogram
有許多網站可以玩 nonogram，其中我最推薦的是 http://webpbn.com/ 這個網站。與其他網站相比，他有這些優點：
- 免費
- 只要瀏覽器(javascript)就能玩，不用裝 flash 或是 java plugin
- 遊戲操作介面良好。滑鼠左右鍵可設定，支援鍵盤快速鍵，還有 undo、redo、save，還有貼心的顏色提示(不喜歡可以關掉)。
- 題目是人出的，而不是程式 random 出題。網站上也有 quality、difficulty 標示，還能對題目寫 comment。
用程式解 nonogram
事實上網路上有不少人寫過 nonogram solver，但大多只能解簡單的題目。目前有公開程式最強的 solver 應該是 webpbn 網站作者 Jan Wolter 寫的 pbnsolve。Jan 也寫了一篇詳細的 solver survey 比較各 solver。也有一些論文在討論如何解 nonogram，我大概整理成一個列表，有空的話我會寫篇文章聊聊我看那些論文的心得。
nonogram 程式比賽
ICGA、TAAI、TCGA 這幾個單位每年都會舉辦棋牌類的電腦程式比賽，像是象棋、圍棋、西洋棋、六子棋、暗棋等，最近幾年也加入了 puzzle 項目。從 2010 年開始有 nonogram 程式的比賽。比賽方式是比賽雙方事先出好題目，交換讓對方解，解得多的獲勝。老實說我覺得用對奕的方式比較 puzzle 輸贏是很奇怪的事。不過這比賽才兩年，也許賽制、形式還會再調整。
今年六月 TCGA 辦的比賽我有參加，也許是這比賽知道的人不多，參賽者還太少，我覺得參賽的程式(包括我自己的)都還比 pbnsolve 弱很多。
沒有留言 :
張貼留言