漫談nonogram - kcwu

我本來想寫兩篇文章，一篇寫我survey nonogram 的心得，一篇寫我自己的nonogram solver 用到的演算法跟技巧。

後來想想，決定先寫這篇一般性的介紹。

2011年8月27日星期六 漫談nonogram 我本來想寫兩篇文章，一篇寫我surveynonogram的心得，一篇寫我自己的nonogramsolver用到的演算法跟技巧。

後來想想，決定先寫這篇一般性的介紹。

什麼是nonogram 看wikipedia這張圖應該就很清楚了。

nonogram是個單人用紙筆玩的邏輯遊戲，題目是一個m*n大小的方格及左邊跟上面的數字，遊戲目的是根據這些數字提示，解出中間的圖形來。

數字表示黑色色塊的數量，譬如第五橫列的334表示那一列中，由左至右有連續3個黑色，之後又有3個黑色，之後又有 4個黑色。

連續的黑色色塊之間至少有一個白色隔開。

很容易能理解，nonogram出題很簡單，隨便畫出中間的圖，算出旁邊的數字就是一題，但nonogram的題目隨便出的話，很容易有不止一組解，也很可能難以解出。

就像sudoku一樣，人們在設計nonogram題目時，常會要求要能夠用邏輯推理解題，而且只有唯一解才是好題目。

Nonogram這種puzzle似乎沒有統一的名字，只有各公司給的產品名稱，因為商標的關係，很多公司推出nonogram的遊戲時會另外再取名字。

因此nonogram有超過十幾種稱呼，除了nonogram之外，常見的稱呼還有 Griddler、Picross、PaintbyNumbers、甚至有的人直接用"JapanesePuzzles"來稱呼nonogram。

nonogram也沒有統一的中文譯名。

相似或相關的問題 Nonogram是黑白、2D、矩形的盤面。

有許多類似的puzzle是用一樣的玩法規則，但加一些變化。

譬如變成彩色(Picross)、變成3D(Picross3D)、或變成六角形(Triddlers)。

也有一種玩法是數字提示只給總合，不像nonogram會給出每一段的長度。

值得一提的是最後這種變形，學術上叫做DiscreteTomography，是 Tomography 的特例。

Tomography是醫學或一些應用科學實際會遇到的問題，有相當多的研究。

譬如用X光照相，根據陰影的濃度大概可以知道穿過多厚的東西，如何從不同方向照的相片，反推出被照物體的3D結構。

nonogram的人類解法 一般的解法都是一次以一直行或一橫列，只看該行或該列，利用數字提示加上已知部分的黑或白，通過邏輯推理求出更多的色塊。

也可以用試誤法、窮舉法等比較暴力的解法。

會需要一次觀察多行/列才能解的題目算是難度相當高的。

很多網站的解法教學都只講了最基本的，剩下就讓人自行領略en.wikipedia 算是把這些基本方法列得比較詳細的。

很少看到網站介紹比較進階的解法，推薦webpbn的這篇 AdvancedPuzzleSolvingTechniques。

nonogram的難度 一般在報紙或書本上的nonogram題目，為了畫出好看的圖形、為了讓人解得出來，其實都不會太難。

若是整個盤面隨機填黑白色塊，不限一定要用邏輯推理來解題，難度就會高非常多。

也就是說，盤面的大小跟難度不一定有關係，雜誌上的80x80盤面可能很簡單，30x30的random盤面可能就很難，用電腦解可能要數分鐘、小時、甚至更久。

在1996年，有論文證明了nonogram是NP-complete問題。

在該論文中，也同時證明了，如果已知nonogram的其中一組解，求是否有第二組解，也是NP-complete問題。

哪裡可以玩nonogram 有許多網站可以玩nonogram，其中我最推薦的是 http://webpbn.com/ 這個網站。

與其他網站相比，他有這些優點： 免費 只要瀏覽器(javascript)就能玩，不用裝flash或是javaplugin 遊戲操作介面良好。

滑鼠左右鍵可設定，支援鍵盤快速鍵，還有undo、redo、save，還有貼心的顏色提示(不喜歡可以關掉)。

題目是人出的，而不是程式random出題。

網站上也有quality、difficulty標示，還能對題目寫comment。

在Android/iOS上也有app可以玩nonogram，只是手機上不易操作，可能還是在pad之類螢幕比較大的裝置比較適合。

用程式解nonogram 事實上網路上有不少人寫過nonogramsolver，但大多只能解簡單的題目。

目前有公開程式最強的solver應該是webpbn網站作者JanWolter寫的pbnsolve。

Jan也寫了一篇詳細的solversurvey 比較各solver。

也有一些論文在討論如何解nonogram，我大概整理成一個列表，有空的話我會寫篇文章聊聊我看那些論文的心得。

nonogram程式比賽 ICGA、TAAI、TCGA這幾個單位每年都會舉辦棋牌類的電腦程式比賽，像是象棋、圍棋、西洋棋、六子棋、暗棋等，最近幾年也加入了puzzle項目。

從2010年開始有nonogram程式的比賽。

比賽方式是比賽雙方事先出好題目，交換讓對方解，解得多的獲勝。

老實說我覺得用對奕的方式比較 puzzle 輸贏是很奇怪的事。

不過這比賽才兩年，也許賽制、形式還會再調整。

今年六月TCGA辦的比賽我有參加，也許是這比賽知道的人不多，參賽者還太少，我覺得參賽的程式(包括我自己的)都還比pbnsolve弱很多。

張貼者： kcwu 於 8月27,2011 以電子郵件傳送這篇文章 BlogThis！ 分享至Twitter 分享至Facebook 標籤： nonogram , puzzle 沒有留言 : 張貼留言 較新的文章 較舊的文章 首頁 訂閱： 張貼留言 ( Atom ) 熱門文章 漫談nonogram OSMvectormap-mapsforge 用hugin接合多張掃描圖檔(更新) TheC++ProgrammingLanguage國際中文版第四版勘誤 FreeBSD單機使用光世代多個IP 如何在網頁上放OpenStreetMap及GPX軌跡 OpenStreetMap登山踏查 nonogram漫談-2 鷹仔尖,觀音山硬漢嶺 我在用的AndroidApps 網誌存檔 ►  2017 ( 1 ) ►  六月 ( 1 ) ►  2015 ( 4 ) ►  七月 ( 1 ) ►  六月 ( 2 ) ►  一月 ( 1 ) ►  2014 ( 1 ) ►  一月 ( 1 ) ►  2013 ( 3 ) ►  六月 ( 1 ) ►  五月 ( 1 ) ►  四月 ( 1 ) ►  2012 ( 1 ) ►  一月 ( 1 ) ▼  2011 ( 1 ) ▼  八月 ( 1 ) 漫談nonogram ►  2010 ( 3 ) ►  十二月 ( 2 ) ►  二月 ( 1 ) ►  2008 ( 2 ) ►  十二月 ( 1 ) ►  二月 ( 1 ) ►  2007 ( 1 ) ►  十二月 ( 1 )