Klondike Solvability

Description

Developed as a bachelors thesis project for Tampere University of Applied Sciences (TAMK UAS). The game prototype was used as a testbed to develop tools for studying card configuration solvability.

Controls & Features

• Mouse controls
• The stock scrolls forwards and backwards with mouse wheel
• Pressing mouse wheel (mouse 3), mouse 4, or mouse 5 highlights card solutions
• Double click or right click moves eligible cards to Foundation
• Auto-Stack moves all available cards to Foundation

Visual aids

• Cards with green outline can be solved to Foundation
• Cards with orange outline can only be solved to Foundation. In the picture the C8 blocks both black tens, and as such must be solved to Foundation. The information is passed on recursively down the suit to warn the player.
• Red outline means a card blocks one of the it's solutions cards:
  eg. the rightmost Black Jack blocks a Red Queen.
• Yellow outline suggests a lower priority: the leftmost Black Jack should be solved after the rightmost Black Jack is solved first (in most cases).

Unsolvable game detection

The project features a new recursive method of tracing card solution routes available. If all routes are blocked a card is detected as impossible (red). This is used to detect unsolvable card configurations when the cards are randomly dealt. It also detects when a card becomes impossible during a game.

This recursive method was tested on a sample of 1 000 000 games. 2,24% were detected as unsolvable by the recursive method/algorithm. More complex unsolvable card configurations fall outside the method search space or depth. At least 81% of games are known to be solvable but the upper bound for draw-1 Klondike is unknown.

The "New Rare Unsolvable" -button is a development tool to test the recursive method. It generates new card configurations until it detects an unsolvable one. This feature was used for sanity checks to verify the games the feature detected really are unsolvable. As a human challenge is's a kind of pessimistic challenge in reverse: the game is already lost but you have to figure out why that's the case.