Is this deck order search game well-known/studied?

Question

A friend of mine introduced this game to me, and apparently he also learnt about it from a friend of his. We unfortunately don't know the source, but we are deeply interested in studying it. The game is as follows:

With a regular deck facedown, start revealing cards as you count the number of the cards you revealed, say $r$. When $r$ matches the value of the card (with A representing $1$; J, $11$; Q, $12$; and K, $13$), put the matching card aside, and append the rest of the stack to the tail of the deck, again, facedown. Then, start counting again. If a match does not occur; meaning that you have counted to $13$ (your remaining cards can also be less than $13$; in that case, you have counted all your cards), and every card had a different value than its corresponding $r$, then you stop and note the number of the cards you have extracted. Find an initial order of the deck that extracts $51$ cards.

Example. The following initial order will extract $50$ cards. (Note about the format of the list: the first element is the value of the card at the top of the deck.)

[13 8 9 4 1 6 8 10 4 5 5 7 6 9 8 10 6 9 4 1 2 11 11 13 11 2 10 13 11 3 12 4 2 5 7 12 10 7 3 12 1 9 7 5 3 12 6 1 8 3 2 13]

Note that it's not possible to extract all of the cards. If it would, your last card would be $1$, that implies that the card put aside before it is also $1$, and so on. But there is only four $1$'s in the deck.

We suspects it's an exercise from an algebra or combinatorics book. Is this game well-known/studied?

Answer 1

Solution to the puzzle

Here is a solution that extracts 51 out of 52 cards, in the same format you used:

[1, 1, 1, 1, 3, 6, 10, 13, 3, 9, 8, 12, 7, 3, 8, 11, 13, 8, 7, 2, 12, 10, 4, 8, 11, 6, 7, 6, 10, 13, 2, 4, 5, 12, 9, 7, 5, 11, 4, 9, 4, 10, 13, 2, 5, 6, 12, 9, 3, 5, 11, 2]

Here is the order of card values we pick while playing out the solution above:

[1, 1, 1, 1, 13, 13, 13, 13, 12, 12, 12, 12, 11, 11, 11, 11, 10, 10, 10, 10, 9, 9, 8, 8, 7, 4, 5, 8, 4, 9, 9, 6, 4, 5, 7, 6, 4, 3, 7, 5, 8, 6, 7, 6, 5, 2, 3, 2, 3, 2, 2]
(3 left over at the end)

C++ code and program explanation

I found this solution using a solver I coded. My full C++ code is available here; it's pretty messy, but you could probably at least see how to run the code for other deck sizes if you wanted. In terms of understanding, I think the method will be more interesting than the code itself, so I'll explain it here.

My overall approach was backtracking, which basically means "I don't have a concrete solution, so just try random guesses, and if we run into a contradiction then undo the last guess(es) and try again". The program starts with a blank deck and fixes the cards one at a time by choosing what the next card value will be and then placing that card accordingly. At each step, the solver needs to figure out what guesses to try next and also be able to undo guesses when necessary. To accomplish that, the program keeps track of several pieces of information:

• State of the deck: 52 slots, starting out all blank but gradually getting filled in.
• Current position in the deck: After placing the cards we've locked in so far, which card will be sitting on top of the deck going into the next iteration?
• Which card values are "banned" in each remaining blank slot. By that I mean: If I place a 6 on the very first step, then the slot just before that 6 is not allowed to end up holding a 5. (Otherwise the 6's placement would retroactively become invalid, since then the first step should have selected the 5 instead.) As we place more and more cards, the "banned" lists get pretty restrictive.

Speeding up the program

By implementing the ideas above, I could make a correct solver. However, it would also take way way way too long to solve the case with the 52 card deck. (There are $\binom{52}{4} \binom{48}{4} \cdots \binom{4}{4} \approx 9.2 \times 10^{49}$ possible deck orderings to consider!) The key to a successful backtracking algorithm is finding good ways to a) choose good paths first most of the time and/or b) realize quickly when we're going down a doomed path so we can back up right away instead of wasting lots more time.

The main efficiency-boosting tricks I used in this program were:

