Abstract : Research on puzzles and games from the viewpoint of theoretical computer science has continued without any break in the history of theoretical computer science. Sometimes the research on computational complexity classes has proceeded by understanding the tons of puzzles. The wide collection of complete problems for a specific computational complexity class shares a common property, which gives us a deep understanding of the class. In this mini-symposium, we will explore the latest topics, results, and trends related to puzzles and games from the viewpoints of mathematics and theoretical computer science.
Abstract : Many classical pencil-and-paper puzzles are defined in a way that requires the puzzle to have a unique solution. We explore the theoretical and practical implications of this requirement on the difficulty of puzzle-solving and puzzle generation, and the uses of the assumption of uniqueness in puzzle inference rules for puzzles including Sudoku, Slither Link / Loopy, and Map.
[04855] The Complexity of Games and Puzzles with Limited Width
Format : Talk at Waseda University
Author(s) :
Tom van der Zanden (Maastricht University)
Abstract : When studying the complexity of games and puzzles, we usually consider generalized versions. For example, chess is played on an $8\times 8$ board but when analyzing the complexity, we consider a version played on an $n\times n$ board. What if instead we consider the $n\times k$ variant, where $k$ is a small number? In this talk, we survey some results on the computational complexity of games and puzzles with small width.
[04898] Mathematical Puzzles for Computer Scientists: Leisure or More?
Format : Talk at Waseda University
Author(s) :
Hirokazu Iwasawa (Waseda University)
Abstract : The speaker, a creator of mathematical puzzles including mechanical puzzles, introduces a selection of puzzles that are likely to appeal to computer scientists, chosen from those he has devised in the past. While these puzzles can be enjoyed as leisure, some of them may potentially become subjects of research.
[05028] One Cycle to Rule Them All
Format : Talk at Waseda University
Author(s) :
Giovanni Viglietta (University of Aizu)
Abstract : One of the consequences of the classification of the finite simple groups is that, if $G$ is a primitive permutation group of degree $n$ containing a cycle of length $n-3$ or less, then $G$ is either the symmetric group $S_n$ or the alternating group $A_n$. We will discuss some applications of this result to the theory of token permutation puzzles, as well as some open problems and directions for further research.
Abstract : Janken or rock-paper-scissors, which is a very simple game and it is usually used as a coin-toss in Japan, originated in China, and many variants are seen throughout the world. A variant of janken can be represented by an asymmetric digraph, where a vertex corresponds a sign and an arc (x,y) means sign x defeats sign y. However, not all asymmetric digraphs define useful janken variants, i.e., some janken variants may include a useless sign, which is strictly inferior than another sign in any case. We call a janken variant efficient if it contains no such a useless sign. We also introduced a measure of amusement of janken variants. We show the results of our mathematical research on janken variants.
[05219] Tilings and unfoldings
Format : Talk at Waseda University
Author(s) :
Stefan Langerman (Université libre de Bruxelles)
Abstract : A tiling is a covering of the plane with copies of a geometric shape (tiles) without gaps or overlaps. A tiler is a shape that tiles the plane.
An unfolding is obtained by cutting along the surface of a polyhedron through all its vertices, and opening all the dihedral angles between adjacent faces to obtain a single flat non-overlapping geometric shape.
In this talk, I will explore connections between these fascinating concepts, highlight some recent results and mention several still unsolved algorithmic problems,
[05433] A Hardness Framework for Games and Puzzles: Motion Planning through Gadgets
Format : Talk at Waseda University
Author(s) :
Erik D. Demaine (Massachusetts Institute of Technology)
Abstract : Many games and puzzles, especially video games, involve one or more characters moving through a changeable environment, like Mario in Super Mario Bros. We describe a powerful framework for proving hardness of such games by characterizing which "gadgets" it suffices to build in the game. A gadget is a local piece of environment with limited traversals, some of which change local state, which in turn change available traversals, similar to a finite automaton. We prove that very simple gadgets suffice to prove NP-hardness, PSPACE-hardness, or EXPTIME-hardness. This framework enables many hardness proofs, old and new, to be distilled down to a single diagram of a single gadget, resulting in new or simplified hardness proofs for games such as Super Mario Bros., Mario Kart, Pokémon, Lemmings, Rush Hour, and Chess. It also opens up a rich study of gadgets themselves, including which gadgets can "simulate" which others, where a "simulation" is a graph representing a reduction algorithm.
[05443] Map Folding
Format : Talk at Waseda University
Author(s) :
Yushi Uno (Osaka Metropolitan University)
Abstract : Origami (paper folding) is not only a traditional Japanese entertainment, but also an interesting research topic in both engineering and computer science. One of the special cases of paper folding is map folding, and it has interesting open problems. In this talk, we will introduce the map folding problem and show their latest research results.
