Tic-Tac-Toe solver

Question

As a programming exercise, I've attempted a Tic-Tac-Toe solver which takes a finished board and determines a winner.

On top of checks for malformed input/ambiguous games (e.g. both players with winning positions), what else can I do to improve this? In particular, is the coding style acceptable and are there better ways to check for win conditions?

def tictac(b):
    """ 
    Parses a tic-tac-toe board and returns a winner.
    Input: a list of lists containing values 0 or 1.
    0 corresponds to 'noughts' and 1 to 'crosses'
    e.g.

    >>> gameboard = [[0,0,1],[0,1,0],[1,1,0]]
    >>> tictac(gameboard)
    X wins

    """

    # If the sum of a column/row/diagonal is 0, O wins.
    # If the sum is number of rows/columns, X wins.

    winner = ""
    board_range = range(len(b))

    # Check rows and columns.
    for i in board_range:
        row_sum = sum(b[i])
        col_sum = sum([x[i] for x in b]) 

        if row_sum == 0 or col_sum == 0:
            winner =  "O wins"
        elif row_sum == len(b) or col_sum == len(b):
            winner =  "X wins"

    # Check the diagonals.
    fwd_diag_sum = sum([b[i][i] for i in board_range])
    bck_diag_sum = sum([b[i][len(b)-i-1] for i in board_range])

    if fwd_diag_sum == 0 or bck_diag_sum == 0:
                winner =  "O wins"

    if fwd_diag_sum == len(b) or bck_diag_sum == len(b):
                winner =  "X wins"

    if winner:
        print winner
    else:
        print "Game is a tie!"

For convenience, here's a little test function too:

def test_tic_tac():

    def pretty_print(b):
            for row in b:
                print row

    gameboard = [[0,0,1],[0,1,0],[1,1,0]]
    pretty_print(gameboard)
    tictac(gameboard)

    gameboard = [[0,1,1],[0,0,0],[1,1,0]]
    pretty_print(gameboard)
    tictac(gameboard)

    gameboard = [[1,0,1],[0,0,1],[0,1,0]]
    pretty_print(gameboard)
    tictac(gameboard)

    gameboard = [[0,0,1,0],[1,1,0,1],[0,1,1,1],[0,1,0,1]]
    pretty_print(gameboard)
    tictac(gameboard)

Answer 1

Missing handling for incomplete boards of finished games

The program works only with complete boards. It won't work with this finished game with incomplete board, which is kind of a big drawback for a game evaluator:

    o
x o o
o x x

Return result instead of printing

It would be better to not have the board evaluation logic and printing in the same method. You should split these steps into separate functions.

This will make some optimizations easier (see my next point).

It will also help improving your testing technique. Testing by reading output is not convenient. It's best when tests either pass or fail, so that you can verify if the program behaves correctly just by checking that everything passes. One way to achieve this is using assertions, for example:

assert "X wins" == evaluate_board([[0, 0, 1], [0, 1, 0], [1, 1, 0]])

A better way is using the unittest package of Python, and splitting your test method to distinct test cases for different kinds of winning positions, such as win by row sum, col sum, diagonal.

Wasted operations

In the loop that checks the row and column sums, once you found a winner, the loop happily continues, and after the loop you check the diagonals, when in fact you could return the winner as soon as you see it:

if row_sum == 0 or col_sum == 0:
    return "O wins"

By returning sooner, the final if winner statements could be replaced with a simple return "Game is a tie!"

Duplicated string literals

The "O wins", "X wins" string literals appear multiple times. It would be better to avoid such code duplication, as it's prone to errors if you ever change the message format, you have to remember to make the same change everywhere.

Coding style

You should follow PEP8.

Answer 2

I hope it's appropriate to follow up with my revised code in an answer to avoid clutter in my original question. As suggested, I've changed the implementation to accommodate 'empty' values as None. I've also done away with print statements in favour of return.

def tictac(b):
    """ 
    Parses a tic-tac-toe board and returns a winner.
    Input: a list of lists containing 0's (representing O),
           1's (representing X), or None (missing values)
    Output: A string describing outcome of the game or False if the input is                      
            not well-formed. 
    e.g.

    >>> gameboard = [[0,0,1],[0,1,0],[1,1,0]]
    >>> tictac(gameboard)
    X wins

    """

    # Validate the input

    # Ensure input is not empty
    if not b:
        return False

    # Ensure len(rows) all equal and equal to row count.
    equal_lengths = [(len(x) == len(b)) for x in b]
    if not all(equal_lengths):
        return False

    # Ensure we only have two different types of input (excl. None)
    flat_board = [el for el in x for x in b]
    input_cardinality = set(flat_board)
    if not len(input_cardinality) == 2:
        return False

    # Check diagonals, rows and columns.
    # If all elements in diagonal/row/column are the same and
    # equal to 0, O wins.
    # If all the same and equal to 1, X wins.

    o_wins = "O wins"
    x_wins = "X wins"
    game_drawn = "Draw"
    board_range = range(len(b))

    # Check the diagonals.
    fwd_diag = [b[i][i] for i in board_range]
    bck_diag = [b[i][len(b)-i-1] for i in board_range]

    if set(fwd_diag) == set([0]) or set(bck_diag) == set([0]):
        return o_wins

    if set(fwd_diag) == set([1]) or set(bck_diag) == set([1]):
        return x_wins

    # Check rows and columns.
    for i in board_range:
        col = [x[i] for x in b]

        if set(b[i]) == set([0]) or set(col) == set([0]):
            return o_wins

        if set(b[i]) == set([1]) or set(col) == set([1]):
            return x_wins

    return game_drawn

And I've replaced the basic testing function with unittest.TestClass.

class TestTicTac(unittest.TestCase):
    def test_three_by_three_x_wins(self):
        gameboard = [[0,0,1],
                     [0,1,0],
                     [1,1,0]]
        self.assertTrue(tictac(gameboard) == "X wins")
        # use assertTrue or failUnlessEqual?

    def test_three_by_three_o_wins(self):
        gameboard = [[0,1,1],
                     [0,0,0],
                     [1,1,0]]
        self.assertTrue(tictac(gameboard) == "O wins")

    def test_three_by_three_draw(self):
        gameboard = [[1,0,1],
                     [0,0,1],
                     [0,1,0]]
        self.assertTrue(tictac(gameboard) == "Draw")

    def test_four_by_four_draw(self):
        gameboard = [[0,0,1,0],
                     [1,1,0,1],
                     [0,1,1,1],
                     [0,1,0,1]]
        self.assertTrue(tictac(gameboard) == "Draw")

    def test_three_by_three_fail(self):
        gameboard = [[1,1,0],
                     [1,0],
                     [0,1,1]]
        self.assertFalse(tictac(gameboard))

    def test_three_by_three_with_none_x_wins(self):
        gameboard = [[None,0,1],
                     [0,1,0],
                     [1,1,0]]
        self.assertTrue(tictac(gameboard) == "X wins")

Is the usage of assertTrue() appropriate or would it be better to be testing with failUnlessEqual()?