Conjecture of a subset of Wang tile which might be decidable From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:
The left color and right color do not uniquely determine the top color and bottom color.
The tiles involved in practice in material science and physics for one big problem is actually more restricted and the tiling problem might actually turn out to be decidable.
So the subset of Wang Tile is lattice tiles, shown in my previous post:
Reference for Wang Tile
The general feature of the tile is that the pair (left color, right color) uniquely determine the pair (top color, bottom color).
I conjecture that a subset of Wang tiles which satisfies the restriction above might turn out to be decidable...
Any thought on this problem? Thank you.
 A: It is a very nice question!
But I claim, unfortunately, that the tiling problem for your special kind of tile sets
is also undecidable. Specifically, I claim that the ordinary Wang
tiling problem reduces to an instance of your kind of tiling
problem. That is, if we are given a finite list of ordinary Wang
tiles $w_0,\ldots, w_n$, then we can create (according to a
computable procedure I shall presently explain) a new set of tiles
$t_0,\ldots,t_k$, such that the original set of tiles admits a
tiling if and only if the new set admits a tiling, and furthermore
the new set of tiles $t_i$ obey your deterministic property.
The new tiles are obtained from the previous tiles by annotating
the labels on the original tiles. Given any Wang tile $w$, labeled
with $1$ and $2$ on the left and right side, respectively,
                    -------------
                    |     3     |
                    |           |
           w   =    |1         2|
                    |           |
                    |     4     |
                    -------------

and for each tile $u$ with a label of $1$ on the right (so that it
could legitimately form $uw$), we create a tile $t_{u,w}$ labeled
by $(u,1)$, $(w,2)$ on left and right, respectively, and otherwise
the same as $w$ on top and bottom. That is, we think of $(u,1)$  and $(w,2)$ as individual new colors in the new tile set. 
                    -------------
                    |     3     |
                    |u         w|
   t_{u,w}   =      |1         2|
                    |           |
                    |     4     |
                    -------------

The meaning of the annotation is that the right-hand side label
$(w,2)$ indicates $w$ and therefore contains all the information needed to know the top and
bottom labels, and we add $(u,1)$ on the left simply so that it
can match the corresponding new tiles corresponding to some $u$
that could match with $w$.
Thus, if $uw$ can be extended to a sequence $ruw$ in the original
tiling, then $t_{r,u}t_{u,w}$ is legitimate in the new tiling. So
any tiling of the plane using the original tiles can be
transformed into a tiling using the new tiles. Conversely, if
$t_{r,u}t_{u',w}$ is legitimate in the new tiling, then it must be
that $u=u'$ becase the annotated labels match, and furthermore $uw$ is 
legitimate in the original
tiling, since we only made $t_{u,w}$ when $uw$ was legitimate. So every tiling with the new tiles immediately produces a
tiling using the old tiles. (Indeed, the tilings themselves are
computable from one another.)
Finally, the new tiles obey your deterministic property, because
the annotations on the side labels contain all the information
necessary to determine the top and bottom labels. Indeed, the right color alone determines the top and bottom colors on these tiles, and severely restricts the possible left colors as well. 
A: If you're interested in restriction of the domino problem to tile sets with some determinism properties, you might also be interested in this result about 4-way deterministic tile sets.
