[Haskell-beginners] A good data structure for representing a tic-tac-toe board?

Brent Yorgey byorgey at seas.upenn.edu
Mon Mar 18 21:59:55 CET 2013

Consider the following game:

Two players take turns choosing a number from 1-9 (inclusive).  Once a
number has been chosen it cannot be chosen again.  The winner is the
first player to have three of their selected numbers which sum
to 15.

Surprisingly, this game turns out to be isomorphic to tic-tac-toe,
which can be seen by arranging the numbers from 1-9 in a magic square,
such as

8 3 4
1 5 9
6 7 2

It is not hard to check that three distinct numbers from 1-9 sum to 15
if and only if they correspond to a tic-tac-toe win on the board
above.  This means you can represent the state of the board as a pair
of sets.  To check the state of a cell you look up the corresponding
number from the board above in both sets.  To mark an empty cell you
add the corresponding number to one of the sets.  To check whether a
player has won, you list all size-3 subsets of their set and check
whether any of them sum to 15.

You may or may not agree that this fulfills your criteria, but at
least it is cute.


On Mon, Mar 18, 2013 at 03:54:58PM +0000, Costello, Roger L. wrote:
> Hi Folks,
> Currently I am representing a tic-tac-toe board as a string, with 'X' denoting player 1 and 'O' denoting player 2. For example, I represent this 2x2 game board:
>      'X' 	|  
> -----------------------
>   	|   'O'
> with this string: "X  O"
> The nice thing about that representation is that it is each to identify which cells are filled or empty, and it is easy to mark a cell with an 'X' or 'O'.
> The problem with the representation is that it is difficult to determine when a player has won.
> Can you recommend a representation that makes it easy to:
> 1. determine when a player has won
> 2. identify cells that are filled or empty
> 3. mark an empty cell 
> /Roger 
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners

More information about the Beginners mailing list