Using your Head is Permitted

Consider a jigsaw puzzle that has already been put together. It is composed of tiles, each tile being connected to several other tiles. We will assume that there is a maximum, d, for some constant d, for the number of tiles that can be neighbors to any single tile. In a standard jigsaw puzzle d=4. In mathematical formulation, we can say that the finished puzzle is described by a connected graph, where each tile is a vertex and an edge is drawn between two vertices if the two tiles are connected. A jigsaw puzzle is therefore described by a connected graph with max-degree d.

Let n be the number of tiles in the puzzle. The problem in a jigsaw puzzle is that we need to determine which tile should be associated with which vertex. We can therefore say that there is an unknown permutation over n elements, that describes which tile is which puzzle piece, and solving the jigsaw puzzle means finding out what the permutation is. (Technically, one should speak here of a one-to-one and onto mapping from the vertex set to the tile set, and not of a permutation, but, for brevity, I use the terminology "permutation", which is how such a bijection is likely to be interpreted, for example, in a computer implementation: as a re-ordering of the tiles.)

Let us consider, for a moment, what tools are given to the puzzle solver in order to discover the permutation. First, on the assumption that this is a pictorial puzzle (a puzzle with a guiding image), every tile has a small fraction of the guiding image, and the puzzle solver will normally first arrange the tiles according to what she can see of the image, in order to get a rough idea of where in the puzzle each piece is to be placed.

The next thing that a puzzle solver does normally is to arrange the tiles by their shape, in order to find out which pairs have a chance of fitting together.

In the process of solving the puzzle, one would normally make several passes of this procedure, each time sifting the tiles according to finer distinctions. However, ultimately one has to compare a specific tile against a specific piece of the guiding image or to actually try out two tiles to see if they can be connected.

Much of what is written in the computer science literature regarding puzzle solving has to do with this iterative process of partitioning the tiles into subsets. In computer implementations, this is normally done by a hash function of sorts.

The specific question for this month has to do with communication complexity, and it is a well-known fact that hashes, although very useful in shortening time constants by large factors, make no difference for the worst-case complexity of any given computation. We will therefore ignore these hashes completely, and model jigsaw puzzles as follows:

As stated before, the puzzle is defined by a connected graph with n vertices (n being our parameter for complexity computations) and max-degree d (d being a constant). The initial state of the puzzle is an unknown permutation over n elements, and the solving algorithm must find out what this permutation is by use of the following two types of Oracle calls:

• (For pictorial puzzles) Given a tile and a position in the puzzle-graph, determine whether the tile fits the puzzle position.
• Given two tiles, determine whether they can be fit together.

In order to be considered a solver for this month's riddle, determine the minimum possible communication complexity for this task and describe an algorithm solving a particular sequence of jigsaw puzzles with constantly increasing n that works in this complexity. The question should be solved twice: once for pictorial puzzles and once for apictorial puzzles (puzzles which have no guiding image, and therefore only support the second type of Oracle calls). The names of people solving both parts will be noted on this page.

Note: For the purposes of this question, you can assume that if the Oracle answers "yes" on any particular query, then her answer should be interpreted not only as "this tile can fit this image location" or "these two tiles can be connected" but rather as "this tile is the tile that will be placed in this position in the final construction" and "these two tiles are connected in the final construction", respectively. The family of puzzles in which tiles can be locally fitted together, or locally fitted to image locations, even though in the final construction these fits ultimately turn out to be red herrings is considered to be more difficult than the family of standard puzzles, where each tile has only one position that it fits and only connects well to its true neighbors. We do not consider this more complicated form of puzzles here.

List of solvers: