Game

from itertools import permutations

# Constants
GRID_SIZE = 3
DIGITS = list(range(1, 10))

# Score functions
def score_rows(grid):
    return sum(row[0] * row[1] * row[2] for row in grid)

def score_cols(grid):
    return sum(grid[0][j] * grid[1][j] * grid[2][j] for j in range(3))

# Recursive Minimax with memoization
memo = {}

def serialize_state(grid, remaining_digits, is_rows_turn):
    flat_grid = tuple(cell for row in grid for cell in row)
    return (flat_grid, tuple(remaining_digits), is_rows_turn)

def minimax(grid, remaining_digits, is_rows_turn):
    key = serialize_state(grid, remaining_digits, is_rows_turn)
    if key in memo:
        return memo[key]

    if not remaining_digits:
        # Game over
        r_score = score_rows(grid)
        c_score = score_cols(grid)
        result = 1 if r_score > c_score else -1 if c_score > r_score else 0
        memo[key] = result
        return result

    best = -2 if is_rows_turn else 2
    for i in range(3):
        for j in range(3):
            if grid[i][j] == 0:
                for d in remaining_digits:
                    new_grid = [row[:] for row in grid]
                    new_grid[i][j] = d
                    new_remaining = remaining_digits[:]
                    new_remaining.remove(d)
                    result = minimax(new_grid, new_remaining, not is_rows_turn)
                    if is_rows_turn:
                        best = max(best, result)
                        if best == 1:
                            memo[key] = best
                            return best
                    else:
                        best = min(best, result)
                        if best == -1:
                            memo[key] = best
                            return best
    memo[key] = best
    return best

# Determine best first move
def best_opening_move():
    best_moves = []
    grid = [[0] * 3 for _ in range(3)]
    remaining = DIGITS[:]
    for i in range(3):
        for j in range(3):
            for d in DIGITS:
                new_grid = [row[:] for row in grid]
                new_grid[i][j] = d
                new_remaining = remaining[:]
                new_remaining.remove(d)
                result = minimax(new_grid, new_remaining, False)
                best_moves.append(((i, j, d), result))
    return best_moves

# Run
if __name__ == "__main__":
    opening_moves = best_opening_move()
    print("Best opening moves for Rows (Player 1):")
    for (i, j, d), result in sorted(opening_moves, key=lambda x: -x[1]):
        result_str = "Win" if result == 1 else "Loss" if result == -1 else "Draw"
        print(f"Place {d} at ({i},{j}): {result_str}")