Is it possible to check for the winning condition of a game of TicTacToe using jGraphT?

Question

I found this working solution:

private int[] winningPatterns = { 0b111000000, 0b000111000, 0b000000111, // rows
        0b100100100, 0b010010010, 0b001001001, // cols
        0b100010001, 0b001010100 // diagonals
};

/** Returns true if thePlayer wins */
private boolean hasWon(int thePlayer) {
    int pattern = 0b000000000; // 9-bit pattern for the 9 cells
    for (int row = 0; row < 3; ++row) {
        for (int col = 0; col < 3; ++col) {
            if (cells[row][col].content == thePlayer) {
                pattern |= (1 << (row * 3 + col));
            }
        }
    }
    for (int winningPattern : winningPatterns) {
        if ((pattern & winningPattern) == winningPattern)
            return true;
    }
    return false;
}

but I would like to know if there is a more elegant solution using graph logic.

Update: I am also looking into using my knowledge at different and bigger variants of the 3x3 board and I believe this approach does not scale well aesthetically.

For example: https://en.wikipedia.org/wiki/Teeko

Homeopathy

That seems plenty elegant -- what more are you looking for? – Lavabo

I would like to invest more in the setup of the graph and then be able to simply call myGraph.isItWon() – Homeopathy

this approach is nice and scales up-to 64 cells (ie 8x8) boards easily – Retrench

It looks great to be honest. Id say work with that. – Phthisis

Answer 1

for a 25 by 25 board I think the method that you have is viable but some ways to improve it are as follows.

1. Create the pattern while the user is adding the pieces, because then it will only take the time it takes to go through the winningPatterns array.

2. To improve the second part you could try to store it more effectively. Store the winningPatterns in a way where You could check multiple of them at the same time. For example if the first position is 0, then it can remove 3 possibilities from the winningPatterns instead of just one (111 000 000 , 100 100 100, 100 010 001).

3. You could improve the average case by checking the position that has the highest probability for it to be right. For example there are 4 ways the player could have won from placing the piece at the middle, So check in that order.

4. If you store the player positions in a seperate array, where p1Tiles, and p2Tiles. Then that could greatly increase the average case because most of them time the board will be fairly empty. It will only be full for 1 instance of this game before the board gets reset.

5. You dont actually need to check all the pieces of the player has won you just need to check if the piece that the current user places makes a win. So with this method you would only need to check worst case 12 other spots , even if the board has a size of 99..999 by 99..999. (12 because of all the slots around the current slot PLUS if there are two of the same color beside each other so you would have to look at the following slot )

Spray