| Presentation | 2010-03-12 NP-Completeness and Enumeration of Number Link Puzzle Kouichi KOTSUMA, Yasuhiko TAKENAGA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Number Link is a puzzle on a square grid. Some numbers are given in cells so that each number appears in two cells, and the object of the puzzle is to connect the cells with the same number by non-crossing lines drawn on the cells. In this paper, we first prove that Number Link is NP-complete even if an answer that has a cell on which no line is drawn is not admitted. Second, we propose an algorithm to enumerate the problems of Number Link with a given size using reverse-search algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | puzzle / NP-completeness / enumeration algorithm |
| Paper # | COMP2009-49 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/3/5(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | NP-Completeness and Enumeration of Number Link Puzzle |
| Sub Title (in English) | |
| Keyword(1) | puzzle |
| Keyword(2) | NP-completeness |
| Keyword(3) | enumeration algorithm |
| 1st Author's Name | Kouichi KOTSUMA |
| 1st Author's Affiliation | Department of Computer Science, Graduate School of Electro-Communications, The University of Electro-Communications() |
| 2nd Author's Name | Yasuhiko TAKENAGA |
| 2nd Author's Affiliation | Department of Computer Science, Faculty of Electro-Communications, The University of Electro-Communications |
| Date | 2010-03-12 |
| Paper # | COMP2009-49 |
| Volume (vol) | vol.109 |
| Number (no) | 465 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |