The complexity of Solitaire

Klondike is the well-known 52-card Solitaire game available on almost every computer. The problem of determining whether an n-card Klondike initial configuration can lead to a win is shown -complete. The problem remains -complete when only three suits are allowed instead of the usual four. When only two suits of opposite color are available, the problem is shown -hard. When the only two suits have the same color, two restrictions are shown in and in respectively. When a single suit is allowed, the problem drops in complexity down to [3], that is, the problem is solvable by a family of constant-depth unbounded-fan-in {and, or, mod3 }-circuits. Other cases are studied: for example, “no King” variant with an arbitrary number of suits of the same color and with an empty “pile” is -complete.