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.
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.
(Also available in HTML and Mathematica notebook formats)
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.
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.
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.
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.
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.
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.
(MSRI talk on streaming video and Slides)
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)
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.
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.
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)
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.
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.
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)
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.
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)
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)
The n-disc p-peg Hanoi graphs have treewidth within a polynomial factor of np − 1.
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.
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.
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.
Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.