Derived from the Greek word for '5', and "domino", a pentomino is a polyomino of order 5; that is, a polygon in the plane made of 5 equal-sized squares connected edge to edge. When rotations and reflections are not considered to be distinct shapes, there are 12 different free pentominoes. When reflections are considered distinct, there are 18 one-sided pentominoes. When rotations are also considered distinct, there are 63 fixed pentominoes.
A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.
Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.
Tantrix is a hexagonal tile-based abstract game invented by Mike McManaway from New Zealand. Each of the 56 different tiles in the set contains three lines, going from one edge of the tile to another. No two lines on a tile have the same colour. There are four colours in the set: red, yellow, blue, and green. No two tiles are identical, and each is individually numbered from 1 through 56.
A polycube is a solid figure formed by joining one or more equal cubes face to face. Polycubes are the three-dimensional analogues of the planar polyominoes. The Soma cube, the Bedlam cube, the Diabolical cube, the Slothouber–Graatsma puzzle, and the Conway puzzle are examples of packing problems based on polycubes.
A tromino or triomino is a polyomino of size 3, that is, a polygon in the plane made of three equal-sized squares connected edge-to-edge.
The no-three-in-line problem in discrete geometry asks how many points can be placed in the grid so that no three points lie on the same line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".
Tiling puzzles are puzzles involving two-dimensional packing problems in which a number of flat shapes have to be assembled into a larger given shape without overlaps. Some tiling puzzles ask players to dissect a given shape first and then rearrange the pieces into another shape. Other tiling puzzles ask players to dissect a given shape while fulfilling certain conditions. The two latter types of tiling puzzles are also called dissection puzzles.
A sliding puzzle, sliding block puzzle, or sliding tile puzzle is a combination puzzle that challenges a player to slide pieces along certain routes to establish a certain end-configuration. The pieces to be moved may consist of simple shapes, or they may be imprinted with colours, patterns, sections of a larger picture, numbers, or letters.
In the mathematical field of combinatorics, given a collection of subsets of a set , an exact cover is a subcollection of such that each element in is contained in exactly one subset in . One says that each element in is covered by exactly one subset in . An exact cover is a kind of cover. It is non-deterministic polynomial time (NP) complete and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design.
The 3-partition problem is a strongly NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triplets that all have the same sum. More precisely:
In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.
The Eternity II puzzle is an edge-matching puzzle launched on 28 July 2007. It was developed by Christopher Monckton and marketed and copyrighted by TOMY UK Ltd as a successor to the original Eternity puzzle. The puzzle was part of a competition in which a $2 million prize was offered for the first complete solution. The competition ended at noon on 31 December 2010, with no solution being found.
A three-dimensional edge-matching puzzle is a type of edge-matching puzzle or tiling puzzle involving tiling a three-dimensional area with polygonal pieces whose edges are distinguished with colors or patterns, in such a way that the edges of adjacent pieces match. Edge-matching puzzles are known to be NP-complete, and capable of conversion to and from equivalent jigsaw puzzles and polyomino packing puzzle.
Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.
Serpentiles is the name coined by Kurt N. Van Ness for the hexagonal tiles used in various edge-matching puzzle connection abstract strategy games, such as Psyche-Paths, Kaliko, and Tantrix. For each tile, one to three colors are used to draw paths linking the six sides together in various configurations. Each side is connected to another side by a specific path route and color. Gameplay generally proceeds so that players take turns laying down tiles. During each turn, a tile is laid adjacent to existing tiles so that colored paths are contiguous across tile edges.
Rectangle packing is a packing problem where the objective is to determine whether a given set of small rectangles can be placed inside a given large polygon, such that no two small rectangles overlap. Several variants of this problem have been studied.
MacMahon Squares are an edge-matching puzzle first published by Percy MacMahon in 1921, using 24 unique squares with 3-color patterns; each of the four edges is assigned a single color. The complete set of 24 squares are organized next to each other by matching edge colors to create a 4 by 6 grid. Such tessellation puzzles have multiple variants, which are determined by restrictions on how to arrange the 24 squares. This game has also been commercialized in numerous physical forms, by various companies.
Le Trioker is a corner-matching puzzle game played using 25 equilateral triangle-shaped tiles. Each corner is marked with zero, one, two, or three dots and newly placed pieces must match the values on pieces already placed on the game board, similar to the gameplay of the earlier Triominoes.
