Edge-matching puzzle

A tile problem is the task to organize a lot of parts to a whole, so that certain rules are followed. Tile problems can be solved as a puzzle to pass the time. Theoretical computer science examines tile problems, since in this case instances of practically or theoretically unsolvable problems occur.

Game

Tile problems can be implemented as a match game. Early as 1880, announced Edwin Lajette Thurston such games for a patent. The tiles can be about isosceles triangles, squares or hexagons.

Jacques Haubrich divides tile problems into seven categories:

The Japanese company K. K. Takara -Tomy Eternity II brought a game on the market, in which 256 parts must be appropriately placed on a 16 by 16 grid fields large. For the first solution 2 million U.S. dollars in prize money was awarded.

Tile problems are implemented with Tetravex as a computer game.

Theoretical computer science

The basic shape of the tiling problem in theoretical computer science is that of rectangular parts in which each of the four sides (also: color) a specific number is assigned. The goal is to flush the parts to be arranged so that when adjacent sides match the two numbers. It usually is added caveat that the parts can not be rotated.

An expression which is a finite square area of the size of n by n parts, which is to be covered by the elements of a full amount of parts. To determine whether there is a solution, has exponential complexity. If any tiling tried, exceeds the latest from n = 5, the computational effort practically manageable.

In another form of the problem of the extent of the tile surface will not be fixed. The elements of tile amount may then be used as often as desired. The question to be answered is whether it is possible to cover a regular compliant with the given tile amount of any finite area. For this problem, it is impossible to write a program that can answer the question in any case. The same is true for an infinite plane with Wang dominoes.