The straight forward algorithm is going to start from the first row and the first column. the algorithm will start by checking if this square is an X or if it is an O.
assume we are trying to find if X is the winner.
If this square is an X, then we will increment the number of X's found in row 1 and the number of X's found in column 1 and the number of X's found in the 270 degrees diagonal.
Because this first row and first column square is a member of all these three possibilities. in order to support this algorithm then we need a storage that will hold the number of X's found in Row 1, the number of X's found in row 2, the number of X's found in row 3, the number of X's found in column 1. the number of X's found in column 2. the number of X's found in column 3. the number of X's found in the 270 degrees diagonal and finally the number of X's found in 45 degrees diagonal.
We can create a class called Tic Tac Toe as follows.
class TicTacToe
{
private readonly int[] _rows; //array to store the number of X's found in each row
private readonly int[] _cols; //array to store the number of X's found in each column
private int _270Diagonal; //one variable to store the number of X's found in the 270 degrees diagonal
private int _45Diagonal;//one variable to store the number of X's found in the 45 degrees diagonal
private readonly int _boardSize; //Caching the board size
private readonly int _boardSizeMinusOne; //cashing the board size minus one in order to perform the subtraction only once
public TicTacToe(int boardSize) // constructor will set the rows and columns array sizes, cash the board size and calculate the boardsize - 1
{
_rows = new int[boardSize];
_cols = new int[boardSize];
_boardSize = boardSize;
_boardSizeMinusOne = _boardSize - 1;
}
//Function to add a Square taken by player X and return true if X won due to this addition
public bool AddSquare(int row, int col)
{
if (_rows[row] == _boardSizeMinusOne) return true; //Since X exist in this row, check if there were two more (or board -1). if so, adding this X will make X take all the squares in this row and hence win
_rows[row] += 1; //otherwise increase the number of X's in this row
if (_cols[col] == _boardSizeMinusOne) return true;
_cols[col] += 1;
if (row == col) //this is the 270 degrees diagonal
{
if (_270Diagonal == _boardSizeMinusOne) return true;
_270Diagonal += 1;
}
if (((row + col) == _boardSizeMinusOne)) //this is the 45 degrees diagonal
{
if (_45Diagonal == _boardSizeMinusOne) return true;
_45Diagonal += 1;
}
return false; //No winner yet
}
}
This class contains the AddSquare function which will add a square taken by X and will let us know if X has won due to this addition.
This algorithm will visit every single square only in the worst case scenario and at this time the Big O will be n to the power of 2.
in order to test this class we would create a sample board and use the class as follows
static void Main(string[] args)
{
var board = new int[3,3];
board[0, 0] = 0;
board[0, 1] = 0;
board[0, 2] = 1;
board[1, 0] = 0;
board[1, 1] = 0;
board[1, 2] = 1;
board[2, 0] = 1;
board[2, 1] = 0;
board[2, 2] = 1;
var ticTacToe = new TicTacToe(3);
for(var row = 0; row != 3; row++)
{
for (var col = 0; col != 3; col++)
{
if (board[row,col] == 1)
if (ticTacToe.AddSquare(row, col))
{
Console.WriteLine("Player 1 has won the game.");
Console.ReadKey();
return;
}
}
}
Console.WriteLine("No one won");
Console.ReadKey();
}
a better algorithm could select the squares to examine more carefully and improve the worst case scenario. If we look at the board, we find that the middle square is responsible about 4 different possibilities of winning, and if this square does not contain X, then that means 4 different possibilities are eliminated. secondly the corner squares are responsible for 3 different possibilities and if a corner square does not contain X then 3 possibilities are eliminated. so, if we start with the middle square and then the corner squares the worst case scenario will indeed be improved.
Not only that, but if we can store the importance of every square and how many possibilities it is a member of, then during the examination of the board we will find that some squares will not affect the board and hence we should not check it. here is an illustration.
| 3 | 2 | 3 |
| 2 | 4 | 2 |
| 3 | 2 | 3 |
| 2 | 1 | 2 |
| 1 | - | 1 |
| 2 | 1 | 2 |
| 2 | 1 | 2 |
| 1 | - | 1 |
| 2 | 1 | 2 |
| - | 0 | 1 |
| 0 | - | 1 |
| 1 | 1 | 1 |
if the top left corner is not an X, then we can go ahead and reduce the weights of all the squares that can make a winning situation jointly with the top left square. in this case we will decrease 1 from the weights of all the squares in row 1, all the squares in column 1 and the 270 degrees diagonal. in this case we will notice that row 1 column 1 now has a weight of zero. and that means the value of this square does not matter, whether it is an X or an O it does not matter, because row 1 can never be a row fully occupied by X, and column 2 can never be fully occupied by X. It does not matter what the value of this square is (row 1, column 2). using this technique we will be able to prune the board and eliminate a number of squares that we do not need to check.
This will affect the Big O calculated for this board since it will not be n square. I still need to calculate how exactly it will be and I should expect to see some log n in the calculation.
I will post the C# program here soon.
