Microsoft Word - paper_v6.doc

Transcription

1 資訊科學與工程研究所 碩士論文 一個有效解決日本益智遊戲 發現小花 的演算法 An Effcent Algorthm for Solvng Japanese Puzzles 研究生 : 尤瓊雪 指導教授 : 陳玲慧教授 中華民國九十六年一月

2 一個有效解決日本益智遊戲 發現小花 的演算法 An Effcent Algorthm for Solvng Japanese Puzzles 研究生 : 尤瓊雪 指導教授 : 陳玲慧 Student :Chung-Hsueh Yu Advsor:Lng-Hwe Chen 國立交通大學資訊科學與工程研究所碩士論文 A Thess Submtted to Insttute of Computer Scence and Engneerng College of Computer Scence Natonal Chao Tung Unversty n Partal Fulfllment of the Requrements for the Degree of Master n Computer Scence January 007 Hsnchu, Tawan, Republc of Chna 中華民國九十六年一月

3 一個有效解決日本益智遊戲 發現小花 的演算法 研究生 : 尤瓊雪 指導教授 : 陳玲慧博士 國立交通大學資訊科學與工程研究所碩士班 摘要 日本益智遊戲 發現小花 是風行於日本與荷蘭的邏輯遊戲之一, 而 該謎題是否能解 是一個難以回答的問題, 甚至是一個非決定性多項式時間 - 完全 (NP-complete) 問題 目前已有一些相關論文提出, 有的是利用基因演算法解決, 但是可能造成錯誤的答案出現 ; 而有的是利用深先搜尋演算法, 該演算法是一種暴力搜尋法, 所以執行速度很慢 ; 因此, 在這篇論文裡, 我們想要提出一種演算法來盡可能快速的解決所有謎題, 這個演算法不只加速了深先搜尋法的速度, 更確保了謎題解答的正確性 在這個遊戲裡, 很多謎題是緊密而連續的圖形, 我們可因此推導出一些邏輯規則, 按照這些規則去填出那些可以馬上決定位置的格子 ; 然而, 並非所有謎題都可以依邏輯規則完全解出, 像是有些隨意產生的謎題需要另一種方法來輔助, 在這種情況下, 我們使用深先搜尋演算法, 但為了加快執行速度, 分支界限法的觀念被引進, 其目的是提早終止那些不合法的路徑 實驗的結果顯示, 我們的演算法成功地解決日本益智遊戲 發現小花, 而執行速度也比一般的深先搜尋法來得快速 I

4 An Effcent Algorthm for Solvng Japanese Puzzles Student: Chung-Hsueh Yu Advsor: Dr. Lng-Hwe Chen Insttute of Computer Scence and Engneerng Natonal Chao Tung Unversty ABSTRACT Japanese puzzle s one of logcal games popular n Japan and Netherlands. The queston Is ths puzzle solvable? s dffcult to answer, even s an NP-complete problem. At present, there have been some related papers proposed. Some use genetc algorthm (GA), but the soluton may be wrong. Some use depth frst search (DFS) algorthm. The DFS algorthm s an exhaustve search, so the executon speed s slow. Hence, n ths thess, we want to propose an algorthm to solve puzzles as quckly as possble. The algorthm not only accelerates the speed of DFS but also ensures the correctness of the soluton of a puzzle. In ths puzzle game, many puzzles are compact and contguous pctures. Based on ths, we can deduce some logcal rules, and use these rules to pant those cells whose postons can be determned mmedately. However, not all puzzles can be solved completely by logcal rules. In ths stuaton, we use the DFS algorthm to complete the puzzle solvng. In order to speed up the process, the branch and bound technque s used to do early termnaton for those mpossble paths. Expermental results show that our algorthm can solve Japanese puzzles successfully, and the processng speed s sgnfcantly faster than that of DFS. II

5 誌謝 這篇論文的完成, 首先要感謝指導教授陳玲慧博士讓我加入自動化資訊處理實驗室的研究群, 並且在這兩年多來不斷的細心指導, 不管是在學業上或是生活上, 老師的提醒 包容與體諒, 都帶給了我不少的助益, 在此, 再次謝謝老師 此外, 感謝口試委員蔡月霞教授 陳佑冠教授以及何俊達教授於口試中給予的指導與建議, 才能使這篇論文更加完善 接著要謝謝實驗室一起研究的可愛伙伴們 : 民全 萓聖 惠龍和文超四位學長, 以及維中 芳如 佩瑩 立人 俊旻 信嘉 薰瑩 子翔和偉全九位學弟妹 ; 不管是在研究上給我的指導與叮嚀, 或是在日常生活上製造的有趣話題, 還有經歷過實驗室一些大大小小的事情後, 那股仍不曾改變的向心力與凝聚力 ; 如果沒有你們, 我想我的研究生活一定會少了很多樂趣與知識的增長 此外, 要謝謝我的大學同學和室友們 : 阿信 建凱 阿福 小美 狼鼠 薇安 綿等等, 讓我在沒有實驗室同屆同學的狀況下, 能夠有人可以一起作伴, 不管是課業上的互相討論, 或是生活上的談心笑鬧, 謝謝你們聽我說話 幫我打氣, 陪我度過一些心理上的波折 最後, 當然要謝謝我的家人 : 媽媽及哥哥們 謝謝你們對我沒能如期畢業的寬容, 還盡可能的提供我經濟上的支出, 更謝謝媽媽長期當我的傾聽者 ; 另外, 也謝謝每天都來迎接我回家的噹噹 能和你們成為一家人, 是我這輩子感到最幸運且最幸福的事, 謹以此篇論文獻給你們, 也獻給所有我關心以及關心我的人 III

