Saturday, March 29, 2008

Counting the number of distinct NxN Reversi games

The Reversi board looks symmetric at the start of a game. It can be rotated by half a turn or reflected at the diagonal and will look the same.

For the first move black can play four positions as shown here for a 6x6 board:

But no matter where black chooses to put the disk, I can rotate the board and/or look at it in a mirror, and it will look as if black put the disk on the field in the third row, second column.
So, without loss of generality, we may as well assume that black always plays that position! This breaks all ambiguities. There are no symmetries after the first move.

In general, on a NxN board I assume that black always plays in the field with the lowest column number first. On a board with even N that is column (N/2)-1, row N/2. For boards with odd N it is column (N-1)/2, row (N+1)/2. (For the odd N boards the game will be different if black plays on one of the sides with fewer fields to the edge of the board. Nonetheless, I will only consider the first move for black as described above.)

After the first move on a 6x6 board, the board will look like this:

No comments: