# 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)


## 1 Answer

One thing that comes to mind is probability.

In all winning cases of tic-tac-toe, the middle spot of the involved row/column/diagonal is always occupied. Therefore, I would look to spread my chances and test from the most frequently occupied space(s) in the middle and keep trying to test one adjacent space outward at a time in an evenly spread fashion.

The benefit of this really comes into focus when you think about the fact that the whole check is really done in one pass in a spiral kind of manner. Having the check in one pass means that as soon as you run into a space that eliminates the possibility of a win being present, you stop checking it. Therefore, the spiral will go faster and faster until a win is found or until the whole check is completed. Pretty cool to think about.

I may code this...but for now that's just an idea of one interesting approach you can take :)