## Aims

Mathematical puzzles and games have their long history, and they are popular not only for pastime but also for stimulating intellectual curiosity of mathematicians and computer scientists as their research material. Their investigation and outcome are significant as the results themselves, and at the same time, they have been playing an important role for incubating new theory and for giving ripple effect to neightboring areas. Such puzzles and games often have geometric flavor in some sense, and thus they have brought rich influence to computational geometry areas and others as well. This workshop is intended to provide a forum for both researchers and practitioners to promote their interactions and blendings. We can expect that such interaction will promote many new interesting geometric problems, concepts and ideas, which will contribute to open up new vistas in computational geometry communities.

## Date and Venue

Date: June 10 (Tue), 14:30 -- 18:00

Place: Kyoto University Centennial Memorial Hall (A workshop
in Computational Geometry Week 2014)

## Program

- [14:30--14:35] Opening: Hiro Ito (The University of Electro-Communications, Japan)
- [14:35--15:05]
**Erik D. Demaine**(MIT, USA)

Recent Results in Recreational Computer Science - [15:05--15:35]
**Kevin Buchin**(Eindhoven University of Technology, The Netherlands)

Things that Roll, Pull and Glide - [15:35--16:05]
**Jin Akiyama**(Tokyo University of Science, Japan)

From Japanese Old Math - Short Break (20 min.)
- [16:25--16:55]
**Marc van Kreveld**(Utrecht University, The Netherlands)

Puzzles in Wood, Puzzles on Paper, and Puzzles in Bytes - [16:55--17:25]
**Matias Korman**(National Institute of Informatics, Japan)

Placing Polyominoes on the Grid - [17:25--17:55]
**Mike Paterson**(Professor Emeritus, University of Warwick, UK)

Packing Pie - [17:55--18:00] Closing: Stefan Langerman (Université Libre de Bruxelles, Belgium)

## Abstracts of Talks

**Erik D. Demaine**(MIT, USA)

**Recent Results in Recreational Computer Science**

Recreational computer science aims to understand "recreational" pursuits such as puzzles, games, and magic tricks from an algorithmic/complexity theoretic perspective. In this talk, I'll present some of my favorite recent results about Nintendo video games, the Rubik's cube, its crazed predecessor Instant Insanity, "mate in 1" puzzles, the picture hanging puzzle/magic trick, and puzzle fonts where reading the written text is itself a puzzle.**Kevin Buchin**(Eindhoven University of Technology, The Netherlands)

**Things that Roll, Pull and Glide**

In many popular puzzle games like rush hour and lunar lockout tokens are moved on an unlabeled board and the goal is to maneuver a specific token to a prescribed goal position. These puzzles differ in the rules for the movement, in rolling block mazes, for instance, blocks are rolled, in lunar lockout robots glide until they bump into another robot. Constraint logic by Hearn and Demaine provides a uniform framework to analyze the complexity of such puzzle games. I will discuss the complexity of several such games and other problems, in particular I will present a new proof of the PSPACE-completeness of lunar lockout.**Jin Akiyama**(Tokyo University of Science, Japan)

**From Japanese Old Math**

[A game from WASAN (Japanese math)]

According to "Sangaku-Kijinden" (written by Yoshio Nagai, published by TBS-BRITANNICA), a non-fiction novel on the history of WASAN (Japanese traditional mathematics), WASAN scholar Chosichi Yoshii (around 1790-1850) in the Edo periodmade a fortune at one swoop by dice gamble. In the gamble, two players A and B bet 1 Ryo (gold coin of 1 Japanese tael) on the following game: (1) A rolls the dice. Let X1 be the number on the top. (2) B rotates the dice by 90 degrees so that gets on the side of the dice. Let X2 be the number on the top. (3) A rotates the dice by 90 degrees so that X2 gets on the side of the dice. Let X3 be the number on the top. (4) Repeat the procedure until the sum X1+X2+...+Xm exceeds 31. If m is odd, i.e., A's dice number caused the sum to exceed 31, B wins and receives1 Ryo from A. If m is even, A wins and receives 1 Ryo from B.

[Generalization of the game]

Let N be an arbitrary integer larger than 2. Instead of a dice, we choose a natural number from 1, 2,... , N. (1) A choose a number from 1, 2,... , N. Let X1 be the number chosen by A. (2) B choose a number from 1, 2,... , N excluding X1and N+1-X1. Let X2 be the number chosen by B. Then X2 satisfies X1 \neq X2 and X1 + X2 \neq N+1. (3) Achoose a number from 1, 2,... , N excluding X2 and N+1-X2. Let X3 be the number chosen by B. Then X3 satisfies X2 \neq X3 and X2 + X3 \neq N+1. (4) Repeat the procedure until the sum X1+X2+...+Xm exceeds M. If m is odd, i.e., A's dice number caused the sum to exceed M, B wins. If m is even, A wins. The table on the right shows the period of the winning strategy depending on N.

Note that the number of game statuses required to obtain the winning strategy for the current status is finite (N x (N/2)) and thus the number of strategies to obtain the full winning strategy is bounded by . By pigeonhole principle, the period always exists although it may be very big.

Also, we are planning to refer geometric game by using pentadra.**Marc van Kreveld**(Utrecht University, The Netherlands)

**Puzzles in Wood, Puzzles on Paper, and Puzzles in Bytes**

I will give an overview of wooden puzzles I designed and the computations done to obtain them. Then I will present recent research on connect-the-dots puzzles, and research related to puzzle apps. Automatically establishing difficulty of a puzzle is one of the main themes.**Matias Korman**(National Institute of Informatics, Japan)

**Placing Polyominoes on the Grid**

Polyominoes are often featured in many popular games. In most of cases, player(s) alternate turns placing polyominoes until one of them constructs a winning pattern. In this talk we study interesting one and two player polyomino games from a theoretical viewpoint.**Mike Paterson**(Professor Emeritus, University of Warwick, UK)

**Packing Pie**

When a circular pie of unit radius is*half*-eaten, the remaining pie is to be cut into slices and rearranged on a smaller circular plate. How small can this plate be? Of course, pie may only be cut into radial sectors!

We would like to answer this question for all values of the variable*half*, where 0 <*half*< 1. At present we have some pretty patterns and conjectures for optimal arrangements. It is an open problem to prove optimality for any of these.

This is joint work with Vaughan Pratt of Stanford University.

## Registration

Free of charge for the registered participants of SoCG 2014.

Others may register from the
SoCG webpage
(1-day workshop registration).

## Organizers

- Hiro Ito (The University of Electro-Communications, Japan)
- Stefan Langerman (Université Libre de Bruxelles, Belgium)
- Yushi Uno (Osaka Prefecture University, Japan)