Now that we've got some interaction in the game with our GridCellMouseListener, let's finish it up by figuring out who is the winner.
There are a couple of ways to solve Tic Tac Toe from a programmatical standpoint. For instance, you could use the brute force method of checking each possible scenario. IE, loop through each row first check for a winner, then loop through each column and check for a winner and finally if no winning rows or columns have been found check the two diagonals.
This doesn't sound so bad, but it's definitely not the optimal way of doing this.
It would be much better to actually do the solving whenever someone actually makes a move, and only solve for that row, column, or diagonal.
Let's take a look at one possible solution for solving a Tic Tac Toe game.
When to Solve
First off, you can't technically have a winner until at least 5 turns have passed - after 5 turns the first player has 3 marks on the board, at 4 turns both players only have 2 marks on the board. So let's not worry about even solving until at least 5 turns have passed.
public class GridCellMouseListener extends SGMouseAdapter { // Keep track of number of turns. private int turns; // ... more instance variables and constructor ... // @Override public synchronized void mouseClicked(MouseEvent event, SGNode node) { // ... get the grid cell ... // if (gridCell.getValue() == null) { // ... update the value if need be ... // // change turns. turn = !turn; // increment turns. turns++; if (turns >= 5) { // if at least 5 turns have passed, we can start seeing if someone's one. } } } }
Now that we know a winner is even possible, let's tackle actually solving the playing board.
How to Solve
As I mentioned previously, I want to solve the game board when a user actually makes a move. This means updating the GridCellMouseListener to handle the solving logic.
First we need an easy way to determine if a row/column/diagonal is ready to be solved and whether or not there's a winner there. If we keep a count for the number of moves made on each, we can easily tell if a row, column or diagonal has enough moves on it to contain a winner.
public class GridCellMouseListener extends SGMouseAdapter { // arrays containing row, column and diagonal counts. private int[] columnCounts = new int[3]; private int[] diagonalCounts = new int[2]; private int[] rowCounts = new int[3]; // ... instance variables and constructor ... // @Override public synchronized void mouseClicked(MouseEvent event, SGNode node) { GridCell gridCell = (GridCell) node; // get the row and column of this grid cell because we're going to need it int row = gridCell.getRow(); int column = gridCell.getColumn(); if (gridCell.getValue() == null) { // ... update the grid cells value, and turn ... // updateRowAndColumn(row, column); updateDiagonals(row, column); // ... Check if solution is available yet ... // } } private void updateDiagonals(int row, int column) { if (row == column) { // handle first diagonal. // X| | // |X| // | |X diagonalCounts[0]++; } if (((row == 0) && (column == 2)) || ((row == 1) && (column == 1)) || ((row == 2) && (column == 0))) { // handle other diagonal. // | |X // |X| // X| | diagonalCounts[1]++; } } private void updateRowAndColumn(int row, int column) { // update the row counts for this row. rowCounts[row]++; // update the column counts for this column. columnCounts[column]++; } }
If a row, column or diagonal has 3 moves made on it then there's a possibility it contains a winner.
Now we need an easy way to check if the ready row, column or diagonal has a winner. If we keep a second set of counts for each row, column, and diagonal, and we give positive and negative values to each X move and O move (respectively), then we can tell very quickly if a row, column, or diagonal has a winner. A winning count will equal 3 or -3. Eg. if row 1 contains 3 X's, then the row value will equal 3 and we have a winner. If row 1 contains 2 X's and 1 O, the row value will equal 2 - no winner, etc...
public class GridCellMouseListener extends SGMouseAdapter { // arrays containing row, column and diagonal values. private int[] columnValues = new int[3]; private int[] diagonalValues = new int[2]; private int[] rowValues = new int[3]; // ... more instance variables and constructor ... // @Override public synchronized void mouseClicked(MouseEvent event, SGNode node) { // turn value, 1 = X, -1 = O. int value = 0; if (gridCell.getValue() == null) { // if the value isn't null, then the value is already set, ignore click. if (turn) { // it's X's turn. // ... // value = 1; } else { // it's O's turn. // ... // value = -1; } // ... change and update turns ... // updateRowAndColumn(row, column, value); updateDiagonals(row, column, value); // ... Check if solution is available yet ... // } } private void updateDiagonals(int row, int column, int value) { if (row == column) { // handle first diagonal. // X| | // |X| // | |X diagonalCounts[0]++; // add value to diagonal values. diagonalValues[0] += value; } if (((row == 0) && (column == 2)) || ((row == 1) && (column == 1)) || ((row == 2) && (column == 0))) { // handle other diagonal. // | |X // |X| // X| | diagonalCounts[1]++; // add value to diagonal values. diagonalValues[1] += value; } } private void updateRowAndColumn(int row, int column, int value) { // update the row/column values. Every X is equal to 1, and O is equal to -1. rowValues[row] += value; columnValues[column] += value; // ... update row and column counts ... // } }
Now we know when a row, column, or diagonal is ready to be checked - it's count will equal 3, and we know if there is a winner there because it's value will be 3 or -3. Let's put it together and print out when we have a winner. I'll also add a check to see if a winner has already been found. If a winner has been found, the board will essentially stop taking input.
public class GridCellMouseListener extends SGMouseAdapter { // ... count and value arrays, turns instance variables ... // private boolean winnerFound; // ... constructor ... // @Override public synchronized void mouseClicked(MouseEvent event, SGNode node) { // ... get GridCell, row, and column. Initialize value ... // if ((gridCell.getValue() == null) && !winnerFound) { // ... update turns, row and column counts/values, and diagonal counts and values ... // if (turns >= 5) { // if at least 5 turns have passed, we can start seeing if someone's one. solve(gridCell); } } } private void solve(GridCell gridCell) { int row = gridCell.getRow(); int column = gridCell.getColumn(); if ((rowCounts[row] == 3) && (Math.abs(rowValues[row]) == 3)) { // there's 3 values at this row and the value is either 3 or -3 // we have a winnerFound. winnerFound = true; System.out.println("Winner " + gridCell.getValue() + " at row[" + (row + 1) + "]"); } else if ((columnCounts[column] == 3) && (Math.abs(columnValues[column]) == 3)) { // there's 3 values at this column and the value is either 3 or -3 // we have a winnerFound. winnerFound = true; System.out.println("Winner " + gridCell.getValue() + " at column[" + (column + 1) + "]"); } else if ((diagonalCounts[0] == 3) && (Math.abs(diagonalValues[0]) == 3)) { // there's 3 values at this diagonal and the value is either 3 or -3 // we have a winnerFound winnerFound = true; System.out.println("Winner " + gridCell.getValue() + " at diagonal[1]"); } else if ((diagonalCounts[1] == 3) && (Math.abs(diagonalValues[1]) == 3)) { // there's 3 values at this diagonal and the value is either 3 or -3 // we have a winnerFound winnerFound = true; System.out.println("Winner " + gridCell.getValue() + " at diagonal[2]"); } } // ... updateDiagonals, updateRowAndColumn methods ... // }
That's pretty much all there is to it. Next time I'll clean up the code some. There's really no need for a solve method if the update methods can check for a solution at the same time. Also the text X and O's are ugly, let's create some images and use them instead.
Here's the code for this one.
Cheers!
