Recreational Mathematics
These papers are mainly for fun, although there is also some serious research content to some of them. See also my publications on folding and unfolding and my recreational mathematics web pages.
- On the NP-completeness of cryptarithms.
D. Eppstein.
SIGACT News 18 (3): 38–40, 1987.A cryptarithm (also known as an alphametic) is a puzzle in which the digits of a mathematical formula (typically addition of two large numbers) are replaced by letters; the goal is to determine which letter stands for which digits. If arithmetic is done in a polynomially large radix, the problem becomes NP-complete.
- Ten algorithms for Egyptian fractions.
D. Eppstein.
Mathematica in Education and Research 4 (2): 5–15, 1995.Number theory. I survey and implement in Mathematica several methods for representing rational numbers as sums of distinct unit fractions. One of the methods involves searching for paths in a certain graph using a k shortest paths heuristic.
- Zonohedra and Zonotopes.
D. Eppstein.
Tech. Rep. 95-53, ICS, UCI, 1995.
Mathematica in Education and Research 5 (4): 15–21, 1996.I use Mathematica to construct zonotopes and display zonohedra. Many examples are shown, including one used for a lower bound in "The centroid of points with approximate weights". This paper is also available in HTML and Mathematica notebook formats.
- A disk-packing algorithm for an origami magic trick.
M. Bern, E. Demaine, D. Eppstein, and B. Hayes.
Int. Conf. Fun with Algorithms, Elba, June 1998.
Proceedings in Informatics 4, Carleton Scientific, Waterloo, Canada, 1999, pp. 32–42.
Origami3: Proc. 3rd Int. Mtg. Origami Science, Math, and Education (Asilomar, California, 2001), A K Peters, 2002, pp. 17–28.We apply techniques from "Quadrilateral meshing by circle packing" to a magic trick of Houdini: fold a piece of paper so that with one straight cut, you can form your favorite polygon.
- Ununfoldable polyhedra.
M. Bern, E. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Snoeyink.
arXiv:cs.CG/9908003.
Tech. rep. CS-99-04, Univ. of Waterloo, Dept. of Computer Science, Aug. 1999.
11th Canad. Conf. Comp. Geom., 1999.
4th CGC Worksh. Computational Geometry, Johns Hopkins Univ., 1999.
Comp. Geom. Theory & Applications (special issue for 4th CGC Worksh.) 24 (2): 51–62, 2003.We prove the existence of polyhedra in which all faces are convex, but which can not be cut along edges and folded flat.
Note variations in different versions: the CCCG one was only Bern, Demain, Eppstein, and Kuo, and the WCG one had the title "Ununfoldable polyhedra with triangular faces". The journal version uses the title "Ununfoldable polyhedra with convex faces" and the combined results from both conference versions.
- Hinged dissections of polyominos and polyforms.
E. Demaine, M. Demaine, D. Eppstein, G. Frederickson, and E. Friedman.
arXiv:cs.CG/9907018.
11th Canad. Conf. Comp. Geom., 1999.
Computational Geometry: Theory and Applications 31 (3): 237–262, 2005 (special issue for 11th CCCG).We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.
- Tangent spheres and triangle centers.
D. Eppstein.
arXiv:math.MG/9909152.
Amer. Math. Monthly 108 (1): 63–66, 2001.Any four mutually tangent spheres determine three coincident lines through opposite pairs of tangencies. As a consequence, we define two new triangle centers. These centers arose as part of a compass-and-straightedge construction of Soddy circles; also available are some Mathematica calculations of trilinear coordinates for the new triangle centers.
- Searching for spaceships.
D. Eppstein.
arXiv:cs.AI/0004003.
MSRI Combinatorial Game Theory Research Worksh., July 2000.
More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 433–453.We describe software that searches for spaceships in Conway's Game of Life and related two-dimensional cellular automata. Our program searches through a state space related to the de Bruijn graph of the automaton, using a method that combines features of breadth first and iterative deepening search, and includes fast bit-parallel graph reachability and path enumeration algorithms for finding the successors of each state. Successful results include a new 2c/7 spaceship in Life, found by searching a space with 2^126 states.
- One-dimensional peg solitaire, and duotaire.
C. Moore and D. Eppstein.
arXiv:math.CO/0006067 and math.CO/0008172.
MSRI Combinatorial Game Theory Research Worksh., July 2000.
Santa Fe Inst. working paper 00-09-050, September 2000.
More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 341–350.We describe by a regular expression the one-dimensional peg-solitaire positions reducible to a single peg, and provide a linear-time algorithm (based on finding shortest paths in an associated DAG) for reducing any such position to the minimum number of pegs. We then investigate impartial games in which players alternate peg solitaire moves in an attempt to be the one to move last.
(Cris' MSRI talk on streaming video – Cris' publications page)
- Phutball endgames are hard.
E. Demaine, M. Demaine, and D. Eppstein.
arXiv:cs.CC/0008025.
More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 351–360.We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.
- Hinged kite mirror dissection.
D. Eppstein.
arXiv:cs.CG/0106032.We show that any polygon can be cut into kites, connected into a chain by hinges at their vertices, and that this hinged assemblage can be unfolded and refolded to form the mirror image of the polygon.
- Triangles and squares.
D. Eppstein.
Invited talk at EuroConf. Combinatorics, Graph Theory, and Applications, Bellaterra, Spain, 2001, p. 114.Which unit-side-length convex polygons can be formed by packing together unit squares and unit equilateral triangles? For instance one can pack six triangles around a common vertex to form a regular hexagon. It turns out that there is a pretty set of 11 solutions. We describe connections from this puzzle to the combinatorics of 3- and 4-dimensional polyhedra, using illustrations from the works of M. C. Escher and others.
(Slides)
- Nonrepetitive paths and cycles in graphs with application to Sudoku.
D. Eppstein.
arXiv:cs.DS/0507053.We describe algorithms and hardness results for finding paths in edge-labeled graphs such that no two consecutive edges have the same label, and use our algorithms to implement heuristics for a program that automatically solves and generates Sudoku puzzles.
- Growth and decay in life-like cellular automata.
D. Eppstein.
arXiv:0911.2890.
Game of Life Cellular Automata (Andrew Adamatzky, ed.), Springer, 2010, pp. 71–98.We classify semi-totalistic cellular automaton rules according to whether patterns can escape any finite bounding box and whether patterns can die out completely, with the aim of finding rules with interesting behavior similar to Conway's Game of Life. We survey a number of such rules.
- Solving single-digit Sudoku subproblems.
D. Eppstein.
arXiv:1202.5074.
6th International Conference on Fun with Algorithms (FUN 2012), Venice, Italy, 2012.
Springer, Lecture Notes in Comp. Sci. 7288, 2012, pp. 142–153.We find an algorithm for making all possible deductions based on the set of candidate locations for a single digit in a Sudoku puzzle; the problem is NP-hard, and our algorithm takes exponential time, but the mild form of the exponential allows it to be fast for practical problem sizes.
(Slides)
- Drawing arrangement graphs in small grids, or how to play
planarity.
D. Eppstein.
arXiv:1308.0066.
21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 436–447.
J. Graph Algorithms & Applications 18 (2): 211–231, 2014 (special issue for GD'13).The planarity game involves rearranging a scrambled line arrangement graph to make it planar. We show that the resulting graphs have drawings in grids of area n7/6, much smaller than the quadratic size bound for grid drawings of planar graphs, and we provide a strategy for planarizing these graphs that is simple enough for human puzzle solving.
- Faster evaluation of subtraction games.
D. Eppstein.
arXiv:1804.06515.
Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018), La Maddalena, Italy.
Leibniz International Proceedings in Informatics (LIPIcs) 100, pp. 20:1–20:12.
We show how to evaluate the set of winning heap sizes in subtraction games like subtract-a-square in near-linear time, and how to compute the nim-values more quickly than naive dynamic programming. Additionally we perform computational experiments showing that the set of winning positions forms an unexpectedly dense square-difference-free set.
(Slides)
- Making change in 2048.
D. Eppstein.
arXiv:1804.07396.
Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018), La Maddalena, Italy.
Leibniz International Proceedings in Informatics (LIPIcs) 100, pp. 21:1–21:13.
The 2048 puzzle, modified to use any sequence of integer tile values that has arbitrarily large gaps, always terminates. The proof relates the puzzle to the greedy algorithm for making change (suboptimally) using a given system of coins.
(Slides)
- On the treewidth of Hanoi graphs.
D. Eppstein, D. Frishberg, and W. Maxwell.
arXiv:2005.00179.
Proc. 10th Int. Conf. Fun with Algorithms (FUN 2021).
Leibniz International Proceedings in Informatics (LIPIcs) 157, 2020, pp. 13:1–13:21.
Theor. Comput. Sci. 906: 1–17, 2022.The n-disc p-peg Hanoi graphs have treewidth within a polynomial factor of np − 1.
- Egyptian fractions with denominators from sequences closed under doubling.
D. Eppstein.
J. Integer Sequences 24: 21.8.8, 2021.
arXiv:2109.12217.We prove that if a set of positive integers includes multiples of all integers, and is closed under multiplication by two, then its reciprocals can form Egyptian fractions for every rational number up to the sum of reciprocals of the set.
- Uniqueness in puzzles and puzzle solving.
D. Eppstein.
Minisymposium on Mathematical Puzzles and Games in Theoretical Computer Science, ICIAM, Waseda Univ., Tokyo, Japan, 2023.
In puzzles such as Sudoku, one can often make use of an assumption that the solution is unique, in deduction rules that eliminate alternatives that would lead to a non-unique solution. However, these rules can lack the monotonicity properties of other deduction rules, under which a conclusion that can be deduced from some partially-solved state of the puzzle remains available to be deduced until it actually is deduced. I discuss a method of obtaining monotonic deductions in a planar precoloring extension puzzle, and ask whether there is some more general method for obtaining monotonicity in this way.
- Games on game graphs.
D. Eppstein. AMS Special Session on Serious Recreational Mathematics, Joint Mathematics Meetings, San Francisco, 2024.
This talk surveys graph parameters defined from pursuit-evasion games on graphs, including cop-number, treewidth, and flip-width, and the values of these parameters on graphs derived from games and puzzles.