# Tic Tac Toe - Verifying a player won

I saw this problem on a mock interview I spectated online, and decided to take a stab at it. The problem as stated originally asked to find if a given player had won a standard game of tic-tac-toe. However, the code below goes for a more general case where: the matrix size is variable, and the number of markers in a row to win is also variable.

If $n$ = height of the board, the solution below is $O(k * N^2)$, where $k$ is the number of markers needed in a row to win. The gist of the approach is to loop through every position and check downward or forward if it is the starting point of a solution.

One clear issue here is that the information gained from a failed traversal isn't stored. For example, if on the first row we have xxo, breaking the traversal on the 'o' doesn't prevent us from calling "test_forward" even though it will clearly fail on the next index.

What are potential improvements that could be implemented made here?

tests = {'a': [['x','x','o'],
['-','o','x'],
['-','-','x']]}

def test_forward(board, i, j, player, num_needed):
# Check for 3 in a row horizontally (forward)
for k in range(1, num_needed):
if board[i][j+k] != player:
return False

return True

def test_down(board, i, j, player, num_needed):
# Check for 3 in a row vertically (downward)
for k in range(1, num_needed):
if board[i+k][j] != player:
return False

return True

def test_diag_forward(board, i, j, player, num_needed):
# Check for 3 in a row diagonally down and right
for k in range(1, num_needed):
if board[i+k][j+k] != player:
return False

return True

def test_diag_backward(board, i, j, player, num_needed):
# Check for 3 in a row diagonally down and left
for k in range(1, num_needed):
if board[i+k][j-k] != player:
return False

return True

def check_neighbors(board, dimension, i, j, player, num_needed):
if board[i][j] != player:
return False

# Avoid array out of bounds
searchable_space = dimension - num_needed

if j <= searchable_space:
won_forward = test_forward(board, i, j, player, num_needed)
if won_forward:
return True

if i <= searchable_space:
won_down = test_down(board, i, j, player, num_needed)
if won_down:
return True

if j <= searchable_space and i <= searchable_space:
won_diag_forward = test_diag_forward(board, i, j, player, num_needed)
if won_diag_forward:
return True

if j >= num_needed - 1 and i <= searchable_space:
won_diag_backward = test_diag_backward(board, i, j, player, num_needed)
if won_diag_backward:
return True

return False

# Loop through every square and check if it is the starting point of a solution
def has_winner(board, player, num_needed):
dimension = len(board[0])
for i in range(dimension):
for j in range(dimension):

result = check_neighbors(board, dimension, i, j, player, num_needed)

if result == True:
return result
else:
continue

return result

print has_winner(tests['a'], 'x', 3)