Introduction
Solitaire games are more than just casual pastimes; they represent "perfect information" puzzles that serve as rigorous benchmarks for AI planning and search algorithms. While classics like FreeCell have been extensively analyzed, "Birds of a Feather" (BoaF)—a game involving stacking cards in a grid based on matching suits or adjacent ranks—presents a unique computational challenge. This paper proves that generalized BoaF is NP-complete and provides a comprehensive classification of one million standard 4x4 deals by combining graph-theoretic filters with efficient heuristic search.
Complexity Analysis
To establish the theoretical difficulty of the game, the authors performed a reduction from 3-SAT. They constructed a generalized $N \times N$ BoaF board where specific blocks of cards represent logical clauses. In this construction, a deal is solvable if and only if the corresponding Boolean formula is satisfiable. This reduction places BoaF in the same class of computational difficulty as other popular puzzles like Minesweeper and Sudoku.
A key innovation in this proof is the "activator" card. This card must be moved into a specific column to "unlock" a sequence of moves, effectively mimicking the way a variable assignment satisfies a clause in logic. This demonstrates that as the board scales, the number of potential move sequences grows exponentially, making an exhaustive search impractical for large grids.
Graph-Theoretic Heuristics
To address the practical solvability of 4x4 deals, the authors developed four polynomial-time "filters" designed to identify unsolvable deals instantly. These filters analyze the match-by-card graph, where nodes represent cards and edges represent potential matches in suit or rank.
- Odd Bird: A card that matches no other card in the deck.
- Multiple Flocks: Occurs when the match-by-card graph is disconnected. If two groups of cards have no possible matches between them, they can never be merged into a single stack.
- Cut Edge: A move that, if executed, would permanently disconnect the graph, rendering the deal unsolvable.
- Lollipop Stick: A specific configuration where a "tail" of cards cannot be merged back into the main component.
Search Algorithms and Results
For deals that passed the initial filters, the authors employed two types of Depth-First Search (DFS). A standard DFS was compared against a Heuristic DFS that utilized a scoring function to reward boards with high connectivity and penalize those triggering "unsolvable" graph conditions.
The study utilized a testbed of one million random 4x4 deals generated via the standard FreeCell shuffler. The results were definitive:
- Solvability is the Norm: 99.812% of random deals (998,120) were found to be solvable. This suggests that while the general problem is NP-complete, the 4x4 instance is highly forgiving for players.
- Filter Efficiency: The graph-theoretic conditions identified 1,828 of the 1,880 unsolvable deals almost instantly. Specifically, the "Odd Bird" and "Multiple Flocks" conditions caught over 94% of all unsolvable cases.
- Search Performance: The Heuristic DFS solved 57% of deals in the minimum possible 15 moves and 90% of deals in under 100 steps.
Conclusion and Future Work
This research successfully bridges the gap between theoretical complexity and practical solvability in solitaire games. By using static graph analysis to prune search trees, the authors demonstrated that even NP-complete problems can be handled efficiently in specific domains.
Future work includes extending these algorithms to larger $N \times N$ or rectangular grids and developing more sophisticated filters, such as analyzing the "match-by-position" graph. The "penalty function" approach used here may also prove useful for other NP-complete planning problems beyond the realm of card games.
Summary updated