6 CONTENTS ABSTRACT (IN CHINESE)... I ABSTRACT... II ACKNOWLEDGE (IN CHINESE)...III CONTENTS...IV LIST OF FIGURES...V LIST OF TABLES... VII CHAPTER INTRODUCTION.... Motvaton.... Japanese Puzzles.... Prevous Works....4 Organzaton of the Thess...5 CHAPTER PROPOSED METHOD...6. The frst phase: Logcal rules (LR)...7. The second phase: DFS wth branch and bound... CHAPTER EXPERIMENTAL RESULTS...6 CHAPTER 4 CONCLUSIONS... CHAPTER 5 FUTURE WORKS... REFERENCES... IV

7 LIST OF FIGURES Fg.. Japanese puzzle. (a) A smple puzzle. (b) The soluton of (a)... Fg.. A puzzle wth two solutons... Fg.. A puzzle wth no soluton.... Fg..4 DT problem and Japanese puzzle. (a) DT problem. (b) Japanese puzzle... Fg..5 A puzzle problem...4 Fg..6 The DFS tree of Fg Fg..7 Sx possble solutons n the DFS tree...4 Fg..8 Verfcaton process for the dfferent cases....5 Fg.. The flowchart of the proposed method...6 Fg.. An llustraton of range. (a) A specal row of a puzzle. (b) The left-most case of (a). (c) The rght-most case of (a)...9 Fg.. An example of Rule...0 Fg..4 An example of Rule.. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule. to (a)....0 Fg..5 An example of Rule.. (a) One row of a puzzle wth a partal pantng result. (b) The cell c r belongs to the thrd black run wth length one. (c) The cell c r s the head cell of the last black run... Fg..6 An example of Rule.4. (a) One row of a puzzle wth a partal pantng result ( maxl =). (b) The new black segment s length after colorng c s 4. (c) The cell c should be left empty... Fg..7 An example of Rule.5. (a) Top: one row of a puzzle wth a partal pantng result. Mddle: all possble solutons for c. Bottom: the result of applyng Rule.5 to top fgure. (b) Top: a specal case (all black runs contanng c have the same length). Bottom: the result of applyng Rule.5 to top fgure....4 Fg..8 An example of Rule...6 Fg..9 An example of Rule.. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule. to (a)....6 Fg..0 An example of Rule.. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule. to (a)....7 Fg.. An example of Rule.-. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule.- to (a)....9 Fg.. An example of Rule.-. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule.- to (a)....9 V

8 Fg.. An example of Rule.-. (a) One row of a puzzle wth a partal pantng result. (b) The length of colorng those cells between c and c s 5. (c) The result of applyng Rule.- to (a)...0 Fg..4 An example of DFS. (a) A gven puzzle. (b) The possble solutons of row. (c) The possble solutons of row. (d) A rough tree of (a)... Fg..5 The process of DFS wth branch and bound. (a) The deduced result of row based on the frst possble soluton of row. (b) The deduced result of row based on the second possble soluton of row. (c) The deduced result of row based on the thrd possble soluton of row. (d) The frst possble soluton of row correspondng to (c). (e) The fnal soluton...4 Fg..6 An example before usng DFS. (a) The orgnal puzzle. (b) The resultng puzzle executed by LR...5 s e Fg.. Test mages. (a) Sheep (5x5). (b) Arplane (5x5). (c) Random_ (0x0). (d) Monkey (5x5). (e) Sunflower (5x5). (f) Random_ (0x0)...7 Fg.. An llustraton of scatterng. (a) 0 possble solutons. (b) possble solutons. (c) 6 possble solutons. (d) 56 possble solutons...7 Fg.. An llustraton of chan relaton. More means the puzzle s more connected. (a) The magnfed pcture of part of Fg.. (c). (b) The magnfed pcture of part of Fg.. (f)...8 Fg..4 A 7x8 puzzle wth many solutons. (a) The result after LR. (b) The frst soluton. (c) The second soluton....8 Fg..5 A puzzle wth no soluton....9 Fg..6 GA gves a wrong answer of Fg Fg..7 Test mages. (a) Flower_word (0x0). (b) Hppo (0x0). (c) Formosa (5x5). (d) Snoopy (5x5). (e) Owl (0x5). (f) Skatng (0x5)....9 Fg. 5. Generator. (a) The nput mage. (b) The puzzle generated. (c) The result of the puzzle.... VI

9 LIST OF TABLES Table The comparson of the expermental results between surveyed paper and our Table algorthm...0 VII

10 CHAPTER INTRODUCTION. Motvaton Japanese puzzle, also known as nonogram, s one of logcal games popular n Japan and Netherlands. The game s recommended to Tawan recently, but few papers are concerned wth ths topc Japanese nonograms. In addton, some related papers solved ths problem by non-logcal algorthms, and the executon speed s slow. On the other hand, the queston Is ths puzzle solvable? turns out to be very hard to answer n general, even s a NP-complete problem [-]. In ths thess, we wll present a fast method to solve ths problem. Frst, we wll provde some logcal rules to solve most part of a puzzle, and then use DFS wth branch and bound scheme to solve the remanng part. The detal of our proposed method wll be descrbed n Chapter.. Japanese Puzzles Japanese puzzles wll be descrbed n ths secton. Fg.. (a) s a smple puzzle and Fg.. (b) s the soluton of Fg.. (a). Ignorng the numbers, the soluton can be consdered as a black-whte (-and-0) pcture. Here, we use as a colored (black) cell, as an empty (whte) cell, and as an unknown cell (.e. an undetermned cell). The postve ntegers alongsde the rows and columns gve the nformaton about the lengths of black runs (a black run: contguous black cells) n that row or column respectvely. The goal s to pant the cells to form a pcture that satsfes the followng constrants:

