6 0 0 0 IR UNO Is Hard, Even for a Single Player
- 著者
- Demaine Erik D. Demaine Martin L. Uehara Ryuhei Uno Takeaki Uno Yushi
- 出版者
- Springer
- 雑誌
- Lecture Notes in Computer Science (ISSN:03029743)
- 巻号頁・発行日
- vol.6099, pp.133-144, 2010
- 被引用文献数
- 3
UNO is one of the world-wide well-known and popular card games. We investigate UNO from the viewpoint of combinatorial algorithmic game theory by giving some simple and concise mathematical models for it. They includecooperative and uncooperative versions of UNO, for example. As a result of analyzing their computational complexities, we prove that even a single-player version of UNO is NP-complete, while it becomes in P in some restricted cases. We also show that uncooperative two-player's version is PSPACE-complete.Fun with Algorithms : 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010.
2 0 0 0 IR Ghost Chimneys
- 著者
- Charlton David Demaine Erik D. Demaine Martin L. Dujmovic Vida Morin Pat Uehara Ryuhei
- 出版者
- World Scientific Publishing
- 雑誌
- International Journal of Computational Geometry and Applications (ISSN:02181959)
- 巻号頁・発行日
- vol.22, no.3, pp.207-214, 2012
A planar point set S is an (i, t) set of ghost chimneys if there exist lines H_0, H_1,…,H_<t-1> such that the orthogonal projection of S onto H_j consists of exactly i + j distinct points. We give upper and lower bounds on the maximum value of t in an (i, t) set of ghost chimneys, showing that it is linear in i.
2 0 0 0 IR UNO は一人でも難しい (計算機科学とアルゴリズムの数理的基礎とその応用)
- 著者
- Demaine Erik D. Demaine Martin L. 上原 隆平 宇野 毅明 宇野 裕之
- 出版者
- 京都大学
- 雑誌
- 数理解析研究所講究録 (ISSN:18802818)
- 巻号頁・発行日
- vol.1744, pp.48-55, 2011-06
- 著者
- Demaine Erik D. Okamoto Yoshio Uehara Ryuhei Uno Yushi
- 出版者
- 電子情報通信学会
- 雑誌
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)
- 巻号頁・発行日
- vol.E97-A, no.6, pp.1213-1219, 2014-06-01
Shakashaka is a pencil-and-paper puzzle proposed by Guten and popularized by the Japanese publisher Nikoli (like Sudoku). We determine the computational complexity by proving that Shakashaka is NP-complete, and furthermore that counting the number of solutions is #P-complete. Next we formulate Shakashaka as an integer-programming (IP) problem, and show that an IP solver can solve every instance from Nikoli's website within a second.
1 0 0 0 OA Ghost Chimneys
- 著者
- Charlton David Demaine Erik D. Demaine Martin L. Dujmovic Vida Morin Pat Uehara Ryuhei
- 出版者
- World Scientific Publishing
- 雑誌
- International Journal of Computational Geometry and Applications (ISSN:02181959)
- 巻号頁・発行日
- vol.22, no.3, pp.207-214, 2012
A planar point set S is an (i, t) set of ghost chimneys if there exist lines H_0, H_1,…,H_<t-1> such that the orthogonal projection of S onto H_j consists of exactly i + j distinct points. We give upper and lower bounds on the maximum value of t in an (i, t) set of ghost chimneys, showing that it is linear in i.
1 0 0 0 OA UNO is hard, even for a single player
- 著者
- Demaine Erik D. Demaine Martin L. Harvey Nicholas J. A. Uehara Ryuhei Uno Takeaki Uno Yushi
- 出版者
- Elsevier
- 雑誌
- Theoretical Computer Science (ISSN:03043975)
- 巻号頁・発行日
- vol.521, pp.51-61, 2013-11-22
- 被引用文献数
- 8
This paper investigates the popular card game UNO from the viewpoint of algorithmic combinatorial game theory. We define simple and concise mathematical models for the game, including both cooperative and uncooperative versions, and analyze their computational complexity. In particular, we prove that even a single-player version of UNO is NP-complete, although some restricted cases are in P. Surprisingly, we show that the uncooperative two-player version is also in P.