cp_solver.py

class CpSolver:
    def __init__(self, game: Clue, max_solve_time_per_turn: float) -> None:
        self.model = cp_model.CpModel()

        self.vars = np.array(
            [
                [
                    self.model.new_bool_var(f"Player {player + 1} has '{card}'")
                    for player in range(game.num_players)
                ]
                for card in game.index
            ]
        )

        # Enforce that each card i is assigned to at most one player
        for i in range(len(game.index)):
            self.model.add(sum(self.vars[i]) <= 1)

        # Enforce that each player has exactly len(hand) cards assigned to them
        for player, hand in enumerate(game.hands):
            self.model.add(sum(self.vars[:, player]) == len(hand))

        # Enforce that there are len(cards) - 1 assignments for each element
        for cards in game.elements.values():
            self.model.add(
                sum(self.vars[[game.index[card] for card in cards]].flatten())
                == len(cards) - 1
            )

        self.solver = cp_model.CpSolver()
        self.solver.parameters.enumerate_all_solutions = True
        self.solver.parameters.max_time_in_seconds = max_solve_time_per_turn

    def grid(self, game: Clue, player: int) -> np.ndarray:
        # Add constraints for last turn
        suggestion, response = game.history[-1] if len(game.history) > 0 else ([], {})
        for other_player, card in response.items():
            if card is not None:
                # Everyone knows that player i has at least one of the suggested cards
                self.model.add_at_least_one(
                    self.vars[[game.index[c] for c in suggestion], other_player]
                )
            else:
                # Everyone knows that player i does not have any of the suggested cards
                self.model.add(
                    sum(self.vars[[game.index[c] for c in suggestion], other_player])
                    == 0
                )

        # Add assumptions for the cards in the player's hand
        for card in game.hands[player]:
            self.model.add_assumption(self.vars[game.index[card], player])

        # Add assumptions for the cards that were revealed to the player in previous turns
        for i, (_, responses) in enumerate(game.history):
            if player == i % game.num_players:
                for j, card in responses.items():
                    if card is not None:
                        self.model.add_assumption(self.vars[game.index[card], j])

        callback = SolutionCallback(game, self.vars)
        status = self.solver.solve(self.model, callback)
        assert status == cp_model.OPTIMAL or status == cp_model.FEASIBLE
        self.model.clear_assumptions()  # Remove private knowledge from the model
        grid = callback.grid / callback.num_solutions
        # set every cell that does not equal zero or one to NaN
        grid[(grid != 0) & (grid != 1)] = np.nan
        return grid


class SolutionCallback(cp_model.CpSolverSolutionCallback):
    def __init__(self, game: Clue, vars: np.ndarray) -> None:
        super().__init__()
        self.grid = np.zeros((len(game.index), game.num_players))
        self.vars = vars
        self.num_solutions = 0

    def on_solution_callback(self) -> None:
        self.grid += np.vectorize(self.value)(self.vars)
        self.num_solutions += 1

deductive_solver.py

