Compsci 100, Fall 2006, 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.

all the unique boards


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 |    


Your Program

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 linked site here. The snarf site is www.cs.duke.edu/courses/cps100/fall06/snarf

This means that once a game has been won, no more moves are made. All symmetry is taken into account. 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

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 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 symmetric boards above, their string representations are (from top-to-bottom, left-to-right in each of the two rows using '.' instead of space ' ' and not repeating the same board twice):

"XO.X....."
"...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'.

Grading

This is worth 15 points. It will take longer than 15 program points are really worth, but these are bonus points that can help move your final letter grade, not simply program points.

Submit

To submit use Ambient and tictac for submitting.

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

Why Philosopher's Can't Count; this article mentions symmetry, but not duplicate boards.


Owen L. Astrachan
Last modified: Wed Feb 22 22:24:37 EST 2006