Design and Evaluate a Solver for a 36-Card Sum-Fifteen Game

Problem Statement

You are tasked with designing and evaluating a solver for a solitaire card game played with a custom 36-card deck containing four copies each of integers 1 through 9.

Game Rules

1. Setup: The deck is shuffled into a deterministic sequence of 36 cards. The top 9 cards are dealt face-up into 9 active board slots.
2. Move: A valid move consists of selecting exactly 3 cards currently on the board whose values sum to 15 (e.g., [1, 5, 9], [4, 5, 6], or [5, 5, 5]).
3. Replenish: The 3 chosen cards are discarded. The 3 empty board slots are immediately replenished by dealing the next 3 cards from the top of the deck in order. If the deck has fewer than 3 cards left, deal all remaining cards.
4. End Conditions:
   • Win: All 36 cards are successfully cleared (the board and deck are both empty).
   • Loss: No 3 cards currently on the board sum to 15, and the board cannot be cleared.

Implement the SumFifteenSolver class:

class SumFifteenSolver:
    def can_win_optimal(self, deck: list[int]) -> bool:
        """
        Returns True if there exists ANY sequence of legal moves
        that clears all 36 cards, using exhaustive search with pruning.
        """
        pass

    def can_win_greedy(self, deck: list[int]) -> bool:
        """
        Plays the game using a deterministic heuristic to select the best move
        at each step without backtracking. Returns True if the game is won.
        """
        pass

Input and Output

• deck: A list of 36 integers where each integer from 1 to 9 appears exactly 4 times.
• Return True if the deck is cleared under the chosen strategy; otherwise False.

Constraints

• len(deck) == 36
• deck.count(v) == 4 for each v in 1..9
• Board capacity is fixed at 9 cards.

Example 1

Input deck: [5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 2, 3, ...]
Initial board (first 9 cards): [5, 5, 5, 5, 5, 5, 5, 5, 5]
Move 1: Take [5, 5, 5]. Board refills with [1, 2, 3].

Example 2

Initial board: [1, 1, 1, 1, 2, 2, 2, 2, 3]
Triples summing to 15: None exist (max possible sum is 3 + 2 + 2 = 7).
Result: Game terminates immediately with False.

Edge Cases

• The final board state has 3 cards remaining that do not sum to 15.
• Multiple identical triples exist on the board (e.g., multiple copies of the same value); duplicates must be handled without redundant search paths.