[comp.theory] A Tiling Problem - Is is NPC?

joshi@m.cs.uiuc.edu (Anil Joshi) (12/01/90)

Hi Everybody.

   I thought about this problem and had been trying to prove that it is
NPC because it seems a hard one. I am no successful yet. Here I go.

Given a square grid and dominoes of say 2 different colors randomly
placed on the board. We can assume that the number of dominoes of each
color are n and the grid is N X N. and 2n <= N^2. Also given is an axis
(wlog vertical line going throuh the center).  Also given is a number k.
Question: Is it possible to arrange the blocks symmetrically along the
axis of symmetry with <= k number of moves? A move is defined to be
moving a dominoe along x or y direction on square.

Anil Joshi (joshi@cs.uiuc.edu)