Category: Computer Science

/*
 *  Board.h
 *  Permutation
 *
 *  Created by James Pate Williams, Jr. on 7/21/08.
 *	Modified on Monday 11/24/2025 
 *  Copyright 2008 James Pate Williams, Jr. All rights reserved.
 *
 */

#ifndef _Board_
#define _Board_

#include <fstream>
#include <vector>

class Board {
	private:
		
		char state[9];
		std::vector<std::vector<char>> board;

	public:
		
		Board(void);
		Board(const Board &board);
		Board(const char b[3][3]);
		Board(const std::vector<char> &v);
		
		char GetState(int n) const;
		void PrintBoard(int n) const;
		void WriteBoard(std::ofstream &out) const;
		
		friend bool operator == (const Board &b1, const Board &b2);
		friend bool operator != (const Board &b1, const Board &b2);
		friend bool Found(const Board &initial, const Board &board);
		friend bool Win(const Board b, char winner[8]);
		friend bool LegalBoard(
			bool& legal, bool& won, char& whoWon, const Board b);
		friend void PrintBoard(char board[3][3], int number);
		
		static const char CharX, CharO, CharS;
};

#endif

/*
 *  Board.cpp
 *  Permutation
 *
 *  Created by James Pate Williams, Jr. on 7/21/08.
 *  Copyright 2008 James Pate Williams, Jr. All rights reserved.
 *
 */

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <vector>
#include "Board.h"

const char Board::CharO = 'o';
const char Board::CharX = 'x';
const char Board::CharS = '_';

Board::Board(void) {
	board.resize(3, std::vector<char>(3));
	for (int i = 0; i < 9; i++)
		state[i] = '\0';
}

Board::Board(const Board &b) {
	board.resize(3, std::vector<char>(3));
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			state[3 * i + j] = board[i][j] = b.state[3 * i + j];
}

Board::Board(const char b[3][3]) {
	board.resize(3, std::vector<char>(3));
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			state[3 * i + j] = board[i][j] = b[i][j];
}

Board::Board(const std::vector<char> &v) {
	board.resize(3, std::vector<char>(3));
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			state[3 * i + j] = board[i][j] = v[3LL * i + j];
}

char Board::GetState(int n) const {
	return state[n];
}

void Board::PrintBoard(int n) const  {
	std::cout << n << std::endl;
	
	for (int i = 0; i < 3; i++) {
	
		for (int j = 0; j < 3; j++)
			std::cout << state[3 * i + j];
				
		std::cout << std::endl;
	}
	
	std::cout << std::endl;
	std::cout << std::endl;
}

void Board::WriteBoard(std::ofstream &out) const {
	for (int i = 0; i < 9; i++) 
		out << state[i];
				
	out << std::endl;
}

bool operator == (const Board &b1, const Board &b2) {
	int i, equal = 0;
	
	for (i = 0; i < 9; i++)
		if (b1.state[i] == b2.state[i])
			equal++;

	return equal == 9;
}

bool operator != (const Board &b1, const Board &b2) {
	for (int i = 0; i < 9; i++)
		if (b1.state[i] == b2.state[i])
			return false;
	
	return true;
}

bool Found(const Board &initial, const Board &board) {

	// reflections
	
	if (initial.state[0] == board.state[6] && initial.state[1] == board.state[7] &&
		initial.state[2] == board.state[8] && initial.state[3] == board.state[3] &&
		initial.state[4] == board.state[4] && initial.state[5] == board.state[5] &&
		initial.state[6] == board.state[0] && initial.state[7] == board.state[1] &&
		initial.state[8] == board.state[2])
		return true;
		
	if (initial.state[0] == board.state[2] && initial.state[1] == board.state[1] &&
		initial.state[2] == board.state[0] && initial.state[3] == board.state[5] &&
		initial.state[4] == board.state[4] && initial.state[5] == board.state[3] &&
		initial.state[6] == board.state[8] && initial.state[7] == board.state[7] &&
		initial.state[8] == board.state[6])
		return true;
	
	if (initial.state[0] == board.state[0] && initial.state[1] == board.state[3] &&
		initial.state[2] == board.state[6] && initial.state[3] == board.state[1] &&
		initial.state[4] == board.state[4] && initial.state[5] == board.state[7] &&
		initial.state[6] == board.state[2] && initial.state[7] == board.state[5] &&
		initial.state[8] == board.state[8])
		return true;

	if (initial.state[0] == board.state[8] && initial.state[1] == board.state[5] &&
		initial.state[2] == board.state[2] && initial.state[3] == board.state[7] &&
		initial.state[4] == board.state[4] && initial.state[5] == board.state[1] &&
		initial.state[6] == board.state[6] && initial.state[7] == board.state[3] &&
		initial.state[8] == board.state[0])
		return true;

	// rotations
	
	if (initial.state[0] == board.state[6] && initial.state[1] == board.state[3] &&
		initial.state[2] == board.state[0] && initial.state[3] == board.state[7] &&
		initial.state[4] == board.state[4] && initial.state[5] == board.state[1] &&
		initial.state[6] == board.state[8] && initial.state[7] == board.state[5] &&
		initial.state[8] == board.state[2])
		return true;
			
	if (initial.state[0] == board.state[8] && initial.state[1] == board.state[7] &&
		initial.state[2] == board.state[6] && initial.state[3] == board.state[5] &&
		initial.state[4] == board.state[4] && initial.state[5] == board.state[3] &&
		initial.state[6] == board.state[2] && initial.state[7] == board.state[1] &&
		initial.state[8] == board.state[0])
		return true;
	
	if (initial.state[0] == board.state[2] && initial.state[1] == board.state[5] &&
		initial.state[2] == board.state[8] && initial.state[3] == board.state[1] &&
		initial.state[4] == board.state[4] && initial.state[5] == board.state[7] &&
		initial.state[6] == board.state[0] && initial.state[7] == board.state[3] &&
		initial.state[8] == board.state[6])
		return true;
			
	// equal

	return initial == board;
}

