How can you check for multiple situations without a bunch of if statments?

Question

Say you want to check if someone won a game of tic tac toe. How would you do that, without just using an if statement to repeatedly check each column, row and diagonal for 3 in a row?

I'm sure there must be a way, some algorithm or technique that doesn't look anywhere near as ugly as 20 lines of ifs(or switches) to check an array of 9 for a winnar.

There are only 3^9 = 19683 Tic-Tac-Toe positions, so if you really wanted to go for speed you could make a look-up table. — Kerrek SB, Feb 05 '12 at 22:32
You only need 9 bits per player to represent the board, and there's only 8 winning combinations. Set the bits, use bitwise operations in a loop to check for a win. Of course, you *still* have to define all that, which makes the 8 `if` statements just as easy. — Brian Roach, Feb 05 '12 at 22:38
possible duplicate of [Algorithm for Determining Tic Tac Toe Game Over (Java)](http://stackoverflow.com/questions/1056316/algorithm-for-determining-tic-tac-toe-game-over-java) — Saeed Amiri, Feb 05 '12 at 22:41

score 3 · Accepted Answer · answered Feb 05 '12 at 22:37

3

I'd probably go for a 9 bit int for each player representing their turns. You can easily apply bit operations to check for an entire column, row or diagonal directly.

answered Feb 05 '12 at 22:37

stryba

1,979
13
19

I was *just* posting this as a comment when you answered. :) – Brian Roach Feb 05 '12 at 22:38

score 2 · Answer 2 · answered Feb 05 '12 at 22:44

There are only eight winning positions possible. Convert to nine bit array and AND to test for win I.e.

Possible win patterns:

111000000 000111000 000000111 100100100 010010010 001001001 100010001 001010100

board:

OXO . X . XO

Testing X results in:

010010010

which ANDed with row 5 ==true

score 1 · Answer 3 · answered Feb 05 '12 at 22:45

You are right, there is such technique.

Each winning pattern starts at the upper edge or at the left edge, and continues for three steps. In each of these steps, one of the following happens:

Row number gets incremented, and column stays the same
Column number gets incremented, and row stays the same
Both row and column number gets incremented (first diagonal)
Row number gets incremented, and column number gets decremented (the other diagonal)

So now you can write a function like this:

bool CheckWin(char[3][3] board, char playerCh, int r, int c, int dr, int dc) {
    for (int i = 0 ; i != 3 ; i++) {
        if (board[r+i*dr][c+i*dc] != playerCh) {
            return false;
        }
    }
    return true;
}

Using this function, you can check if a player has three in a row starting at (r,c), with the step dr rows and dc columns:

bool won = false;
for (int i = 0 ; !won && i != 3 ; i++) {
    won |= CheckWin(board, 'X', i, 0, 0, 1)
        || CheckWin(board, 'X', 0, i, 1, 0);
}
won |= CheckWin(board, 'X', 0, 0, 1, 1);
won |= CheckWin(board, 'X', 2, 0, -1, 1);

How can you check for multiple situations without a bunch of if statments?

3 Answers3