On the solvability of domino snake problems (Q1331945)

Tiling problems, originally introduced by Hao Wang in 1962, show a wide variety in complexity and decidability status, depending on the precise nature of the region to be tiled, the presence of boundary conditions and possible further constraints. At the same time these problems provide a nice starting point for reductions to other combinatorial problems in order to establish complexity lower bounds or undecidability for those problems. The class of tiling problems considered in this paper is of a quite different nature, since one does not want to completely tile a given region, but only to connect a pair of given locations by a connected path, called a snake. Again the problems have a great variety in complexity and decidability status, where most problems seem to have the sort of complexity one might expect given the general results about tiling. The main result in this paper however shows that the unrestricted snake problem over the entire plane is decidable; a result which is peculiar as a number of related problems with minor additional constraints have previously been shown to be undecidable. These undecidability results are to a large extent based on work by Ebbinghaus published in 1982. The history of the result is that 15 years before the publication of this paper the last author Dale Myers claimed the result in the Notices of the Am. Math. Soc., but subsequently never published a proof. When the other two authors recently provided a proof which they submitted for publication in Theor. Comput. Sci. (with credit given to Myers), Myers himself submitted a full version with proof to the same journal. Eventually the two submissions generated this joint paper. It is instructive to inspect the general outline of the decidability proof. If two locations can be connected by a snake, there also exists a minimal snake establishing the connection. This minimal snake is shown to have some powerful properties of a topological and geometrical nature. It will not be self-intersecting but it also does not intersect any of its translates over an integer multiple of the vector expressing the distance between the starting and the endpoint of the snake. Based on this observation, one can show that the entire snake resides within an a- priori bounded region of space, and this key insight does not only lead to decidability but even to a PSPACE-algorithm for the problem.