bool Win(const Board b, char winner[8]) {
	bool win = false;
	
	for (int i = 0; i < 8; i++)
		winner[i] = Board::CharS;

	if (b.board[0][0] == b.board[0][1] && b.board[0][0] == 
		b.board[0][2] && b.board[0][0] != Board::CharS) {
		winner[0] = b.board[0][0];
		win = true;
	}
	
	if (b.board[1][0] == b.board[1][1] && b.board[1][0] ==
		b.board[1][2] && b.board[1][0] != Board::CharS)  {
		winner[1] = b.board[1][0];
		win = true;
	}
	
	if (b.board[2][0] == b.board[2][1] && b.board[2][0] == 
		b.board[2][2] && b.board[2][0] != Board::CharS)  {
		winner[2] = b.board[2][0];
		win = true;
	}
	
	if (b.board[0][0] == b.board[1][0] && b.board[0][0] == 
		b.board[2][0] && b.board[0][0] != Board::CharS)  {
		winner[3] = b.board[0][0];
		win = true;
	}
	
	if (b.board[0][1] == b.board[1][1] && b.board[0][1] == 
		b.board[2][1] && b.board[0][1] != Board::CharS)  {
		winner[4] = b.board[0][1];
		win = true;
	}
	
	if (b.board[0][2] == b.board[1][2] && b.board[0][2] == 
		b.board[2][2] && b.board[0][2] != Board::CharS)  {
		winner[5] = b.board[0][2];
		win = true;
	}
	
	if (b.board[0][0] == b.board[1][1] && b.board[0][0] == 
		b.board[2][2] && b.board[0][0] != Board::CharS)  {
		winner[6] = b.board[0][0];
		win = true;
	}                
	
	if (b.board[0][2] == b.board[1][1] && b.board[0][2] == 
		b.board[2][0] && b.board[0][2] != Board::CharS)  {
		winner[7] = b.board[0][2];
		win = true;
	}

	return win;
}
	
void PrintBoard(char board[3][3], int number) {
	
	std::cout << "number = " << number << std::endl;
	std::cout << std::endl;

	for (int i = 0; i < 3; i++) {
	
		for (int j = 0; j < 3; j++)
			std::cout << board[i][j];
		
		std:: cout << std::endl;
	}

	std::cout << std::endl;
}

bool LegalBoard(
	bool &legal, bool &won, char &whoWon, const Board b) {
	bool winO, winX;
	char winner[8];
	int countO = 0, countS = 0, countX = 0;
	int i, j, oWins = 0, xWins = 0;
	
	legal = won = false;
	
	for (i = 0; i < 3; i++) {
	
		for (j = 0; j < 3; j++) {
			if (b.board[i][j] == Board::CharO)
				countO++;
			else if (b.board[i][j] == Board::CharX)
				countX++;
			else if (b.board[i][j] == Board::CharS)
				countS++;
		}
	}

	if ((countX >= 3 || countO >= 3) && Win(b, winner)) {
	
		for (i = 0; i < 8; i++) {
			if (winner[i] == Board::CharX)
				xWins++;
			else if (winner[i] == Board::CharO)
				oWins++;
		}
		
		winX = (xWins  >= 1 && oWins == 0) && 
			   (countX <= 5 && countO <= 4 && countX == countO + 1);
		
		winO = (xWins  == 0 && oWins >= 1) &&
			   (countO <= 5 && countX <= 4 && countO == countX + 1);
		
		legal = won = winX || winO;

		if (won && winX)
			whoWon = Board::CharX;
		else if (won && winO)
			whoWon = Board::CharO;
	}
	else
		legal = (countX <= 5 && countO <= 4 && countX == countO + 1) ||
			    (countO <= 5 && countX <= 4 && countO == countX + 1);
			  
	return legal;
}

