What's the expected number of moves in this puzzle?

Question

A binary matrix of size n x n is given.

At each step a function checks whether each row and each column of the given matrix has at least one 1. If not, a purely random coordinate is chosen, say i, j where 1 <= i, j <= n, and it is marked as 1 if it's 0 else the 1 is retained.

The process is repeated until the matrix has each row and column having at least one 1.

Please tell what are the "expected number" of moves in this algorithm.

Answer 1

You can use heuristics and simulate over random filed to get approximate output.
You can create an output file over this, which will ensure you have simulated over a lot of data to ensure your approximate answer is close to optimized one.

Answer 2

for n = 1, 10 do

   -- prepare matrix of zeroes
   local P = {}
   for i = 0, n do
      P[i] = {}
      for j = 0, n do
         P[i][j] = 0
      end
   end
   -- set matrix element at (0,0) = 1
   P[0][0] = 1

   local E = 0  -- expected value of number of steps
   for move = 1, 1000000 do  -- emulate one million steps
      for x = n, 1, -1 do
      for y = n, 1, -1 do
         -- calculate probabilities after next move
         P[x][y] = (
            P[x][y]    *x      *y +
            P[x-1][y]  *(n+1-x)*y +
            P[x][y-1]  *x      *(n+1-y) +
            P[x-1][y-1]*(n+1-x)*(n+1-y)
         )/(n*n)
      end
      end
      E = E + P[n][n]*move
      P[0][0] = 0
      P[n][n] = 0
   end

   print(n, E)

end

Results (n, E):

1   1
2   3.6666666666667
3   6.8178571428571
4   10.301098901099
5   14.039464751085
6   17.982832900812
7   22.096912050614
8   26.357063600653
9   30.744803580639
10  35.245774455244

---

Exact value of E may be calculated, but it would require inversion of matrix N*N, where N=n*n