hw9
			    Extra Credit
	      [ The lowest hw grade will be raised to 100 if you are
		successful on this.  Due by Thursday, April 28. ]

You must produce a BDD that counts the number of winning games by "x"
after 7 moves.

Your program should print the number of winning games by "x" after
7 moves.  As before, please also include the source code for your program.
This work must be absolutely individual.

Note that after 7 moves, "x" will have made 4 moves, and "o" will have
made 3 moves.

===

Here is a warm-up that you are _not_ required to hand in.  (If Monday had
not been a holiday (Patriot's Day), then we would have done this as
a regular assignment.)

Note that Buddy is a package for BDDs.  It is available at:
  http://buddy.sourceforge.net/manual/main.html
OR:
  http://sourceforge.net/projects/buddy/

Buddy has also been set up in the course directory.  The program runs in C++.
On our CCIS Linux computers, g++ is the standard C++ compiler.
In particular, you may want to look at
  /course/cs5800gc/buddy-2.4/examples/count-simple
for an example code that is intended to be easy to read.
It counts how many ways there are to set k out of n variables to true.
USAGE:  count k n
(For example, count 1 2  returns 2 (two ways to set 1 out of 2 variables
 to true))

The best manual for Buddy is the include files:
  buddy-2.4/include/bdd.h
    declares the main functions:  bdd_and(,) bdd_or(,) bdd_not() etc.
  buddy-2.4/include/bvec.h
    declares the C++ operators:  & (and) | (or)  ^ (xor) ! (not)
Try /course/cs5800gc/buddy-examples/count-simple.tar.gz for an example
  of a buddy program.

To compile and run the file /course/cs5800gc/buddy-examples/count-simple.tar.gz
  on a CCIS College Linux computer, do:
    tar zxvf /course/cs5800gc/buddy-examples/count-simple.tar.gz
    cd count-simple
    make

To create your own program,  modify the directory name to your myprogram,
modify count.cxx to myprogram.cxx, and modify
"FILE=count" in Makefile to:  FILE=myprogram
You will also need to modify "ARGS=" in Makefile to the arguments
that you want to pass to your program.

This homework and the next one will have the theme of tic-tac-toe.
If you have never played tic-tac-toe, there is a description
of the game at:  http://en.wikipedia.org/wiki/Tic-tac-toe

Assume the 9 squares are labeled squares from left to right.
So, the first row is squares 1,2,3.  The second row is squares 4,5,6.
The first column is squares 1,4,7

Let x1 mean there is an x in square 1 of the tic tac toe board.
For row one, no one wins in that row can be written:
  x1 | x2 | x3    [There is at least one "x" in row one.]
  !x1 | !x2 | !x3 [There is at least one "o" in row one.]

First, write a buddy program with a logical expression indicating
that it is a tie game:  no one wins in any row, column, or diagonal.
It's okay for now if one player made more moves than the other player.
Call this boolean expression:  E1

Run the buddy program and find out how many possible tie games there are.

If you have trouble debugging your buddy program, then you can
debug it by setting x1, x2, ... to values for which your program is
getting the wrong answer.  For example, if your program thinks
x1 = x2 = x3 = x4 = ... = true is a tie game, then near the
beginning of your program, write:
  x1 = x2 = x3 = x4 = x5 = x6 = x7 = x8 = x9 = bddtrue;

Then run the program in your favorite debugger, or else use print
statements, to print the values of your intermediate bdd expressions.
Since the 9 variables were all set to constants (true or false),
all intermediate bdd expressions will also be constants (true or false).
You can then decide if your intermediate bdd expressions are correct
for the example input that you are using.


When you are done, report the number of solutions for:
1.  E1, the number of boards with a tie game.
2.a.  Report the number of boards in which "x" wins.
	(Note that "x" wins if, among the nine squares,
	there is an "x" on five squares and an "o" on four squares,
	and it is not a tie, and "o" does not have a win.)
	You can use the function bdd_count() in count.tar.gz
	to help you construct the bdd.  Then use bdd_satcount() to
	count the number of solutions satisfying it.
2.b.  Also, hand in the BuDDy source code that you used to answer this question.
3.  Give an English explanation for how Buddy can very quickly
	produce a bdd for bdd_not(E1), if it already has a bdd for E1.
4.  The BuDDy function bdd_satcount() takes a bdd as a solution and
	reports how many solutions there are for the Boolean variables.
	Describe a dynamic programming algorithm (no programming,
	just the pseudo-code or English description) that will compute
	the total number of solutions.