title: Find any one sequence of moves that can generate provided Connect-4 board state
body: <p>Given a valid <a href="https://en.wikipedia.org/wiki/Connect_Four" rel="nofollow noreferrer">Connect-4</a> board state in a matrix A(6x7), where </p>
  
  <pre><code>A[i][j] = '0',  if empty,
  A[i][j] = 'r',  if filled with red stone,
  A[i][j] = 'y',  if filled with yellow stone.
  </code></pre>
  
  <p>I am trying to think of an algorithm which can return any valid sequence of moves that can generate the given board state.</p>
  
  <p>It can be assumed that red always starts the game.</p>
  
  <p>Example:</p>
  
  <pre><code>A = [0 0 0 0 0 0 0
       0 0 0 0 0 0 0
       0 0 0 y 0 0 0
       0 0 0 r 0 0 0
       0 0 0 y 0 0 0
       0 0 r r 0 0 0]
  
  Valid sequence of moves:- 44443 
  </code></pre>
  
  <p>44443 means -><br>
  First player moves on column number 4,<br>
  then Second player moves on column number 4, ...
  (Taking column numbers as 1-indexed)</p>
  
  <p><strong>My approach</strong>:-<br>
  -) First finding out the colour of last stone by parity of the number of non-empty positions. Let that colour be <code>last_coloured</code>.<br>
  -) Then take one topmost stone of colour <code>last_coloured</code> out from the board, recursively continue forward, if cannot find any stone of colour <code>last_coloured</code> then backtrack.</p>
  
  <p>Although this approach can solve for 7*6 board in less than 16^21 steps.<br>
  (Edit: Thanks to @Prune for correcting this upper bound)</p>
  
  <p><strong>Question 1)</strong> Is there a better bound on the number of steps of the above approach?<br>
  <strong>Question 2)</strong> Is there any better approach?</p>