1. ## Hard combinatorics question

Let's say that I have a chess board (64 squares), and I want to color it using 5 colors (green, red, blue, yellow and black), but making sure that neither of the colors touch each other. How many different boards can I make?

To clarify a bit: let's say that the square b2 is blue. Then the following squares can't be blue: b3, b1, a2 and c2. But the following squares can be blue: a3, c3, a1 and c1.

2. ## Re: Hard combinatorics question

Hey oveluus.

Are you willing to use a computer to solve this?

3. ## Re: Hard combinatorics question

Yes, even though I was hoping for a more general formula.

I know nothing about programming so you'll have to help me with that.

4. ## Re: Hard combinatorics question

If you colour as follows:

1. colour the lowest left corner
2. colour the 3 squares around that corner
3. colour the 5 squares around this new larger square
etc.

Then there are 5 ways of doing the first step.
For each remaining step start at the lowest square and work counter clockwise. The first square to be coloured can be done in one of four ways, the highest rightmost (diagonal square) can be coloured in one of four ways all remaining squares can be coloured in one of three ways.

So by my reconing there are $5*3^1*4^2*3^3*4^2*3^5*4^2*3^7*4^2*3^9*4^2*3^{11}*4 ^2*3^{13}*4^2=3^{49}4^{14}5$

Now I might have over counted because the board can be rotated through 90, 180 or 270 degrees and you may or may not want to cound boards with rotational symetry as being identical.