Connect 4 solver

c4.py

import json

boards = [

	(False, """[
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", "O", "X", "X", "X", "O", "."],
	  [".", "O", "X", "X", "O", "O", "X"],
	  [".", "O", "X", "X", "X", "O", "O"]
	]"""),

	('X', """[
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", "X", ".", ".", ".", ".", "."],
	  [".", "O", "X", "X", "X", "O", "."],
	  [".", "O", "X", "X", "O", "O", "X"],
	  [".", "O", "X", "X", "X", "O", "O"]
	]"""),

	('X', """[
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", "X", ".", ".", ".", "X", "."],
	  [".", "O", "X", "X", "X", "O", "."],
	  [".", "O", "X", "X", "O", "O", "X"],
	  [".", "O", "X", "X", "X", "O", "O"]
	]"""),

	('X', """[
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", "X", ".", ".", ".", ".", "."],
	  [".", "O", "X", "X", "X", "X", "."],
	  [".", "O", "X", "X", "O", "O", "X"],
	  [".", "O", "X", "X", "X", "O", "O"]
	]"""),

	('O', """[
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", ".", ".", ".", ".", ".", "."],
	  [".", "O", ".", ".", ".", ".", "."],
	  [".", "O", "X", "X", "X", "X", "."],
	  [".", "O", "X", "X", "O", "O", "X"],
	  [".", "O", "X", "X", "X", "O", "O"]
	]"""),
]

# for each piece we hit, check diagonally up and to the left, directly up
# diagonally up and to the right and directly right
# as we're iterating left to right from the bottom of the board we do not need
# to check behind or below us, as we would already have seen those cells
directions = [
	(-1, -1),
	(0, -1),
	(1, -1),
	(1, 0)
]

def check_direction(expected_cell, x, y, dir_x, dir_y):
	count = 1 # the cell itself!

	while 1:
		x += dir_x
		y += dir_y
		
		try:
			check_cell = board[y][x]
		except IndexError:
			# end of the board
			break
			
		if check_cell != expected_cell:
			break
		
		count += 1

		if count == 4:
			return True
			
	return False
		

def check_board(board):	
	# run through the board, from the bottom to the top
	# we could flip the board but then all the pieces would fall out
	y = len(board) - 1
	
	while y > 0:
		row = board[y]
		for x, cell in enumerate(row):
			if cell in ['X', 'O']:
				for direction in directions:
					if check_direction(cell, x, y, direction[0], direction[1]):
						return cell
						
		y -= 1 # head up one row
	
	return False

for expected, board in boards:
	board = json.loads(board)
		
	result = check_board(board)

	print result, expected