著者

Xu Dawei Horiyama Takashi Uehara Ryuhei

出版者

CCCG

雑誌

Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017)

巻号頁・発行日

pp.62-67, 2017-07-26

---

Last year, a new notion of rep-cube was proposed. A rep-cube is a polyomino that is a net of a cube, and it can be divided into some polyominoes such that each of them can be folded to a cube. This notion was inspired by the notions of polyomino and rep-tile, which were introduced by Solomon W. Golomb. It was proved that there are infinitely many distinct rep-cubes. In this paper, we investigate this new notion and obtain three new results. First, we prove that there does not exist a regular rep-cube of order 3, which solves an open question proposed in the paper. Next, we enumerate all regular rep-cubes of order 2 and 4. For example, there are 33 rep-cubes of order 2; that is, there are 33 dodecominoes that can fold to a cube of size √<2> x √<2> x √<2> and each of them can be divided into two nets of unit cube. Similarly, there are 7185 rep-cubes of order 4. Lastly, we focus on pythagorean triples that consist of three positive integers (a, b,c) with a^2+b^2=c^2. For each of these triples、 we can consider a rep-cube problem that asks whether a net of a cube of size c x c x c can be divided into two nets of two cubes of size a x a x a and b x b x b. We give a partial answer to this natural open question by dividing into more than two pieces. For any given pythagorean triple (a, b, c), we construct five polyominoes that form a net of a cube of size c x c x c and two nets of two cubes of size a x a x a and b x b x b.

著者

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.

著者

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.

著者

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.

著者

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.

著者

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.