class DeductiveSolver:
    def __init__(self) -> None: ...

    def grid(self, game: Clue, player: int) -> np.ndarray:
        grid = np.full((len(game.index), game.num_players + 1), np.nan)
        constraints: list[Constraint] = []

        # Each card may only be in one place
        for i in range(len(game.index)):
            constraints.append((grid[i], 1))

        # Each player has game.hands[i] cards
        for i, hand in enumerate(game.hands):
            constraints.append((grid[:, i], len(hand)))

        # The solution must have exactly one card from each game element
        start = 0
        for cards in game.elements.values():
            end = start + len(cards)
            constraints.append((grid[start:end, -1], 1))
            start = end

        # Fill in the grid with the known cards
        for card in game.hands[player]:
            grid[game.index[card], player] = 1

        one_of: dict[int, list[set[int]]] = {i: [] for i in range(game.num_players)}

        # Fill in the grid with the known cards from previous turns
        for suggesting_player, (suggestion, responses) in enumerate(game.history):
            suggesting_player %= game.num_players
            for responding_player, card in responses.items():
                if card is not None:
                    if player == suggesting_player:
                        grid[game.index[card], responding_player] = 1
                    elif player != responding_player:
                        indices = [game.index[c] for c in suggestion]
                        # At least one of the suggested cards is in the responding player's hand
                        constraints.append(
                            (
                                tuple(
                                    grid[i : i + 1, responding_player] for i in indices
                                ),
                                (1, len(suggestion)),
                            )
                        )
                        # And no more than len(game.hands[responding_player]) - 1 of the
                        # unsuggested cards are in the responding player's hand
                        constraints.append(
                            (
                                tuple(
                                    grid[i + 1 : j, responding_player]
                                    for i, j in zip(
                                        [-1] + indices, indices + [len(game.index)]
                                    )
                                ),
                                (0, len(game.hands[responding_player]) - 1),
                            )
                        )
                        for previous_indices in one_of[responding_player]:
                            if previous_indices.isdisjoint(indices):
                                union = sorted(previous_indices.union(indices))
                                constraints.append(
                                    (
                                        tuple(
                                            grid[i + 1 : j, responding_player]
                                            for i, j in zip(
                                                [-1] + union, union + [len(game.index)]
                                            )
                                        ),
                                        (
                                            0,
                                            len(game.hands[responding_player])
                                            - len(union) // len(indices),
                                        ),
                                    )
                                )
                                one_of[responding_player].append(set(union))
                        one_of[responding_player].append(set(indices))
                else:
                    for card in suggestion:
                        grid[game.index[card], responding_player] = 0

        self.fill_grid(grid, constraints)

        last_grid = np.full_like(grid, np.nan)
        while not np.array_equal(grid, last_grid, equal_nan=True):
            last_grid = grid.copy()
            for indices in np.argwhere(np.isnan(grid)):
                for assignment in (0, 1):
                    original_grid = grid.copy()
                    grid[indices[0], indices[1]] = assignment
                    try:
                        self.fill_grid(grid, constraints)
                        grid[:] = original_grid[:]
                    except ValueError:
                        grid[:] = original_grid[:]
                        grid[indices[0], indices[1]] = 1 - assignment
                        self.fill_grid(grid, constraints)

        return grid[:, :-1]

    def fill_grid(self, grid: np.ndarray, constraints: list[Constraint]) -> None:
        last_grid = np.full_like(grid, np.nan)
        while not np.array_equal(grid, last_grid, equal_nan=True):
            last_grid = grid.copy()
            for views, bounds in constraints:
                if not isinstance(views, tuple):
                    views = (views,)
                if isinstance(bounds, int):
                    lower_bound = upper_bound = bounds
                else:
                    lower_bound, upper_bound = bounds
                values = np.concatenate([view.flatten() for view in views])
                if np.sum(np.nan_to_num(values, nan=1)) < lower_bound:
                    raise ValueError(
                        f"Impossible to have at least {lower_bound} cards in constraint"
                    )
                elif np.sum(np.nan_to_num(values, nan=1)) == lower_bound:
                    for view in views:
                        view[np.isnan(view)] = 1
                if np.nansum(values) == upper_bound:
                    for view in views:
                        view[np.isnan(view)] = 0
                elif np.nansum(values) > upper_bound:
                    raise ValueError(
                        f"Impossible to have at most {upper_bound} cards in constraint"
                    )

toy-example.txt

Player 1 has at least one of ['Miss Scarlet', 'Lead Pipe', 'Dining Room']
Player 3 has at least one of ['Miss Scarlet', 'Lead Pipe', 'Dining Room']
Player 1 has at least one of ['Miss Scarlet', 'Knife', 'Lounge']

Player 2's Simple Solver Grid:
Player                1  2  3
Element Card                 
Suspect Miss Scarlet     ✗  ✗
        Mr. Green        ✗  ✗
        Mrs. White    ✗  ✗  ✓
Weapon  Candlestick   ✗  ✗  ✗
        Knife         ✗  ✓  ✗
        Lead Pipe     ✗  ✗  ✓
Room    Hall          ✗  ✓  ✗
        Lounge           ✗  ✗
        Dining Room      ✗  ✗

Player 2's CP-SAT Solver Grid:
Player                1  2  3
Element Card                 
Suspect Miss Scarlet  ✓  ✗  ✗
        Mr. Green     ✗  ✗  ✗
        Mrs. White    ✗  ✗  ✓
Weapon  Candlestick   ✗  ✗  ✗
        Knife         ✗  ✓  ✗
        Lead Pipe     ✗  ✗  ✓
Room    Hall          ✗  ✓  ✗
        Lounge           ✗  ✗
        Dining Room      ✗  ✗