Tile problem

from Wikipedia, the free encyclopedia

A tile problem is the task of arranging a set of parts into a whole so that certain rules are followed. Tile problems can be solved as puzzles to pass the time. The theoretical computer science studied tile problems as they may be cases of practical or theoretical unsolvable problems.

game

Tile problems can be implemented as a puzzle game . Edwin Lajette Thurston applied for a patent for such a game as early as 1880. The tiles can be isosceles triangles, squares or hexagons.

Jacques Haubrich divides tile problems into seven categories:

  1. Matching sides: Adjacent sides of two tiles must have the same color, number, ... (example domino ).
  2. Upper and lower part: Instead of bringing the same together as with the matching pages, two-part pairs have to be brought together here, for example to bring the upper and lower part of a figure together.
  3. Paths: By putting them together correctly, a path is not interrupted at any point.
  4. Matching corners: There are markings on the corners of the tiles that must match when the corners are adjacent (example triominos ).
  5. Incorrect corners: The corner markings must not be the same.
  6. Puzzle-like: next to a tile, at most one of the other tiles fits.
  7. Mixed forms

The Japanese company KK Takara-Tomy launched Eternity II, a game in which 256 pieces have to be placed on a 16 by 16 grid. The first solution was awarded $ 2 million in prize money.

Tile problems are implemented as a computer game with TetraVex .

Theoretical computer science

The basic form of the tile problem in theoretical computer science is that of rectangular parts, where each of the four sides is assigned a certain number (also: color). The aim is to arrange the parts flush so that the two numbers match when the sides are next to each other. In addition, there is usually a restriction that the parts must not be rotated.

An expression is that of a finite square area the size of n times n parts, which is to be covered with the elements of a set comprising parts. Determining whether there is a solution is exponential. If every possible tiling is tried out, the computational effort exceeds what can be practically managed from n = 5 at the latest.

In another manifestation of the problem, the scope of the area to be tiled is not fixed. The elements of the tile set can then be used as often as required. The question to be answered is now whether it is possible to cover any finite surface with the given set of tiles in accordance with the rules. For this problem, it is impossible to write a program that can answer the question in every case. The same applies to an infinite level in Wang dominoes .

Individual evidence

  1. ↑ a b Rob Stegmann: Pattern Puzzles: Edge Matching
  2. ↑ Official website for Eternity II
  3. ↑ Solymosi / Grund, p. 181 f.
  4. ↑ Solymosi / Grund, pp. 175–177

literature

  • Andreas Solymosi, Ulrich Grund: Basic course in algorithms and data structures. 3rd edition, Vieweg, Braunschweig / Wiesbaden, 2002.