Are you willing to use a computer to solve this?
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.
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
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
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.