#include <iostream.h>

#include <stdlib.h>

#include <fstream.h>

//Define the state structure

struct state { int b[9]; };

//Output file that contains start boards and defined next boards

ofstream fout("create.dat");

//Number of Boards to be Questioned

int maxNumberBoards;

int totalDefined = 0;

//Array of states that are prompted to user

state s[1000];

//when displaying the boards, 0=nothing, 1=X 2=O

char sym[3] = {' ','X','O'};

//When choosing the placement of the mark, this array translates

//the number from the numberpad to the board array number

int NUMBERPAD[10] = {0,6,7,8,3,4,5,0,1,2};

//Permutations on the board

void rotate(int);

void flipHoriz(int);

void flipVert(int);

void flipLLUR(int);

void flipULLR(int);

//Checks if there are any boards that are exactly equal to INT

int anySimilar(int);

//Checks if board at location INT is exactly equal to INT

int equals(int, int);

//Checks if there are any other boards that match INT (w/permutations)

int anyOthers(int);

//Checks if the board INT is done (win by either party)

int checkdone(int);

//Checks if INT is equal to INT (w/rotations)

int completeEquality(int,int);

/******************************************************************/

int main() {

cout << "Number of boards to question:";

cin >> maxNumberBoards;

srand(maxNumberBoards); //Seed random with # board input

//Prompt for maxNumberBoards boards

for(int i = 0; i < maxNumberBoards; i++)

{ int numberX, numberO;

do {

//Initialize the board to all empty spaces

for(int b_init = 0; b_init < 9; b_init++)

{s[i].b[b_init] = 0;}

//Randomly choose the number of X's and O's

numberX = rand() % 4;

numberO = numberX - rand() % 2;

if (numberX == 4 && numberO == 4)

{numberO = 3;}

//Place the X's on the board

for(int Xloop = 0; Xloop < numberX; Xloop++)

{int pos = rand() % 9; //pick a pos

while (s[i].b[pos] != 0) //until it is

{pos = rand() % 9;} //an open space

s[i].b[pos] = 1;} //mark it

//Place the O's on the board

for(int Oloop = 0; Oloop < numberO; Oloop++)

{int pos = rand() % 9; //pick a pos

while (s[i].b[pos] != 0) //until it is

{pos = rand() % 9;} //an open space

s[i].b[pos] = 2;} //mark it

} while (anyOthers(i) == 1 || checkdone(i) == 1);

//Keep trying to generate random boards until a completly unique

//board is generated.

//Display the generated board

cout << "Board #:" << i << endl;

cout << sym[s[i].b[0]] << '|';

cout << sym[s[i].b[1]] << '|';

cout << sym[s[i].b[2]] << endl;

cout << "-+-+-" << endl;

cout << sym[s[i].b[3]] << '|';

cout << sym[s[i].b[4]] << '|';

cout << sym[s[i].b[5]] << endl;

cout << "-+-+-" << endl;

cout << sym[s[i].b[6]] << '|';

cout << sym[s[i].b[7]] << '|';

cout << sym[s[i].b[8]] << endl;

int place; //The number hit on the numberpad

int numType; //The type of mark that is to be put down

//Prompt for the placement of the mark, and also determine mark type

cout << "Placement of ";

if (numberX == numberO || numberO == -1)

{cout << "*X*";

numType = 1; }

else

{cout << "*O*";

numType = 2; }

cin >> place;

int boardsDefined = 0; //Number of actual boards defined

boardsDefined++; //regular board

//Copy the board 8 times for the permutations

for(int k = 0; k < 9; k++)

{s[900].b[k] = s[i].b[k];

s[901].b[k] = s[i].b[k];

s[902].b[k] = s[i].b[k];

s[903].b[k] = s[i].b[k];

s[904].b[k] = s[i].b[k];

s[905].b[k] = s[i].b[k];

s[906].b[k] = s[i].b[k];

s[907].b[k] = s[i].b[k];}

//The 8 permutations

rotate(900);

rotate(901); rotate(901);

rotate(902); rotate(902); rotate(902);

flipHoriz(903);

flipVert(904);

flipLLUR(905);

flipULLR(906);

//Check the 8 permutations, if each is unique, add it to total

for(int ck = 900; ck < 907; ck++)

{ if (anySimilar(ck) == -1)

{boardsDefined++;} }

fout << boardsDefined << '#';

totalDefined = totalDefined + boardsDefined;

//Output starting board

fout << s[i].b[0] << s[i].b[1] << s[i].b[2];

fout << s[i].b[3] << s[i].b[4] << s[i].b[5];

fout << s[i].b[6] << s[i].b[7] << s[i].b[8] << ':';

//Copy starting board to temporary spot 900

for(int j = 0; j < 9; j++)

{s[900].b[j] = s[i].b[j];}

//Check for Horizontal Symetry in the board

int HorizSym = -1;

flipHoriz(900);

if (equals(900,i) == 1)

HorizSym = 1;

flipHoriz(900);

//Check for Vertical Symetry in the board

int VertSym = -1;

flipVert(900);

if (equals(900,i) == 1)

VertSym = 1;

flipVert(900);

//Check for Lower-Left Upper-Right Symetry

int LLURSym = -1;

flipLLUR(900);

if (equals(900,i) == 1)

LLURSym = 1;

flipLLUR(900);

//Check for Upper-Left Lower-Right Symetry

int ULLRSym = -1;

flipULLR(900);

if (equals(900,i) == 1)

ULLRSym = 1;

flipULLR(900);

//Place the mark on the board

s[i].b[NUMBERPAD[place]] = numType;

//Output the marked board

fout << s[i].b[0] << s[i].b[1] << s[i].b[2];

fout << s[i].b[3] << s[i].b[4] << s[i].b[5];

fout << s[i].b[6] << s[i].b[7] << s[i].b[8] << ',';

//If the board had Horizontal Symetry, generate Symetrical board

if (HorizSym == 1)

{ flipHoriz(i);

fout << s[i].b[0] << s[i].b[1] << s[i].b[2];

fout << s[i].b[3] << s[i].b[4] << s[i].b[5];

fout << s[i].b[6] << s[i].b[7] << s[i].b[8] << ',';

flipHoriz(i); }

//If the board had Vertical Symetry, generate Symetrical board

if (VertSym == 1)

{ flipVert(i);

fout << s[i].b[0] << s[i].b[1] << s[i].b[2];

fout << s[i].b[3] << s[i].b[4] << s[i].b[5];

fout << s[i].b[6] << s[i].b[7] << s[i].b[8] << ',';

flipVert(i); }

if (LLURSym == 1)

{ flipLLUR(i);

fout << s[i].b[0] << s[i].b[1] << s[i].b[2];

fout << s[i].b[3] << s[i].b[4] << s[i].b[5];

fout << s[i].b[6] << s[i].b[7] << s[i].b[8] << ',';

flipLLUR(i); }

if (ULLRSym == 1)

{ flipULLR(i);

fout << s[i].b[0] << s[i].b[1] << s[i].b[2];

fout << s[i].b[3] << s[i].b[4] << s[i].b[5];

fout << s[i].b[6] << s[i].b[7] << s[i].b[8] << ',';

flipULLR(i); }

//Write the terminal symbols

fout << "//" << endl;

//Remove the mark from the board so that future boards may check

//against it for uniqueness

s[i].b[NUMBERPAD[place]] = 0;

} //end of asking for a bunch of boards loop

fout.close(); //close the output file

//Results

cout << "Defined a total of " << totalDefined << " boards ";

cout << "from " << maxNumberBoards << endl;

} //end main()