11 . Each cell must be colored (black) or left empty (whte).. If a row or column has k numbers: s, s,, s k, then t must contan k black runs the frst (leftmost for rows / topmost for columns) black run wth the length s, the second black run wth the length s, and so on.. There should be at least one empty cell between two consecutve black runs. (a) (b) Fg.. Japanese puzzle. (a) A smple puzzle. (b) The soluton of (a). It s evdent that the puzzle n Fg.. (a) has a unque soluton. However, the puzzle n Fg.. has two solutons, and the puzzle n Fg.. has no soluton (.e. no correspondng pcture). Hence, there may be no, exact one, or more than one soluton for gven ntegral numbers. 5 Fg.. A puzzle wth two solutons. Fg.. A puzzle wth no soluton.. Prevous Works In 004, Batenburg [] descrbed an evolutonary algorthm for dscrete tomography (DT). And then Batenburg Kosters [4] provded a method to solve Japanese puzzle. By modfyng the ftness functon n [], the evolutonary algorthm

12 can be used to solve Japanese puzzle. DT s concerned wth the reconstructon of a dscrete mage from ts proectons [4]. Japanese puzzles can be consdered as a specal form of the DT problem. Fg..4 shows an example to explan the dfference between them. Snce the evolutonary algorthm n [] wll converge to a local optmum, the obtaned soluton may be ncorrect. (a) (b) Fg..4 DT problem and Japanese puzzle. (a) DT problem. (b) Japanese puzzle. In 004, Wggers [4] proposed a genetc algorthm (GA) and a depth frst search (DFS) algorthm to solve Japanese puzzles. He also compared the performance of these two algorthms. For a puzzle of small sze, DFS algorthm s faster than GA; otherwse, GA s faster. However, both methods are slow. In the followng, we wll gve a bref descrpton for the DFS algorthm, snce t wll also be used n our proposed method. [Depth Frst Search (DFS)] It s a straghtforward dea to solve the Japanese nonogram by DFS. The author generates all possble solutons of each row. Takng Fg..5 as an example, Fg..6 s ts correspondng DFS tree and Fg..7 shows all possble solutons n the tree. Each possble soluton corresponds to a path from root to a leaf node, fnd all paths usng DFS and then use the column nformaton of the puzzle to verfy each possble soluton. A possble soluton wll be consdered as a true soluton, f t satsfes all

13 columns restrctons. Fg..8 (c) s the only correct soluton after the verfcaton process. Note that the symbol X n Fg..8 stands for the column s restrcton not satsfed. Fg..5 A puzzle problem. row ( possble solutons) row ( possble solutons) row ( possble soluton) possble solutons: (a) (b) (c) (d) (e) (f) Fg..6 The DFS tree of Fg..5. (a) (b) (c) (d) (e) (f) Fg..7 Sx possble solutons n the DFS tree. 4

14 X X X X X X X (a) (b) (c) X X X X X X X X X X X X X (d) (e) (f) Fg..8 Verfcaton process for the dfferent cases. Whether the evolutonary algorthm presented n [4] or the genetc algorthm (GA) descrbed n [5], both of them wll converge to a local optmum, so sometmes the obtaned soluton may not be correct. Besdes, the depth frst search (DFS) algorthm proposed n [5] takes longer tme than GA when solvng large puzzles. However, DFS wll always fnd correct solutons. In ths thess, some logcal rules (LR) are provded to determne the unknown cells n a Japanese puzzle as many as possble, and then DFS s used to solve those remanng unknown cells. In order to speed up the process, the branch and bound technque s used to do early termnaton for those mpossble paths..4 Organzaton of the Thess Ths thess s composed of fve chapters. In Chapter, Japanese puzzles and prevous works are ntroduced. And then, the remander of ths thess s organzed as follows. Our proposed algorthm for solvng Japanese puzzles wll be presented n Chapter. In Chapter, several expermental results wll be shown. Fnally, conclusons and future works wll be gven n the last two chapters. 5

15 CHAPTER PROPOSED METHOD In general Japanese puzzle game, we usually pant those cells whch can be determned mmedately at frst. Then, the rest of undetermned cells wll be solved by guess. Based on ths fact, we wll propose a method to solve Japanese puzzles automatcally. The method contans two phases. In the frst phase, some logcal rules are deduced and used to determne some cells; n the second phase, another method, the depth frst search wll be appled to solve those remanng unknown cells. Furthermore, the branch and bound technque s used to accelerate the searchng speed of the general DFS. These two phases wll be presented n Sectons. and.. Fg.. s the flowchart of the proposed method. The condtons n the decson boxes wll also be descrbed n Secton.. Start Phase Solved by logcal rules (LR) Yes Yes Is any unknown cell determned? Is any black run's range changed? No No End Yes Is the puzzle solved completely? No Phase Solved by DFS wth Branch and bound scheme Fg.. The flowchart of the proposed method. 6

16 . The frst phase: Logcal rules (LR) One may also use some sklls to solve Japanese puzzles, lke the rules descrbed n [6]. In ths phase, eleven rules are proposed but we present a new concept of range of a black run ( range wll be explaned later). These rules can be dvded nto three man parts. The frst part s to determne whch cells should be colored or left empty, the second part s to refne the ranges of black runs, and the thrd s not only to determne whch cells should be colored or left empty but also to refne the ranges of black runs. The frst fve rules belong to part I, the followng three rules belong to part II, and the last three rules belong to part III. Each rule wll be appled n each row and then n each column. The total eleven rules are executed sequentally and teratvely. In the begnnng, all cells n the puzzle are consdered as unknown. In some teratons, some unknown cells wll be determned as colored cells or empty ones. However, n some teratons, maybe only the ranges of some possble black runs are refned. That s, there are not always some unknown cells determned n each teraton. Thus, f no unknown cell s determned and no black run s range s changed, we wll stop usng logcal rules because there wll be no changes n later teratons. Note that, the rules appled n a row are the same as those appled n a column, so we only take a row as an example to explan our algorthm. Prelmnary The poston where a black run may be placed plays an mportant role. An dea about the range ( r, re) of a black run s proposed, where r stands for the left-most startng poston of the run, and r e stands for the rght-most endng poston of the run. That s, black run can only be placed between r and r e. If the range of each black run s precsely estmated, these ranges nformaton can help 7