1. Always start with 1, 1, 1, 1. After coding a brute-force solver and running it for some smaller deck sizes, I decided it seemed usually possible to find a solution under this constraint. Therefore I told the solver to assume this just to get the 1s out of the way and reduce the effective deck size by 4 cards.
2. Always guess higher card values first. At each step, I try to place the highest remaining card value if possible; then if that fails I try the second-highest; and so on. This is based on my heuristic feeling after solving a few small cases by hand: if I saved high values for later, I often had trouble placing them at the end when the deck is thinner and there are more "banned" values for the remaining slots.
3. Backtrack right away if some slot has every remaining card value banned. Obviously the partial solution is doomed in this scenario, so we can save time by backing out as soon as the problem is detected.
4. Backtrack right away if we have 2 cards that are too high to place. If we have two 10s remaining but only 8 blank slots left in the deck, we'll never be able to place those 10s because each iteration of the game can only check as many cards as the current deck size. Therefore there's no hope of extracting all but 1 card, so we can safely give up.

With these tricks, the program took around 1 hour to find a solution for the 52 card deck.

Bonus: Other deck sizes

I also had my solver run the same problem with different deck sizes. Let $R$ denote the number of ranks (# values per suit) and let $C$ denote the number of suits (how many copies of each value). The program treats both $R$ and $C as parameters that can be easily changed. For example, I tried running with $R$ ranging from $2$ up to $13$ while keeping $C = 4$ the whole time and I got these example solutions:

R=2: [1, 1, 1, 1, 2, 2, 2, 2]
R=3: [1, 1, 1, 2, 1, 3, 2, 2, 3, 3, 3, 2]
R=4: [1, 1, 1, 1, 4, 4, 2, 4, 3, 3, 3, 3, 2, 2, 4, 2]
R=5: [1, 1, 1, 1, 2, 4, 4, 3, 5, 2, 3, 5, 2, 5, 4, 3, 2, 4, 5, 3]
R=6: [1, 1, 1, 1, 5, 3, 2, 6, 2, 6, 4, 4, 2, 5, 2, 6, 5, 4, 4, 5, 3, 6, 3, 3]
R=7: [1, 1, 1, 1, 5, 3, 4, 7, 3, 5, 7, 2, 6, 2, 6, 4, 4, 7, 6, 3, 2, 6, 2, 5, 7, 4, 3, 5]
R=8: [1, 1, 1, 1, 6, 3, 4, 8, 6, 3, 2, 8, 7, 4, 4, 7, 6, 4, 5, 8, 5, 3, 2, 7, 3, 5, 5, 8, 2, 6, 2, 7]
R=9: [1, 1, 1, 1, 4, 4, 4, 9, 2, 5, 2, 6, 9, 4, 7, 5, 8, 8, 7, 6, 6, 9, 3, 3, 5, 8, 7, 3, 5, 2, 9, 6, 3, 2, 8, 7]
R=10: [1, 1, 1, 1, 2, 7, 2, 10, 7, 4, 4, 9, 6, 10, 8, 3, 2, 9, 4, 7, 6, 6, 8, 10, 5, 8, 7, 9, 6, 5, 5, 3, 4, 10, 3, 8, 2, 9, 3, 5]
R=11: [1, 1, 1, 1, 9, 3, 7, 11, 2, 5, 8, 10, 7, 5, 11, 5, 9, 8, 10, 4, 3, 6, 9, 3, 7, 11, 2, 6, 2, 10, 4, 8, 6, 9, 8, 5, 11, 2, 7, 6, 10, 4, 3, 4]
R=12: [1, 1, 1, 1, 2, 5, 5, 12, 9, 8, 4, 11, 6, 3, 8, 12, 10, 7, 4, 11, 2, 9, 2, 10, 4, 3, 4, 12, 9, 6, 8, 11, 6, 7, 6, 10, 3, 3, 5, 12, 9, 7, 5, 11, 8, 7, 2, 10]

I of course still encourage you to investigate further, starting from my code or pencil and paper or however else. Just because you have a solution for the 52-card deck doesn't mean there's no more fun to be had thinking about this puzzle :)

Final note: Citations

I do realize that what you actually asked for here was a citation, not a solution! I haven't heard of this problem before and I did a bit of searching but didn't find anything. My only "input" here is that I think you should check sources beyond just algebra and combinatorics; for example, it seems possible that the best solution involves some kind of programming (maybe more efficient than mine), in which case you'd want to try including "codeforces" or "atcoder" in your search queries.

Of course, if you knew for sure whether it's an example in a number theory vs. discrete math vs. programming textbook then that would go a long way toward hinting what strategy you should use!

Anyway, it's also possible this problem is just not very known/studied/published. Shrug, I'll watch with interest to see if someone else comes up with a citation for you.