#define _WriteBV_
#include <algorithm>

#ifdef _WriteBV_
#include <fstream>
#endif

#include <iomanip>
#include <iostream>
#include <vector>
#include "Board.h"

static int Compare(const void *vPtr1, const void *vPtr2) {
	char *cPtr1 = (char *) vPtr1;
	char *cPtr2 = (char *) vPtr2;

	return strcmp(cPtr1, cPtr2);
}

static void EnumerateTicTacToe(void) {
	bool legal, won;
	char b[3][3], whoWon;
	char tree[3][3][3][3][3][3][3][3][3];
	int i0, i1, i2, i3, i4, i5, i6, i7, i8;
	int legals = 0, number = 0, wCount = 0;
	int xCount = 0, oCount = 0;
	int bvSize, i, j;

	std::vector<Board> boardVector;
	
	for (i0 = 0; i0 < 3; i0++) {
	for (i1 = 0; i1 < 3; i1++) {
	for (i2 = 0; i2 < 3; i2++) {
	for (i3 = 0; i3 < 3; i3++) {
	for (i4 = 0; i4 < 3; i4++) {
	for (i5 = 0; i5 < 3; i5++) {
	for (i6 = 0; i6 < 3; i6++) {
	for (i7 = 0; i7 < 3; i7++) {
	for (i8 = 0; i8 < 3; i8++) {
		if (i0 == 0)
			b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
		else if (i0 == 1)
			b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
		else if (i0 == 2)
			b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
				
		if (i1 == 0)
			b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
		else if (i1 == 1)
			b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
		else if (i1 == 2)
			b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;

		if (i2 == 0)
			b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
		else if (i2 == 1)
			b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
		else if (i2 == 2)
			b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;

		if (i3 == 0)
			b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
		else if (i3 == 1)
			b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
		else if (i3 == 2)
			b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;

		if (i4 == 0)
			b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
		else if (i4 == 1)
			b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
		else if (i4 == 2)
			b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
			
		if (i5 == 0)
			b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
		else if (i5 == 1)
			b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
		else if (i5 == 2)
			b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
			
		if (i6 == 0)
			b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
		else if (i6 == 1)
			b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
		else if (i6 == 2)
			b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
			
		if (i7 == 0)
			b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
		else if (i7 == 1)
			b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
		else if (i7 == 2)
			b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
			
		if (i8 == 0)
			b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
		else if (i8 == 1)
			b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
		else if (i8 == 2)
			b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
		
		Board bb(b);

		if (LegalBoard(legal, won, whoWon, bb)) {
			Board board(b);

			legals++;
		
			if (won) {
				wCount++;
				
				if (whoWon == Board::CharX)
					xCount++;
				else if (whoWon == Board::CharO)
					oCount++;
			}
			
			boardVector.push_back(board);
		}
		
		number++;

	}}}}}}}}}

	for (i = 0; i < boardVector.size() - 1; i++)
		for (j = i; j < boardVector.size(); j++)
			if (Found(boardVector[i], boardVector[j]))
				boardVector.erase(boardVector.begin() + j);

	bvSize = (int)boardVector.size();
	std::cout << std::setw(4) << "legal total = " << legals << std::endl;
	std::cout << std::setw(4) << "xWins total = " << xCount << std::endl;
	std::cout << std::setw(4) << "oWins total = " << xCount << std::endl;
	std::cout << std::setw(4) << "oxWin total = " << xCount + oCount << std::endl;
	std::cout << std::setw(4) << "unique size = " << boardVector.size();
	std::cout << std::endl;
	
#ifdef _WriteBV_
 
	std::cout << std::endl;
	std::ofstream outFile("Tic TacToe Game Tree Enumeration.txt");
	std::cout << std::endl;
	
	for (i = 0; i < bvSize; i++) {
		boardVector[i].PrintBoard(i + 1);
		boardVector[i].WriteBoard(outFile);
	}

#endif
}

int main (int argc, char * const argv[]) {
	EnumerateTicTacToe();
    return 0;
}