Probability of winning a card game where you draw successive cards until all cards have been drawn

Question

I had this question in an interview a few weeks back and I haven't been able to stop thinking about it since.

There is a deck of cards before you - in the deck are cards on which there is one of three shapes (Square, Triangle, Circle) drawn in one of three colors (Red, Blue, Green). The deck consists of all possible color / shape combos with no duplicates - 9 cards total.

To win the game, you must draw each card in the deck. Each successive card you draw MUST have one property in common with the previously drawn card. E.g. if you draw a Red Triangle, then the next card must either be red or have a triangle on it. If you draw a card that has nothing in common with the previous card, you lose.

What's the probability of winning this game?

Answer 1

This sounds like a job for computer code and seems a reasonable question to be asked in a coding interview. The number of cases is not so large that it is unmanageable, only $9!=362880$ outcomes.

That said, I do not as of yet see a clean approach to take with pencil and paper. Having thrown together some quick and dirty code (shown below) I get a value of $1512$ for the three-colors three-shapes case giving then a probability of $\dfrac{1512}{9!}$. The two-color two-shape case and one-color one-shape case can be found by inspection to be $8$ and $1$ respectively.

We can now plug these numbers in to OEIS.org to see if it is a known sequence and indeed it is. https://oeis.org/A096970. We can see how OEIS interprets the problem as counting the number of hamiltonian paths on the rook graph $K_n\square K_n$ though it doesn't elaborate further on the methods used to generate the entries given in the sequence already. I certainly wouldn't trust my code to be able to generate many more entries in any reasonable amount of time... but then again, I wasn't setting out to do so.

In javascript:

function permutator(inputArr) {
   var results = [];

   function permute(arr, memo) {
     var cur, memo = memo || [];

     for (var i = 0; i < arr.length; i++) {
       cur = arr.splice(i, 1);
       if (arr.length === 0) {
         results.push(memo.concat(cur));
       }
       permute(arr.slice(), memo.concat(cur));
       arr.splice(i, 0, cur[0]);
     }

     return results;
   }

   return permute(inputArr);
 }
 count=0; 
 permutator(['A1','A2','A3','B1','B2','B3','C1','C2','C3']).$each(function(p){
      fail=false;
      for(i=1; i<p.length; i++){
           if(p[i][0]!=p[i-1][0] && p[i][1]!=p[i-1][1]){
                fail = true;
                break;
           }
      }
      if(!fail){
           count+=1; console.log(p)
      }
 })

(I use a custom .$each which should be clear how it works. Adjust accordingly if you wish to run it yourself. It could also be further adjusted if you wish to create the deck of cards programmatically rather than hardcoding. Again, I was lazy and just after a quick answer.)