Expected steps to solve a 3x3 jigsaw puzzle

Question

Consider a 3x3 jigsaw puzzle, i.e., with 9 pieces. The first piece is randomly drawn from a bag and placed at its correct location. Subsequent pieces are drawn one at a time from the bag and they are placed only if they connect with any piece already placed. Pieces are returned to the bag if they do not connect with any piece already placed and another piece is drawn. Including the first draw, what is the expected number of draws required to finish the puzzle?

Edit: Two pieces connect if they share an edge (as in a jigsaw puzzle).

Answer 1

HINTS (updated for the Jigsaw puzzle case)

If you go brute force, you have 3 cases to consider:

1. First piece is at the center (weight $1/9$).
2. First piece is at the corner (weight $4/9$).
3. First piece is in the middle of a side (weight $4/9$).

In each case, the number of draws until you find a match is a geometric random variable (albeit the parameter will depend on the case), of which is easy to find the expected value. Then break down each of the cases based on what you get and continue on.

For example for case (1), probability of connecting the next piece is $p = 4/8=1/2$. Hence, we expect a connection in $2$ steps, which will always be the middle-of-the-side piece. Now probability of connecting is $5/7$, you expect $7/5 = 1.4$ steps and on connection you have 2 cases: (a) a corner piece (with weight $2/5$) or (b) a side piece (with weight $3/5$).

Can you finish?

Answer 2

Writing it down as a Markov process with all its states and calculating from the leaves of the tree should give you the answer. I have done it for the centrepiece for some intuition. Notice that many states are essentially the same due to symmetry of rotation. Hope it helps.