A Rust library that provides a 2 byte representation of a tic-tac-toe grid.

I read an article where a tic-tac-toe grid was represented by two bitsets of length 9, one for the Xs one for the Os, and it got me thinking. That representation is with 18 bits just over 2 bytes and it allows illegal grid states, where a field is both filled by X and O.

Given that the grid has 9 fields and each field has 3 possible states (Blank, occupied by X, occupied by O), there are 3⁹=19683 possible grids. To enumerate all of these grids, 15 bits are needed (ld(19683) < 15).

As we have 9 fields with 3 possible states each, we can encode a field as a trinary number with 9 digits.

Each field state is given a value:

Each field is given a digit x_n:

x_0 | x_1 | x_2
----+-----+----
x_3 | x_4 | x_5
----+-----+----
x_6 | x_7 | x_8

Then the value for the grid is calculated as follows:

grid = x_0 + x_1 * 3 + x_2 * 3² + x_3 * 3³ + x_4 * 3⁴ + x_5 * 3⁵ + x_6 * 3⁶ + x_7 * 3⁷ + x_8 * 3⁸

No.

This library still allows the representation of states that can never appear during normal play. For example a grid where every field is occupied by Xs.

This library also does not take advantage of the symmetries of the rules of tic-tac-toe.