y CompSci 100E Spring 2011: Boggle

# Extra Credit: Tic-Tac-Toe

Standard Tic Tac Toe (ttt) is a game played between two players 'X' and 'O' on the board shown below.

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.

## Rules of the Game

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 |         |   | X

```
After 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.

### Symmetry

Many of the boards generated by the program are the same board because of symmetry. For example, there are are really only three different first moves as shown below.
``` 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 |

```

You should write a program, using the ideas from TicTac.java, that generates every really-different, valid tic-tac-toe board. You can snarf this code or copy it from the code directory.

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.

For example, there are three rotational symmetries: rotate 90, 180, and 270 degrees shown below, respectively, for the board on the left.

``` 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 | X

```
This 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 | 8

```
So 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.