Placing Chain Of Colored Links Into A Grid

[Leroy Quet]

[I had thought I had sent the below, which I posted to sci.math in 
mid-October, to seq.fan already, but it is not in my in-box from this 
group. If I have already sent it to you all, then I apologize.]

So, there were never any replies to any of my questions (which were 
poorly asked, in any case) anyhow.  I will send the post to seq.fan 
because of the possible sequences that might result from specific cases 
of the below (such as the number of possible placements when the chain is 
colored according to some predetermined rule).

----


Let us say we have a loop of chain (or we have a necklace) of m^2
links/beads, each link/bead colored with one of n colors.

Now, we take a m-by-m grid, over which we can place the chain so that
each square contains exactly one link.
(m is even.)

How many ways can we expect to be able place the chain so that no
similar colors are in any immediately adjacent (up/left/down/right)
squares?

(Of course, the exact number varies according to how the links are
colored. I guess I am just wishing for some analysis on this. Perhaps
the number is exactly determined or approximated asymptotically based
on some statistic of how the chain is colored.)


And what would the number be in the range of, if the chain need not be
a loop?
(m may be either odd or even, in this case.)

This question was directly inspired by this puzzle from way back:

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&safe=off&threadm=b4be2fd
f.0211291522.548ca740%40posting.google.com&rnum=13&prev=

I wonder if I can get any idea if any such maze has multiple solutions
(after rotation/reflection), and if so, what would the magnitude of
this number of solutions be.


thanks,
Leroy Quet