17 us to solve puzzles quckly. In the begnnng, the ntal range of a black run n a row s set between the left-most possble poston and the rght-most possble poston. For each black run, t must reserve some cells for the former black runs and the later ones. Fg.. shows an example. Fg.. (a) shows a specal row of a puzzle, n ths row, there are three black runs wth lengths,, and, respectvely. Fg.. (b) shows the left-most possble soluton of Fg.. (a) for each run, the frst cell s colored and there s only one empty cell between every two neghborng black runs. Fg.. (c) shows the rght-most possble soluton of Fg.. (a) for each run, the last cell s colored and there s only one empty cell between every two neghborng black runs. Now, we take the second run as an example to do more detal explanaton. In Fg.. (b), the left-most poston, at whch the frst cell of the second black run can start, s the thrd poston. The reason s that there must reserve at least two cells n the head, one cell s reserved for the frst black run and the other s reserved for the empty cell between the frst and second black runs. Smlarly, the rght-most poston, at whch the last cell of the second black run can appear, s the seventh poston. That s due to that there must reserve at least three cells n the tal, two cells are reserved for the thrd black run and one cell s reserved for the empty cell between the second and thrd black runs. Intal run range estmatng We let the sze of each row wth k black runs be n and the cells n a row wth ndex (0, K, n-), we can use the followng formula to determne the ntal range of each black run. Specally, r of the frst black run s ntalzed 0 and r e of the last black run s ntalzed (n- ). 8

18 r r e = - = ( LB = ( n-) - + ), k = + ( LB + ), =, K, k. where LB s the length of black run. Usng the above formula, we can get the ntal ranges of the three black runs n Fg.. (a), whch are (0, ), (, 6), and (6, 9), respectvely. (a) (b) (c) Fg.. An llustraton of range. (a) A specal row of a puzzle. (b) The left-most case of (a). (c) The rght-most case of (a). Part I There are fve rules n ths part, all of them are used to determne whch cells should be colored (black) or left empty (whte). Rule. For each black run, some cells must be colored f all the possble solutons of the black run have the ntersecton. Actually, the ntersecton of all possble solutons s also the ntersecton of the left-most case of the black run and the rght-most case of the black run. It s obvous that the ntersecton exsts when the length of the black run s range s less than two tmes the actual length of a black run. Fg.. s an example. Consequently, we provde Rule. to pant the cells sure to be colored. In the rule, c s the cell wth ndex. 9

19 0 4 Fg.. An example of Rule.. Rule. For each black run, cell c wll be colored when r where u = ( r - r + ) - LB e + u r e -u, Rule. In the begnnng, each cell belongs to one or more than one black run. However, after some teratons, many black runs ranges wll be refned, ths may make some cells not belong to any black run, and these cells should be left empty. Rule. s provded to do ths work. Fg..4 shows that cells c 0 and c 4 should be left empty because they do not belong to any black run. Rule. For each cell c, t wll be left empty, f one of the followng three condtons s satsfed () 0 < r s, () rke < < n, () r < < r for some, < k. e ( + ) s s range s range s range s range (a) (b) Fg..4 An example of Rule.. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule. to (a). 0

20 Rule. For each black run, when the frst cell c r of ts range s colored, we wll check c r covered by what other black runs. If the lengths of those coverng black runs are all one, the cell c r - should be left empty. In the smlar way, when the last cell c r of ts range s colored, we wll check e re c covered by what other black runs. If the lengths of those coverng black runs are all one, the cell c + should be left empty. We provde Rule. to determne whether cells c r - and c + should be r e r e left empty. Takng Fg..5 as an example, the colored cell c r n Fg..5 (a) s the frst cell of the range of the last black run wth length. It s also covered by the thrd black run wth length. Thus, t must be the thrd black run wth length (see Fg..5 (b)) or the head cell of the last black run (see Fg..5 (c)). No matter what case, the cell c r - should be left empty. Rule. For each black run, () If the lengths of all black run cell c r () If the lengths of all black run cell c e - r + =, K, k wll be left empty. wll be left empty. coverng c coverng c r r e wth wth are all one, are all one, (a) (b) (c) s range s range r - r s range s range Fg..5 An example of Rule.. (a) One row of a puzzle wth a partal pantng result. (b) The cell The cell c r c r belongs to the thrd black run wth length one. (c) s the head cell of the last black run.

21 Rule.4 There may be some short black segments exstng n a row. If any two consecutve black segments wth an unknown cell between them are combned nto a new black segment wth length larger than the maxmal length of all black runs contanng part of ths new segment, the unknown cell should be left empty. Rule.4 s provded to deal wth ths stuaton. Fg..6 shows an example. From Fg..6 (b), we can see that by colorng c, the length of the new black segment s 4. Snce the new black segment s covered by two runs wth length and and 4 s larger than, so we set the unknown cell c as empty. Rule.4 For any three consecutve cells c -, c, and c +, =, K, n- Constrant: cells c - and c + must be black, and cell c must be unknown. Let maxl be the maxmal length of all the black runs contanng the three cells.. If we color c and fnd that the length of the black segment contanng larger than maxl, c should be left empty. c s (a) (b) (c) - + s range s range s range 4 Fg..6 An example of Rule.4. (a) One row of a puzzle wth a partal pantng result (maxl =). (b) The new black segment s length after colorng c s 4. (c) The cell c should be left empty.

