A contractor has been offered a special deal on a practically unlimited supply of tiles for tiling the walls of rooms in future buildings to be constructed. He must accept the deal now, and cannot wait to know the size of any of these walls. The tiles are square, all have a smiling sun at the centre, and are bordered in various colours, possibly different colours for each edge. For example, three such tiles are (shown sideways) 
		   W		   W		   B
		B :-) W		W :-) R		R :-) B
		   W		   B		   W

		   1		   2		   3
where B is blue, R is red, and W is white, the colours around the borders. The contractor knows that customers will only buy houses where the tiles have been set so that the edges of adjacent tiles have the same colour. Thus, he can put tile 1 directly on top of tile 2, but not directly on top of tile 3.

Can the contractor use these three tiles for any size wall? Yes. For example, here is a 5 by 5 wall (also shown sideways). 

				1 2 3 1 2
				2 3 1 2 3
				3 1 2 3 1
				1 2 3 1 2
				2 3 1 2 3
But the tile company, as is often the case with special deals, supplied the wrong information. Actually, tiles 2 and 3 have their bottom colours swapped, red for blue. Now it is impossible to tile even a 3 by 3 wall.

The contractor knows an enthusiastic programmer, who taught herself and never learned computer science. She offered to write a program which would, quite generally, accept a description of the border colours of any number of different types of tile, and come out with a warning not to buy the set of tile types if in fact they cannot be used.

Unfortunately for the programmer, such a program has been proven impossible to write. The proof may be found, in simple terms, in "Algorithmics: The Spirit of Computing", by David Harel (Addison-Wesley Publishing Company, 1987, 1992). It proceeds by showing that if the tiling problem can be solved, then so can the "halting problem". Alan Turing (the person most computer scientists consider to be the founder of the discipline) proved this impossible in 1937. His proof involves a program which determines whether it itself halts or runs on forever, and derives a contradiction.