1. ## The Domino Problem(tiling)????

Hi
I have a logic coursework which is about the domino problem (problem of deciding whether a given set of tiles admits a tiling), and I dont understand properly what the problem is... Can someone give me an easy explanation of what it is.

Thank you

2. Originally Posted by alireza1989
Hi
I have a logic coursework which is about the domino problem (problem of deciding whether a given set of tiles admits a tiling), and I dont understand properly what the problem is... Can someone give me an easy explanation of what it is.

Thank you
A domino is a rectangle twice as long as it is wide. It should be obvious that if you have a tile that is a square with side length equal to the width of the domino, a domino won't fit on it- the domino is too big. If your tile is a rectangle with width equal to that of a domino and length twice that, obviously one domino will fit that exactly. Just as obviously, you cannot fit dominoes onto a rectangle with width equal to that of the domino and rectangle three times the width. In fact, it should not be difficult to see that you can fit dominos onto a rectangle that is the same width as a the domino and an any even multiple of that in length, but not if its length is an odd multiple of the width.

How you would determine whether a particular tile can be covered by dominos depends strongly upon the tile.

But here's a famous example. (I hope it's not YOUR problem!) Suppose you have an 8 by 8 chess board and your dominos have width equal to the width of 1 square and length equal to two such widths. It should be obvious that such a board can be covered by dominos (because each row can be covered by 4 dominos). Now remove two diagonally opposite squares. Can that be covered by dominos? If we had removed just one square the answer would be "obviously not" because there would be an odd number of squares to cover and each domino covers two squares. But removing two squares leaves an even number of squares so it still might be possible to cover a board with opposite corners removed.

Now suppose the board is colored like a standard chess board, alternating colors. Each domino will cover two DIFFERENT colors but removing the opposite corners we have removed two square of the same color. Since there are not, now, the same number of squares of each color, it is impossible to cover this by dominos.