A while back I was given a jigsaw puzzle shaped like a globe as a present.
This departure from the standard mesh shaped jigsaw puzzle led me to wonder
what it is that makes something into a jigsaw puzzle. The following is my
initial formulation for an answer to this question in mathematical form,
and this month's riddle deals with the first theorem I was able to prove
regarding this model of jigsaw puzzles.
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,
Let 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 - (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.
n. It is clear
that this value cannot be larger than O(n^{2}), because
in this amount of information we can ask the Oracle every possible
question that she can answer. We want to know whether there is any algorithm
that allows solving the puzzle in less than O(n^{2})
Oracle calls. The algorithm does not need to be able to solve every
jigsaw puzzle. It's enough that you show that there is some infinite series
of jigsaw puzzles with constantly increasing n (and constant d)
that can be solved using it in less than O(n^{2}) calls.
(Unlike the choice of puzzle, which will be free and can be tuned to a
best-case scenario, assume, for complexity calculations, the worst-case
set of Oracle answers for any given algorithm.)
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 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:Oded Margalit (10 October 18:00) |

Elegant solutions can be submitted to the puzzlemaster at __riddlesbrand.scso.com__.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!