22 Rule.5 Some empty cells lke walls may obstruct some black segments expand, we want to color more cells based on ths property. For a black segment belongng to seres of black runs, whch have the same length but the ranges of them overlap each other, f the length of the black segment equals to the length of those black runs coverng the black segment, we can set the two cells closest to the black segment as empty. Rule.5 s proposed to solve the above problems. Fg..7 s a detaled descrpton. In Fg..7(a), we do not know c belongng to whch black run. However, an empty cell c - obstructs the black segment contanng c to expand to the left sde of c -. Hence, no matter c belongs to the run wth length or the run wth length 4, the cell next to c should be colored. On the other hand, Fg..7 (b) s a specal case, all black runs contanng c have the same length. Thus, we are qute sure that the two cells c s- and c e+ closest to the black segment should be left empty. Rule.5 For any two consecutve cells c - and c, =, K, n- Constrant: cell c - must be empty or unknown, and cell c must be black. Let mnl be the mnmal length of all the black runs contanng c.. Fnd an empty cell c m closest to c, m = -mnl +, K, - If c m exsts, color cell c p when + p m + mnl.. Fnd an empty cell c n closest to c, n = +, K, + mnl- If c n exsts, color cell c p when n - mnl p If all black runs contanng c have the same length. () Let s and e be the start and end ndces of the black segment contanng c () If e-s + = mnl, leave cells c s- and c e+ empty.

23 s range 4 4 s range m - (a) - s range s range s range s range s- s e e+ (b) Fg..7 An example of Rule.5. (a) Top: one row of a puzzle wth a partal pantng result. Mddle: all possble solutons for c. Bottom: the result of applyng Rule.5 to top fgure. (b) Top: a specal case (all black runs contanng c have the same length). Bottom: the result of applyng Rule.5 to top fgure. Part II Three rules are contaned n ths part. They are desgned to refne the ranges of black runs. Rule. Two consecutve black runs can not have the same r or r e, because t s mpossble that they are placed n the same start poston or end poston. We use Rule. to update the range of each black run when t has the same r wth black run - or the same r e wth black run +. Rule. For each black run, r r e wll be refned to ( r wll be refned to ( r ( -) s + LB - LB - + ), f r -), f r r r ( -) s ( + ) e + e ( + ) e 4

24 Rule. There should be one empty cell between two consecutve black runs, so we should update the range of black run f the cell c r - or c r e + s colored. The cells c r - and c + do not belong to black run because they are not n the r e range r, ). It means that the colored cell must belong to the prevous or the next ( re black run when t s panted. Therefore, Rule. s proposed to solve ths problem. Rule. For each black run, r wll be refned to ( r + ), re wll be refned to ( re -), f f the cell c the cell c r - r e s colored + s colored Rule. In the range of a black run, maybe one or more than one black segment exst. Some of black segments have the lengths larger than LB, but some not. We try to determne each black segment wth length larger than LB belongs to the former black runs or the later ones. If a black segment belongs to both of them, we can not do anythng. But f no, then we update the range of black run. We provde Rule. to do ths work. In Fg..8, the orgnal range of the second black run s (4, ). In the range of the second black run, the length of the frst black segment s whch s larger than, and the black segment belongs to the frst black run not the last, so we update the range of the second black run from (4, ) to (8, ). But the length of the second black segment s and s less than, so we gnore t. 5

25 Rule. For each black run, fnd out all black segments n ( r We denote the class of these black segments by Β., r e ). For each black segment n Β wth start ndex s and end ndex e, If the length ( e -s + ) of black segment s larger than LB, r wll be refned to ( e + ), re wll be refned to ( s - ), f black segment only belongs to the former black runs f black segment only belongs to the later black runs s range s range s range Fg..8 An example of Rule.. Part III Ths part s also composed of three rules. The purpose of each rule s not only to determne whch cells should be colored or left empty but also to refne the ranges of some black runs. Rule. In solvng process, we met a problem as shown n Fg..9 (a) several colored cells belong to the same black run but they are scattered. It means that all cells between them should be colored to form a new black segment. Rule. s presented to solve ths problem and Fg..9 (b) s the result of applyng Rule. to Fg.9 (a). (a) 4 r(- )e m n r(+ )s (b) 4 4 s range (old) 4 s range (new) Fg..9 An example of Rule.. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule. to (a). 6

26 Rule. For each black run, fnd the frst colored cell c m after ( and the last colored cell c n before r -) e. Color all cells between c m and c n r ( + ) s. r wll be refned to ( m-u) re wll be refned to ( n + u) where u = LB - (n - m + ) Rule. As shown n Fg..0 (a), some scattered empty cells are dstrbuted over the range of black run, so there wll be several segments bounded by these empty cells. The lengths of some segments may be less than LB, so they can be gnored to consder. We propose Rule. to solve ths problem. Fg..0 (a) shows that there are sx segments n s range. The frst two and the last segments wll be skpped and then the range s adusted. Snce the length of the forth segment s less than and s covered only by one black run wth length, we can set t as empty. Fg..0 (b) shows the result of applyng Rule. to Fg..0 (a) (a) s range (b) s range Fg..0 An example of Rule.. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule. to (a). 7

27 Rule. For each black run, fnd out all segments bounded by empty cells n ( r We denote the class of these segments by Β wth sze b., r e ). step.set = 0 step. If step.set step 4. If the length of segment s less than LB Otherwse, r wll be refned to the start ndex of stop and go to step. the length of segment s less than LB Otherwse, r = + and go to step. = -and go to step 4. e = b- wll be refned to the end ndex of stop and go to step 5. step 5. If there stll reman some segments wth lengths less than (we denote the class of these segments by R) for each segment n R, segment, segment, f the segment does not belong to other black runs, all cells n ths segment should be left empty.,, LB, Rule. Ths rule s desgned for solvng the case of the range of black run not overlappng the range of black run - or +. We take the case not overlappng black run - as an example, another case not overlappng black run + s treated by the same dea but the condtons are reversed. It wll be explaned at the end of ths secton.. The cell c r s black (see Fg.. (a)) Because the black run does not overlap the black run -, so when the head cell of black run has been colored, we can fnsh ths black run by Rule.-. Fg.. (b) s the result of applyng Rule.- to Fg.. (a). 8

28 Rule.- For each black run wth c colored, and ts range not overlappng the range of black run -, () Color cell c when r + r () r should be refned to ( r + LB e + LB -and leave cell c -) () If black run + overlaps black run orgnally, r( + ) s should be refned to ( r + LB + ) r r + LB empty (a) 4 r r + LB 4 s range (b) 4 4 s range Fg.. An example of Rule.-. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule.- to (a).. An empty cell c w appears after a black cell c b (see Fg.. (a)) It should be true that each cell after c w wll not belong to black run. Thus, we can use Rule.- to refne the range of black run as shown n Fg.. (b). (a) b w (b) s range s range Fg.. An example of Rule.-. (a) One row of a puzzle wth a partal pantng result. (b) The result of applyng Rule.- to (a). Rule.- For each black run wth ts range not overlappng the range of black run -, Constrant: an empty cell c w appears after a black cell Constrant: range of black run r e wll be refned to (w-) c b wth c w and c b n the 9

29 . There s more than one black segment n the range (see Fg.. (a)) In r, ) ( re, we fnd the frst black cell c s n the frst black segment and the frst black cell c e n the second black segment. If the length of the new run after mergng the frst and second black segments by colorng those cells between these two cells s larger than LB, ths means that c e wll not belong to the same run as c s. Otherwse, we proceed to fnd the frst black cell c e n the thrd black segment and also check the length of the new run after mergng the frst and thrd black segments. The process starts all over agan untl all black segments n r, ) have ( re been checked or a black segment has been found and the length after mergng the frst black segment and black segment s larger than LB. Thus we provde Rule.- to deal wth ths stuaton. The length after mergng two black runs shown n Fg.. (a) s 5 (see Fg..(b)) and s larger than 4, thus we can update the range as shown n Fg.. (c). (a) 4 s e (b) (c) s range 5 4 s range Fg.. An example of Rule.-. (a) One row of a puzzle wth a partal pantng result. (b) The length of colorng those cells between c s and c e s 5. (c) The result of applyng Rule.- to (a). 0

30 Rule.- For each black run wth ts range not overlappng the range of black run -, Constrant: there s more than one black segment n the range Fnd out all black segments n r, ). ( re We denote the class of these black segments by Β wth sze b. step. set =0 step. fnd the frst black cell step. set m = + step 4. f c s n black segment m < b, fnd the frst black cell c e n black segment m, If ( e-s +) s larger than LB, stop and r e wll be refned to (e-). Otherwse, m = m + and go to step 4. The above three condtons are sutable for the case not overlappng black run -. To treat the case not overlappng black run +, we ust need to reverse the above three condtons as follows:.the cell c () Color cell r e s black c when r e - LB + r -and leave cell c () r should be refned to ( re - LB + ) () If black run -overlaps black run orgnally, r( -) e should be refned to ( re - LB -). An empty cell cw appears before a black cell cb () r wll be refned to ( w + ).There s more than one black segment n the range the last black cell cs n the last black segment the last black cell ce n the other black segments () If ( s-e + ) s larger LB, r wll be refned to ( e + ) e r -LB e empty

31 . The second phase: DFS wth branch and bound After the frst phase, a puzzle s not always solved completely. If some cells n the puzzle are stll unknown, we wll enter the second phase. Depth frst search (DFS) s an exhaustve search, thus t wll fnd out the soluton of puzzle eventually. For ths reason, we use DFS method to solve the unsolved puzzle. Snce the general DFS s tme-consumng, we wll provde a branch and bound scheme to mprove the processng speed. One thng should be mentoned at frst, we choose the row nformaton to buld a search tree and use the column nformaton to do verfcaton as the method used n []. It means that every layer of tree s composed of row nformaton and all nodes of each layer are the possble solutons (PS) for the row. The followng fgures wll provde more detaled descrpton. Fg..4 (a) s a gven puzzle and Fgs..4 (b) and (c) are all possble solutons for row and row, respectvely. There are three possble solutons for row, two possble solutons for row, and two possble solutons for row, etc. Fg..4 (d) s a rough tree of Fg..4 (a). At a start, we try the frst possble soluton of row and use column nformaton to deduce that some cells n row should be colored or left empty. Then we check all possble solutons of row to refne whch possble solutons we want. Fg..5 (a) shows the deduced result based on the frst possble soluton of row : n row, the cells c 0 and c should be left empty, and then the cells c and c 4 should be colored. It s evdent that there s no possble soluton n row for ths stuaton. Hence, we reect ths possble soluton and do not search the followng rows. Then we try the next possble soluton of row as shown n Fg..5 (b) and the same result s obtaned. Thus, we proceed to try the last possble soluton of row and then we fnd the frst possble soluton of row sutable as shown n Fgs..5 (c) and (d). We go

32 on lke ths and then the answer, Fg..5 (e), s found. The above deducton and reecton process s called branch and bound scheme. Note that the symbol n Fg..5 stands for the cell determned. row row row row 4 row 5 5 (a) (b) (c) row row Fg..4 An example of DFS. (a) A gven puzzle. (b) The possble solutons of row. (c) The possble solutons of row. (d) A rough tree of (a). (d) There are 7 ( 6 = 7 ) leaf nodes n DFS tree for the puzzle n Fg..4 (a) we must check, but we do not need to check all leaf nodes based on the branch and bound scheme. The man reason s that some columns restrctons wll bound cells types n the next row after the current row beng bult. Ths wll make some branches be cut f a certan possble soluton of the next row can not ft the restrctons. In other words, we need not waste tme to test those possble solutons of the followng rows we have known they are wrong.

33 4 Fg..5 The process of DFS wth branch and bound. (a) The deduced result of row based on the frst possble soluton of row. (b) The deduced result of row based on the second possble soluton of row. (c) The deduced result of row based on the thrd possble soluton of row. (d) The frst possble soluton of row correspondng to (c). (e) The fnal soluton. Note that the DFS wth branch and bound scheme s used after usng logcal rules, the sze of searchng tree wll be reduced sgnfcantly. Fg..6 gves an example to do llustraton. There are possble solutons for the frst row n Fg..6 (a) orgnally. After applyng the logcal rules to Fg..6 (a), we obtan the result shown n Fg..6 (b). From Fg..6 (b), we can fnd that only possble solutons are left because the frst black run has been solved completely by LR. In addton, although the range of the last black run s (5, 8) now, we only need to check 5 c and 8 c not 5 c - 8 c. Checkng 6 c and 7 c s useless because we have known they are empty cells (a) (b) (c) (e) (d)

34 5 Fg..6 An example before usng DFS. (a) The orgnal puzzle. (b) The resultng puzzle executed by LR (a) (b)

35 CHAPTER EXPERIMENTAL RESULTS In our database, there are about 60 puzzles. Most of them come from [4-5, 7] and a lttle are created by us. There are two lnks beng contaned n [7], one s for playng Japanese puzzles onlne and another s a book of Japanese puzzles, we get the puzzles from here. A PC (CPU: AMD Athlon GHz) and a NB (CPU: Intel Pentum M.00GHz) are used to run ths program. Because most Japanese puzzles are meanngful, they can be solved quckly and completely only by LR. The executon tme s less than second. If the puzzle s not solved totally, the unknown part left s also solved successfully by DFS wth branch and bound scheme. Fg.. are the test mages: Fgs.. (a) (c) come from [4], Fg.. (d) comes from [5], and Fgs.. (e) and (f) are created by us. The frst two mages and the forth one are solved completely and quckly only by logcal rules. The three mages take more than 0 mnutes to get the solutons even an ncorrect soluton n [4-5], but we only spend about 0. second to solve them by usng logcal rules. However, Fg.. (c), a random mage (50% black), s solved completely usng about 6 hours whch s three tmes the executon tme of [4]. If the black pattern n a puzzle scatters everywhere, lke Fgs.. (c) and (e), ths wll lead LR to fal and make lengths of most black runs shorter and many of black runs n a row. It means that a black run may be placed n many possble postons and we should check many possble solutons of each row as shown n Fg... Thus, DFS wll take a longer tme to solve the puzzle. However, we can see Fg.. (f), the puzzle s also a random one (50% black), t s solved successfully wthn mnutes because t s more compact (.e. most black cells are connected together). Although most of the lengths of black runs are shorter lke Fg.. (c), they have a chan relaton, that s, some black cells n row 6

36 connect to some black cells n row, some black cells n row connect to some black cells n row, and so forth. Fg.. gves a more detaled llustraton. Note that the symbol n Fg.. stands for the connecton. (a) (b) (c) (d) (e) (f) Fg.. Test mages. (a) Sheep (5x5). (b) Arplane (5x5). (c) Random_ (0x0). (d) Monkey (5x5). (e) Sunflower (5x5). (f) Random_ (0x0). (a) (b) (c) (d) Fg.. An llustraton of scatterng. (a) 0 possble solutons. (b) possble solutons. (c) 6 possble solutons. (d) 56 possble solutons. 7

37 (a) (b) Fg.. An llustraton of chan relaton. More means the puzzle s more connected. (a) The magnfed pcture of part of Fg.. (c). (b) The magnfed pcture of part of Fg.. (f). Fg..4 from [4] s a puzzle wth two solutons. After applyng our algorthm, all the solutons wll be found out. Fg..5 s a puzzle wth no soluton. GA can not detect t and wll gve a wrong answer lke Fg..6. However, our method can detect t quckly because there must be a contradcton n logc of a vald puzzle wth no soluton. Hence, when we determne one cell should be colored or left empty, we wll check at frst whether the cell has been colored or left empty. If one cell s determned as a colored cell but t has been left empty, we wll detect that the puzzle has no soluton. Smlarly, f one cell s determned as an empty cell but t has been colored, t also means that the puzzle has no soluton. (a) (b) (c) Fg..4 A 7x8 puzzle wth many solutons. (a) The result after LR. (b) The frst soluton. (c) The second soluton. 8

38 Fg..5 A puzzle wth no soluton. Fg..6 GA gves a wrong answer of Fg..5. Fnally, Fg..7 shows some other test mages and Table shows the comparson of the expermental results between surveyed paper [5] and our algorthm. From Table, there are over 9% puzzles beng solved more than mnute whether by usng GA or DFS. However, after applyng our proposed method, there are over 98% puzzles beng solved about 0. second. All puzzles n our database are solved successfully and there s no doubt about the correctness of solutons. (a) (b) (c) (d) (e) (f) Fg..7 Test mages. (a) Flower_word (0x0). (b) Hppo (0x0). (c) Formosa (5x5). (d) Snoopy (5x5). (e) Owl (0x5). (f) Skatng (0x5). 9

39 Table The comparson of the expermental results between surveyed paper and our algorthm. Puzzle Type: Number Tme (64 puzzles totally) GA DFS Our Method 5x5: 5x6: 0x0:, 0x40: wrong answer more than mn. wrong answer more than mn. no soluton 0.0 sec sec. no soluton more than mn. no soluton detected less than 0. sec. (above fve puzzles have no soluton) sze 6x6: sec.<tme <5 sec. 0.0 sec. tme <0.6 sec. 0.0 sec. tme <0. sec. 6x6<sze<0x0: 9 about 0 sec.: > mn.: sec.<tme < mn.: 7 > mn.: about 0. sec. Random_ more than days more than days about 6 hr. 0x0 sze 5x5: 5x5<sze<5x5: 0 sze 5x5: 00 Sunflower more than hr. more than hr. about 0 mn. Random_ Owl: sec. Others more than mn. more than mn. Skatng: 6 sec. Others: about 0. sec. 0

40 CHAPTER 4 CONCLUSIONS In ths thess, we have proposed a fast method to solve Japanese puzzles. The method contans two phases, the frst phase used logcal rules to solve cells n a puzzle as many as possble. In the second phase, based on column nformaton, DFS wth branch and bound scheme s used to solve those unknown cells remanng after the frst phase. Snce DFS s an exhaustve search, t s very tme-consumng. When the sze of puzzle or the possble solutons of each row becomes larger, the tme complexty also rses. Consequently, usng LR at frst s necessary because some cells can be solved easly by logc. If some cells are solved successfully at frst, the sze of tree wll be reduced. However, not all puzzles can be solved completely by LR f the black pattern n a puzzle s dstrbuted randomly, lke Fgs.. (c), (e), and (f). For ths stuaton, we use branch and bound scheme to assst n solvng Japanese puzzles. The expermental results show that our method can solve those puzzles wth compact black patterns quckly. For those puzzles wth random black patterns, the method can also rase the speed of DFS usng branch and bound scheme. Furthermore, our method always provdes correct solutons.

41 CHAPTER 5 FUTURE WORKS Japanese puzzle, a pencl-and-paper game, s very popular n some countres, lke Japan and Netherlands. It s as nterestng as Sudoku because both of them are logcal games. Logcal games let people to use ther bran when they are playng. Thnkng and learnng n playng s a good thng. Ether adults or chldren wll be attracted by Japanese puzzles deeply. At present, Sudoku has been developed as onlne gamng and moble gamng, we thnk the Japanese puzzle could also be desgned lke Sudoku. A complete Japanese puzzle game may consst of three parts: generator, solver, and helper. Usng a puzzle generator, the player can create what puzzle he wants by nputtng a pcture. In ths thess, a smple generator s created for any type pctures but t works better n black-whte pctures than colorful ones. Fg. 5. s an llustraton. The sze of puzzle can be decded arbtrarly. As for the solver, t s the man part of ths game. As the prevous chapters mentoned, the solver s to solve all Japanese puzzles. Fnally, the helper can gve the player several hnts based on the solver when he needs. Combnng what proposed above, we use the tmes of hnts gven and the tme spent to calculate the score, and then rank all players accordng to ther scores. Consequently, Japanese puzzle wll become a game full of challenge and exctaton. (a) (b) (c) Fg. 5. Generator. (a) The nput mage. (b) The puzzle generated. (c) The result of the puzzle.

42 REFERENCES [] N. Ueda and T. Nagao, NP-completeness Results for NONOGRAM va Parsmonous Reductons, Techncal Report TR , Department of Computer Scence, Tokyo Insttute of Technology, May 996. [] B. P. McPhal, Lght Up s NP-Complete, Feb URL: edu/~mcphalb/lghtup.pdf. [] K. J. Batenburg, An Evolutonary Algorthm for Dscrete Tomography, Dscrete Appled Mathematcs, vol. 5, no. -, pp. 6-54, Oct [4] K. J. Batenburg and W. A. Kosters, A Dscrete Tomography Approach to Japanese Puzzles, Proceedngs of BNAIC, pp. 4-50, 004. [5] W. A. Wggers, A Comparson of a Genetc Algorthm and a Depth Frst Search Algorthm Appled to Japanese Nonograms, Twente Student Conference on IT, Jun [6] URL: [7] Database of Japanese puzzles. URL: /stage_0/ndex.html and em= [8] K. A. DeJong and W. M. S pears, Usng Genetc Algorthms to Solve NP-Complete Problems, Proceedngs of the rd Internatonal Conference on Genetc Algorthms, pp. 4-, 989. [9] T. Yato and T. Seta, Complexty and Completeness of Fndng Another Soluton and Its Applcaton to Puzzles, IEICE Transactons on Fundamentals of Electroncs, Communcatons and Computer Scences, vol. E86-A, no. 5, pp , 00. [0] B. P. McPhal, The Complexty of Puzzles: NP-completeness Results for Nurkabe and Mnesweeper, Reed College, Undergraduate Thess, Dec. 00. URL: [] D. R. Fulkerson, Zero-one Matrces wth Zero Trace, Pacfc Journal of Mathematcs, vol. 0, no., pp. 8-86, 960. [] J. Benton, R. Snow, and N. Wallach, A Combnatoral Problem Assocated wth Nonograms, Lnear Algebra and Its Applcatons, vol. 4, no., pp. 0-8, 006. [] Robert A. Bosch, Pantng by Numbers, Sep URL: edu/math/faculty/bosch/pbn-page.html.