Determining three in a row in Python 2d array

Question

I'm working on a tic-tac-toe game with a M x N board in Python. I'm trying to find an efficient way to determine if a player has won (3 in a row either vertical, horizontal, or diagonal direction.) Most 3x3 implementations of the game just check for all possible winning combinations after each turn. This seems a little extreme with a massive board.

4x4 example: (using 1s and 2s instead of Xs and Os)

board = ([1,0,2,1], [0,0,0,1], [2,2,0,0], [1,0,0,1])
for row in board:
    print row

Thanks- Jonathan

Answer 1

Although this approach has a certain appeal, it's probably not especially fast.

# A bogus game with wins in several directions.
board = (
    [1,1,2,1],
    [0,2,1,1],
    [2,2,2,1],
    [1,0,0,1],
)

# A few convenience variables.    
n_rows = len(board)    
lft = [ [0] * i for i in range(n_rows) ]  # [[], [0], [0, 0], [0, 0, 0]]
rgt = list(reversed(lft))

# Create transpositions of the board to check for wins in various directions.
transpositions = {
    'horizontal' : board,
    'vertical'   : zip(*board),
    'diag_forw'  : zip(* [lft[i] + board[i] + rgt[i] for i in range(n_rows)] ),
    'diag_back'  : zip(* [rgt[i] + board[i] + lft[i] for i in range(n_rows)] ),
}

# Apply Jonathan's horizontal-win check to all of the transpositions.
for direction, transp in transpositions.iteritems():
    for row in transp:
        s = ''.join( map(str, row) )
        for player in range(1,3):
            if s.find(str(player) * 3) >= 0:
                print 'player={0} direction={1}'.format(player, direction)

Output:

player=1 direction=diag_back
player=2 direction=diag_forw
player=2 direction=horizontal
player=1 direction=vertical

The idea behind the diagonal transpositions is to shift the rows, using lft and rgt for left and right padding. For example, the diag_forw list looks like this after the padding is added (pad characters are shown as periods, even though zeroes are used in the actual code).

1 1 2 1 . . .
. 0 2 1 1 . .
. . 2 2 2 1 .
. . . 1 0 0 1 

Then we simply transpose that array, using zip(*foo), which allows us to use Jonathan's good idea for finding horizontal wins.

Answer 2

You can look if the player's move closed the game (looking on that row, that column and the 2 diagonals if they ar x checks consecutively), it's o(x) complexity. Let's say you're looking o that row to see if he won. Look to the left how many consecutively checks are and to the right. If the sum of them excedes x he won. You'll do the same on the columns and on the diagonals.