Try this website for an explanation of the rules and to play the game (against a rather dumb opponent).

For this extra credit program you'll write a program that calculates the number of different tic-tac-toe boards there are, taking many factors (e.g., symmetry) into account.

Traditionally 'X' goes first, and there are 9 locations in which 'X' can go. There are nine "different" boards with one 'X' as shown below. (See the discussion on symmetry for why there are really only 3 different boards.)

X | | | X | | | X | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | | X | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | | | | | | | | | | | | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | X | | | X | | | | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | X | | | X | | | XAfter this spot is taken there are 8 locations for 'O' to go so there are 72 (9*8) different boards with one 'X' and one 'O'. Continuing with this reasoning leads to 9*8*7*6*5*4*3*2*1 = 9! different board configurations in which all squares are taken with 5 X's and 4 O's since X goes first. Note that in the real game one player may win before all squares are taken, but 9! is an upper bound on the number of boards with all squares taken.

The total number of boards, i.e., with one X; one X and one O; two X's and one O, and so on is then

9 + 9*8 + 9*8*7 + 9*8*7*6 + 9*8*7*6*5 + ... + 9! = 986,409

The program TicTac.java generates
each of these boards and stores
each of the 986,409 boards in an `ArrayList`

.
Note that there are lots of duplicate boards, for example consider the two
sequences of moves below which lead to the same board. The
third board in each row below is generated twice by
the program since it places an X in every location, then an O
in the remaining locations, and so on.

X | | X | O | X | O | X ---+---+--- ---+---+--- ---+---+--- | | | | | | ---+---+--- ---+---+--- ---+---+--- | | | | | | | | X | O | X X | O | X ---+---+--- ---+---+--- ---+---+--- | | | | | | ---+---+--- ---+---+--- ---+---+--- | | | | | |If all the duplicates are removed from the vector of 986,409 there are 6,045 different boards generated. In a real sequence of games, not all of these could be generated since once a player wins, no more X's or O's are placed, but the program TicTac.java doesn't take this into account.

X | | | X | | | ---+---+--- ---+---+--- ---+---+--- | | | | | X | ---+---+--- ---+---+--- ---+---+--- | | | | | |The other moves are all symmetric to, or the same as, one of these. For example, any corner move is the same for the first move for the purposes of strategy in playing the game. Similarly, there are 12 really different boards containing one X and one O if symmetry is taken into account, as shown below.

X | O | X | | X | | O X | | X | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | O | | | | | | | O ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | | | | O | | | O | | | O ---+---+--- ---+---+--- | X | | X | ---+---+--- ---+---+--- | | | | O | X | | X | | X | | X | | X | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | O | | | | O | | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | | O | | | O |

In determining unique boards you must take the following into account.

- Once a game has been won, no more moves are made.
- All symmetry is taken into
account.

X | O | | X | X | | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- X | | | | O | | X O | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | O | X X | X |There are four reflective symmetries: horizontal, vertical, left/right-diagonal, and right/left-diagonal as shown below, respectively, for the board on the left.

X | O | | | | O | X X | X | | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- X | | X | | | | X O | | | | O ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | X | O | | | | | | X | XThis means there are eight symmetric representations of the left-most board on each line above. Instead of storing and printing all eight, your program will store and print just one -- details as to which one are provided below.

The output from your program should be every really-different board printed, one board per line, with each line consisting of 9 characters, either 'X' or 'O' or space ' '. Use the numbering/indexing scheme below

0 | 1 | 2 ---+---+--- 3 | 4 | 5 ---+---+--- 6 | 7 | 8So that the string "X O OX X " represents the board below.

X | | O ---+---+--- | O | X ---+---+--- | X |This means the number of lines your program prints is the number of really-different/not-symmetric, valid tic tac toe boards.

**Your program's output should be in lexicographical/sorted
order**. This means that if you've stored strings representing
the boards in an ArrayList, you'll need to sort it before printing.

For each possible board, if there's more than one representation of the
board when taking symmetry into account you must use the
*lexicographically smallest* of these symmetric boards.

For example for the eight symmetric boards above, their string representations are shown below.

'XO.X.....' '.XX..O...' '.....X.OX' '...O..XX.' '...X..XO.' '.OX..X...' 'XX.O.....' '.....O.XX'

Of these, the last board is the lexicographically first since a space comes before either 'O' or 'X'.

This means, for example, that when creating a board you can generate all
possible symmetries, sort the representations (as strings) and the
smallest/first one will be the board to keep. Think about how to
structure data to help. In Java, you can create a String from an
array of char values and you can generate such an array from a
string. This is helpful since you can't change a string once it's
been created, strings are *immutable*.

Your README should include your thoughts of the assignment, a list of people with whom you discussed the assignment, and how much time you spent on it.

Last modified: Mon Apr 11 23:26:58 EDT 2011