#!/usr/bin/python3
"""Count number of distinct tic-tac-toe games."""
all_squares = set(range(9))
winning_triples = tuple(frozenset(s) for s in (
{0,1,2},
{3,4,5},
{6,7,8},
{0,3,6},
{1,4,7},
{2,5,8},
{0,4,8},
{2,4,6},
))
def is_winning_position(s):
return any(triple <= squares for triple in winning_triples for squares in s)
def all_terminal_positions(s0 = (frozenset(), frozenset())):
"""Yield terminal position of all games.
This will produce duplicates for games that end in the same position."""
if is_winning_position(s0):
yield s0
else:
a, b = s0
moves = all_squares - (a|b)
if moves:
for move in moves:
s1 = (b, a | {move})
for p in all_terminal_positions(s1):
yield p
else:
# board is full, we are done
yield s0
if __name__ == '__main__':
positions = list(all_terminal_positions())
print(len(positions), len(set(positions)))