The contractor of the previous example has a specific wall to tile, only 5 by 5. The programmer, still undaunted, undertakes to write a program which will accept data on the border colours of any 25 tiles, and determine if those tiles can be used. This program can be written. The simple-minded way to do it involves trying each of the 25 tiles in the first square on the wall, for each of these trying the remaining 24 tiles in the second square, and so on: 25*24*..*2*1 = 25! combinations will determine whether the problem can be solved (and find a solution if it can).

Unfortunately, even if we have an ultra fast computer, which can test one complete combination in 20 picoseconds (1/50 microseconds), the complete test will run for approximately the present lifetime of the universe. N! gets too big too fast.

There are less simple minded ways to write this program, and they will run faster. But no method now known escapes the buildup of complexity illustrated by N!. Furthermore, Stephen Cook in 1970 showed that there is a class of problems, all equivalent to each other in a precise sense of "complexity", which stand or fall together. Our second tiling problem is in this class, along with over 1000 other, apparently unrelated, problems. None have been shown to escape intractibility, but if only one does then so do all the rest. Computer scientists currently believe that this class of problems will remain intractible. Harel's book also discusses these issues.