class Puzzle:
    puzzle_count = 0
    guess_count = 0

    @classmethod
    def new_puzzle_trying_guess(cls, puzzle, guess, position=None):
        if position is None:
            position = puzzle.guess_position
        old = puzzle.game
        new = old[:position] + guess + old[position+1:]
        return cls(new)

    @classmethod
    def from_list(cls, a_list):
        joined = ''.join(a_list)
        return cls(joined)

    def __init__(self, a_game_string):
        Puzzle.puzzle_count += 1
        self.game = a_game_string
        if len(a_game_string) == 9:
            self.available_values = '123'
            self.line_size = 3
        elif len(a_game_string) == 81:
            self.available_values = '123456789'
            self.line_size = 9
        else:
            raise ValueError('problem must have length 9 or 81')
        self.guess_position = self.first_unsolved_position()

    @property
    def is_solved(self):
        return self.guess_position == -1

    def possible_answers(self, position=None):
        if position is None:
            position = self.guess_position
        row = Row(self, position)
        column = Column(self, position)
        sub_grid = SubGrid(self, position)
        return [c for c in self.available_values if c not in row and c not in column and c not in sub_grid]

    def find_next_puzzles(self):
        guesses = self.possible_answers()
        Puzzle.guess_count += len(guesses)
        puzzles = (Puzzle.new_puzzle_trying_guess(self, guess) for guess in guesses)
        return puzzles

    def first_unsolved_position(self):
        try:
            return self.game.index('0')
        except ValueError:
            return -1

class Component():
    def __iter__(self):
        return iter(self. used)

    @property
    def used_numbers(self):
        return [c for c in self.used if c != '0']


class Row(Component):
    def __init__(self, puzzle, position):
        start = position - position % puzzle.line_size
        self.used = puzzle.game[start:start + puzzle.line_size]


class Column(Component):
    def __init__(self, puzzle, position):
        start = position % puzzle.line_size
        self.used = puzzle.game[start:len(puzzle.game):puzzle.line_size]


class SubGrid(Component):
    def __init__(self, puzzle, position):
        starting_row_of_sub_grid = position - position % (3*puzzle.line_size)
        offset_in_row = position % 9 // 3 * 3
        first_index_in_sub_grid = starting_row_of_sub_grid + offset_in_row
        result = []
        if puzzle.line_size == 9:
            for row_index in range(3):
                cell = first_index_in_sub_grid + row_index*9
                result.extend(puzzle.game[cell:cell+3])
        self.used = result

class Solver:
    solver_count = 0

    def __init__(self, puzzle):
        Solver.solver_count += 1
        self.puzzle = puzzle

    def solve(self) -> Puzzle | None:
        if self.puzzle.is_solved:
            return self.puzzle
        for new_puzzle in self.puzzle.find_next_puzzles():
            solved_puzzle = Solver(new_puzzle).solve()
            if solved_puzzle:
                return solved_puzzle
        return None