Once upon a time when I was about the age of 7, my father mentioned to me of the existence of "card solitaires" - games for single player. Perhaps it is a common way to make children busy :) Anyway, he showed me the description of three such games published in newspaper, and the first of them I learnt was just this one.
Rules are very simple. The deck of 36 cards is used, with 9 different ranks in 4 suits. Cards are shuffled
and put into 9 stacks or heaps (thus each stack having 4 cards). They all are faces-up but only top card
of each stack is visible anyway.
Each move consists of identifying a pair of cards of the same rank among the visible ones - and removing them. This opens some new cards (unless some of the stacks becomes empty).
Game continues until either all cards are removed (win) or no more pairs could be picked (lost).
Naturally, there is opportunity to make decisions (e.g. when more than two matching cards are visible or several different pairs are available). However since the cards beyond "tops" are not visible, there is limited information to base decisions upon. So it is much the game of chance.
Try playing the demo above and you probably find it difficult to win. Colors represent different suits, but they are not important. Simulation however may show that randomly generated layouts are often winnable.
Given initial layout of cards (knowing all cards, not only top ones) we want to know if there is a way to win the game.
It looks like fairly easy exercise for any programmer slightly above beginner level - however I don't know any better approach besides straightforward one - and it is supposedly very poor if number stacks, ranks and suits is slightly increased.
Input data contain the number of layouts in the first line. Next lines contain one layout per line. Each
layout is given as 9 strings (representing stacks) of 4 letters, representing card ranks.
Suits are not important and thus are omitted. The "top" card of each stack is at the end of the corresponding
string.
Answer should give yes or no for each of layouts, separated with spaces.
Example
input:
3
98AK 7T8T Q6KA 9J79 T67J 67JA 9KKJ 86AQ 8TQQ
KK6A QKT8 9TA9 A7QT QJ7Q 6J66 78JJ T8K9 879A
7J6Q T66T TJJA 687Q 98K8 QKTK 977A 89AA J9QK
answer:
yes no yes
In this example the first line, for example is solved by the following sequence of removals:
25 46 06 26 36 34 24 14 28 35 78 07 01 03 18 15 57 78
Here first pair of digits (25) means removing top cards (Aces) from stacks 2 and 5 (zero-based), the next
means removing from 4-th and 6-th (Jacks), on third move we remove Kings from stacks 0 and 6, so after
these three moves we have the following situation:
98A 7T8T Q6K 9J79 T67 67J 9K 86AQ 8TQQ