ON THE SOLVABILITY OF DOMINO SNAKE PROBLEMS

In this paper we present an extensive treatment of tile connectability problems, sometimes called domino snake problems. The interest in suc h problems stems from their relationship to classical tiling problems, which have been established as an important, simple and useful tool f or obtaining basic lower bound results in complexity and computability theory. We concentrate on the following two contrasting results: The general snake problem is undecidable in a half-plane (due to Ebbinghau s), but is decidable in the whole plane. This surprising decidability result was announced without proof by Myers in 1979. We provide here t he first full proof, and show that the problem is actually PSPACE-comp lete. We also prove many results concerning the difficulty of variants of these general snake problems and their extension to infinite snake s. In addition, we establish a resemblance between snake problems and classical tiling problems, considering the corresponding bounded, unbo unded and recurring cases.