you mathed wrong. 3x3 board with 8 states per cell is 72 total states. 9x8,not 8^9.

Edit, I just considered : Unless you mean that the state is the combination of all the cells. Then you are right