/**********************************************************************/

//Checks if state w is a terminal board, due to win. 1=done, 0=not-done

int checkdone(int w) {

if (s[w].b[0] != 0 && s[w].b[0] == s[w].b[1] && s[w].b[1] == s[w].b[2])

{return 1;}

if (s[w].b[3] != 0 && s[w].b[3] == s[w].b[4] && s[w].b[4] == s[w].b[5])

{return 1;}

if (s[w].b[6] != 0 && s[w].b[6] == s[w].b[7] && s[w].b[7] == s[w].b[8])

{return 1;}

if (s[w].b[0] != 0 && s[w].b[0] == s[w].b[3] && s[w].b[3] == s[w].b[6])

{return 1;}

if (s[w].b[1] != 0 && s[w].b[1] == s[w].b[4] && s[w].b[4] == s[w].b[7])

{return 1;}

if (s[w].b[2] != 0 && s[w].b[2] == s[w].b[5] && s[w].b[5] == s[w].b[8])

{return 1;}

if (s[w].b[0] != 0 && s[w].b[0] == s[w].b[4] && s[w].b[4] == s[w].b[8])

{return 1;}

if (s[w].b[6] != 0 && s[w].b[6] == s[w].b[4] && s[w].b[4] == s[w].b[2])

{return 1;}

return 0;

}

//Rotate state w by 90 degrees clockwise

