Search code examples
tic-tac-toe

Representing a tic tac toe board in computer memory,

I am trying to solve this problem: Design a method for representing the state of a tic-tac-toe board in computer memory. Can you fit your representation into three bytes?

This is from a textbook without solutions, thank you!

Any help is appreciated!

Solution

  • The state of a Tic-Tac-Toe board can be encoded using 3 bytes as follows.

    To represent the state of each cell, 3 states are necessary, namely X, O and undefined. 3 states can be represented by 2 bits (2 bits can in fact represent 4 states, but only 3 are needed here - on the other hand, 1 bit is insufficient).

    There are 9 cells in total, so in total

    2 * 9 = 18

    bits are necessary to represent the board. 18 bits can be encoded in 3 bytes (which in total have 24 bits, which means that 6 bits are not needed).