sudoku.py

import random
from copy import deepcopy
from collections import defaultdict
from itertools import product

from tqdm import tqdm


def play_game(size=3, verbose=False):
    candidates = {
        i: set(product(range(size * size), range(size * size))) for i in range(size * size)
    }
    to_play = {i: size * size for i in range(size * size)}
    player = -1
    grid = [[" " for _ in range(size * size)] for _ in range(size * size)]
    fill_per_square = defaultdict(int)
    count = -1
    while any(len(c) > 0 for c in candidates.values()):
        player = (player + 1) % (size * size)
        count += 1
        choices = candidates[player]

        if verbose and count != 0 and count % (size * size) == 0:
            print_grid(grid, size)
            print()

        if len(choices) == 0:
            continue

        choices_per_square = defaultdict(set)
        for r, c in choices:
            square = ((r // size) * size, (c // size) * size)
            choices_per_square[square].add((r, c))

        # Strategy: dumb, choose randomly from all choices
        # choose_from = choices

        # Strategy: choose from square that is most filled already
        # max_square = list(choices_per_square.keys())[0]
        # max_opponents = fill_per_square[square]
        # choose_from = set()
        # for square, opponents in fill_per_square.items():
        #     if square in choices_per_square:
        #         if opponents > max_opponents:
        #             max_opponents = opponents
        #             max_square = square
        #             choose_from = choices_per_square[max_square]
        #         elif opponents == max_opponents:
        #             choose_from.update(choices_per_square[square])


        # Strategy: choose from square where the fewest choices are left for the player
        min_square = list(choices_per_square.keys())[0]
        min_choices = len(choices_per_square[min_square])
        choose_from = choices_per_square[min_square]
        for square, choices_ in choices_per_square.items():
            if len(choices_) < min_choices:
                min_choices = len(choices_)
                min_square = square
                choose_from = choices_per_square[min_square]
            elif len(choices_) == min_choices:
                choose_from.update(choices_per_square[square])

        # Strategy: same as above, but choose choices that are also choices for other players
        choices_count = defaultdict(int)
        for choices_ in candidates.values():
            for choice_ in choices_:
                choices_count[choice_] += 1
        new_choose_from = set()
        max_count = 0
        for choice_, count_ in choices_count.items():
            if choice_ in choose_from:
                if count_ > max_count:
                    max_count = count_
                    new_choose_from = set([choice_])
                elif count_ == max_count:
                    new_choose_from.add(choice_)
        choose_from = new_choose_from

        r, c = random.sample(choose_from, 1)[0]
        grid[r][c] = player + 1
        to_play[player] -= 1

        # Remove row from choices
        choices -= set(product([r], range(size * size)))

        # Remove column from choices
        choices -= set(product(range(size * size), [c]))

        # Remove square from choices
        square_r = (r // size) * size
        square_c = (c // size) * size
        choices -= set(product(range(square_r, square_r + size), range(square_c, square_c + size)))

        fill_per_square[(square_r, square_c)] += 1

        # Remove (r, c) from choices of all players
        for cc in candidates.values():
            cc.discard((r, c))

    return to_play


def print_grid(grid, size):
    for i, line in enumerate(grid):
        string = ""
        for j, char in enumerate(line):
            if j % size == 0 and j != 0:
                string += "| "
            string += f"{char} "
        if i % size == 0 and i != 0:
            print("-" * (len(string) - 1))
        print(string)


def main(size=3):
    nb_games = 10000
    nb_wins = {i: 0 for i in range(size * size + 1)}
    wins = {i: 0 for i in range(size * size)}
    for _ in tqdm(range(nb_games)):
        to_play = play_game(size=size)
        nb_wins[sum(count == 0 for count in to_play.values())] += 1
        for player, count in to_play.items():
            if count == 0:
                wins[player] += 1
    for p, w in nb_wins.items():
        if w > 0:
            print(f"{p} {(w / nb_games) * 100:.2f}")
    print()
    for p, w in wins.items():
        print(f"{p} {(w / nb_games) * 100:.2f}")