Algorithm for a n x n grid of squares

Question

Say we have a puzzle where by there are $n^2$ squares and each of the 4 sides of each square has a colour. The aim of the puzzle is to see if the squares can be arranged in such a way that when 2 squares are adjacent they must have the same colour sides touching. How could we non-deterministically and deterministically solve the puzzle? The algorithm can be treated as a function of n. Is this in polynomial time? (I think we can for non-determinitcally, not sure about deterministically) If you know, can the algorithmic steps be expressed in natural english language please.

Answer 1

There deterministic algorithm for solving the puzzle is quite simple -- just try all the possible configurations of the squares and see if any of them works (verifying one particular configuration is simple; one just needs to check the $2n(n-1)$ adjacent sides of squares). Depending on the exact interpretation of the possible arrangements (e.g. are the squares placed in the grid and we're only allowed to rotate/flip them, or is it more like jigsaw puzzle pieces we are putting into an empty board, so we're free to place each square wherever we want?), the number of possible configurations is most likely to be super-exponential in $n$; and so will be the algorithm execution time.

Non-deterministic approach has an important advantage -- instead of trying all the possible arrangements, it can just "guess" the right one and then verify it. As indicated above, such checking can be done in polynomial time, since there is only a polynomial number of adjacent sides to be checked.

Whether this puzzle can be solved in polynomial time deterministically... that's most likely a quite difficult question. At the moment, I don't see any obvious polynomial-time deterministic algorithm, but actually proving that one cannot exist would amount to resolving the P=NP problem :-)