void rotate(int w) {

int b0 = s[w].b[0]; int b1 = s[w].b[1]; int b2 = s[w].b[2];

int b3 = s[w].b[3]; int b4 = s[w].b[4]; int b5 = s[w].b[5];

int b6 = s[w].b[6]; int b7 = s[w].b[7]; int b8 = s[w].b[8];

s[w].b[0] = b6; s[w].b[1] = b3; s[w].b[2] = b0;

s[w].b[3] = b7; s[w].b[4] = b4; s[w].b[5] = b1;

s[w].b[6] = b8; s[w].b[7] = b5; s[w].b[8] = b2; }

//Flip state w about the Upper-Left to Lower-Right line

void flipULLR(int w) {

int b0 = s[w].b[0]; int b1 = s[w].b[1]; int b2 = s[w].b[2];

int b3 = s[w].b[3]; int b4 = s[w].b[4]; int b5 = s[w].b[5];

int b6 = s[w].b[6]; int b7 = s[w].b[7]; int b8 = s[w].b[8];

s[w].b[0] = b0; s[w].b[1] = b3; s[w].b[2] = b6;

s[w].b[3] = b1; s[w].b[4] = b4; s[w].b[5] = b7;

s[w].b[6] = b2; s[w].b[7] = b5; s[w].b[8] = b8; }

//Flip state w about the Lower-Left to upper-Right line

void flipLLUR(int w) {

int b0 = s[w].b[0]; int b1 = s[w].b[1]; int b2 = s[w].b[2];

int b3 = s[w].b[3]; int b4 = s[w].b[4]; int b5 = s[w].b[5];

int b6 = s[w].b[6]; int b7 = s[w].b[7]; int b8 = s[w].b[8];

s[w].b[0] = b8; s[w].b[1] = b5; s[w].b[2] = b2;

s[w].b[3] = b7; s[w].b[4] = b4; s[w].b[5] = b1;

s[w].b[6] = b6; s[w].b[7] = b3; s[w].b[8] = b0; }

//Flip state w about the Vertical Line

void flipVert(int w) {

int b0 = s[w].b[0]; int b1 = s[w].b[1]; int b2 = s[w].b[2];

int b3 = s[w].b[3]; int b4 = s[w].b[4]; int b5 = s[w].b[5];

int b6 = s[w].b[6]; int b7 = s[w].b[7]; int b8 = s[w].b[8];

s[w].b[0] = b2; s[w].b[1] = b1; s[w].b[2] = b0;

s[w].b[3] = b5; s[w].b[4] = b4; s[w].b[5] = b3;

s[w].b[6] = b8; s[w].b[7] = b7; s[w].b[8] = b6; }

//Flip state w about the Horizontal

void flipHoriz(int w) {

int b0 = s[w].b[0]; int b1 = s[w].b[1]; int b2 = s[w].b[2];

int b3 = s[w].b[3]; int b4 = s[w].b[4]; int b5 = s[w].b[5];

int b6 = s[w].b[6]; int b7 = s[w].b[7]; int b8 = s[w].b[8];

s[w].b[0] = b6; s[w].b[1] = b7; s[w].b[2] = b8;

s[w].b[3] = b3; s[w].b[4] = b4; s[w].b[5] = b5;

s[w].b[6] = b0; s[w].b[7] = b1; s[w].b[8] = b2; }

//Check if there are any other boards like s1 (w/permutations)

int anyOthers(int s1) {

for(int i = 0; i < s1; i++)

{if (completeEquality(s1,i) == 1)

{return 1;}}

return -1;}

//Check if there are any similar boards to s1, (w/o permutations)

int anySimilar(int s1) {

for(int i = 0; i < s1; i++)

{if (equals(s1,i) == 1)

{return 1;} }

return -1;}

//Checks if board s1 equals board s2 exactly

int equals(int s1, int s2) {

for(int i = 0; i < 9; i++)

{if (s[s1].b[i] != s[s2].b[i])

return -1;}

return 1;}

//Checks if s1 and s2 are equal (with permutations)

int completeEquality(int s1, int s2) {

if (equals(s1,s2) == 1) //First check if they're

return 1; //exactly equal

for(int i = 0; i < 4; i++) //Then rotate the board

{rotate(s1); //and check if the rotations

if (equals(s1,s2) == 1) //are equal to s2

return 1;}

flipHoriz(s1); //Flip it horizontally

if (equals(s1,s2) == 1) //and check to see if it

return 1; //equals s2

flipHoriz(s1);

flipVert(s1);

if (equals(s1,s2) == 1)

return 1;

flipVert(s1);

flipLLUR(s1);

if (equals(s1,s2) == 1)

return 1;

flipLLUR(s1);

flipULLR(s1);

if (equals(s1,s2) == 1)

return 1;

flipULLR(s1);

return -1;}