code for https://www.reddit.com/r/math/comments/8b1z6h/interview_question/

solitaire.py

#!/usr/bin/env python3

# https://www.reddit.com/r/math/comments/8b1z6h/interview_question/

from statistics import mean
from functools import lru_cache
memoize = lru_cache(None)

rolls = tuple((min(i, j), max(i, j))
              for i in range(1, 7) for j in range(1, 7) if i+j <= 9)

table = {}


@memoize
def value(position=frozenset(range(1, 10)), roll=None, move=None):

    if move is not None:
        if not move.issubset(position):
            return 9 - len(position)
        return value(position - move)

    elif roll is None:
        return mean(value(position, roll) for roll in rolls)

    else:
        i, j = roll

        moves = [[i+j]] if i == j else [[i, j], [i+j]]

        val, move = max((value(position, move=frozenset(move)), move) for move in moves)

        table[position, roll] = move, val
        return val


print("value", value())

for (position, roll), (move, val) in sorted(table.items(), key=lambda x: x[1][1]):
    if len(position) >= 9:
        print(list(position), roll, f"{val:.6f}", move)

output:

value 5.143223988782197
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (3, 3) 4.847329 [6]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (2, 2) 4.873217 [4]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (1, 1) 4.892157 [2]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (2, 4) 4.996989 [2, 4]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (1, 4) 5.005090 [5]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (2, 3) 5.005090 [5]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (1, 3) 5.017288 [1, 3]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (1, 5) 5.017674 [1, 5]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (2, 6) 5.152256 [8]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (3, 5) 5.152256 [8]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (4, 4) 5.152256 [8]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (1, 2) 5.200526 [1, 2]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (1, 6) 5.248438 [7]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (2, 5) 5.248438 [7]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (3, 4) 5.248438 [7]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (3, 6) 5.486699 [9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9] (4, 5) 5.486699 [9]