Connect 4: Spot the Fake!

JavaScript (ES6),  202 194 187  183 bytes

Takes input as a matrix with \$2\$ for red, \$4\$ for yellow and \$0\$ for empty. Returns a string of 0-indexed moves (or an empty string if there's no solution). Reds start the game.

m=>(p=[...'5555555'],g=(c,s=o='')=>/2|4/.test(m)?['',0,2,4].some(n=>m.join``.match(`(1|3)(.{1${n}}\\1){3}`))?o:p.map((y,x)=>m[m[y][x]--^c||p[g(c^6,s+x,p[x]--),x]++,y][x]++)&&o:o=s)(2)

Try it online!

How?

The recursive function \$g\$ attempts to replace all \$2\$'s and \$4\$'s in the input matrix with \$1\$'s and \$3\$'s respectively.

While doing so, it makes sure that we don't have any run of four consecutive odd values until all even values have disappeared (i.e. if a side wins, it must be the last move).

The row \$y\$ of the next available slot for each column \$x\$ is stored in \$p[x]\$.

Commented

m => (                            // m[] = input matrix
  p = [...'5555555'],             // p[] = next row for each column
  g = (c,                         // g = recursive function taking c = color,
          s = o = '') =>          //     s = current solution, o = final output
    /2|4/.test(m) ?               // if the matrix still contains at least a 2 or a 4:
      ['', 0, 2, 4]               //   see if we have four consecutive 1's or 3's
      .some(n =>                  //   by testing the four possible directions
        m.join``                  //   on the joined matrix, using
        .match(                   //   a regular expression where the number of characters
          `(1|3)(.{1${n}}\\1){3}` //   between each occurrence is either 1, 10, 12 or 14
        )                         //   (horizontal, diagonal, vertical, anti-diagonal)
      ) ?                         //   if we have a match:
        o                         //     abort and just return the current value of o
      :                           //   else:
        p.map((y, x) =>           //     for each cell at (x, y = p[x]):
          m[                      // 
            m[y][x]--             //       decrement the value of the cell
            ^ c ||                //       compare the original value with c
            p[                    //       if they're equal:
              g(                  //         do a recursive call with:
                c ^ 6,            //           the other color
                s + x,            //           the updated solution
                p[x]--            //           the updated row for this column
              ),                  //         end of recursive call
              x                   //         then:
            ]++,                  //         restore p[x]
            y                     //         and restore m[y][x]
          ][x]++                  //         to their initial values
        ) && o                    //     end of map(); yield o
    :                             // else:
      o = s                       //   we've found a solution: copy s to o
)(2)                              // initial call to g() with c = 2

Jelly, 57 bytes

ŒṪŒ!µ0ịŒṬ¬a³ZU,Ɗ;ŒD$€Ẏṡ€4Ḅo1%15;Ḋ€ṢṚ$Ƒƙ$Ȧȧœị³$2R¤ṁ$ƑµƇṪṪ€

Takes a matrix where 0 is unfilled, 1 played first, and 2 played second. Yields a list of 1-indexed columns, empty if a fake was identified.

Try it online! (too inefficient for more than 7 pieces to run in under a minute)

Note:

1. Assumes that no "floating" pieces are present (fix this by prepending ZṠṢ€Ƒȧ for +6 bytes)
2. Assumes that the empty board is a fake

Python 2, 295 285 bytes

def f(a):
 if 1-any(a):return[]
 p=sum(map(len,a))%2
 for i in R(7):
	if a[i][-1:]==`p`:
	 b=a[:];b[i]=b[i][:-1];L=f(b)
	 if L>1>(`1-p`*4in','.join([J((u[j]+' '*14)[n-j]for j in R(7))for n in R(12)for u in[b,b[::-1]]]+b+map(J,zip(*[r+' '*7for r in b])))):return L+[i]
R=range;J=''.join

Try it online!

-10 thx to Jo King.

Input is a list of strings representing the columns; with '1' for Red and '0' for Yellow. The strings are not ' '-padded. So the (falsey) case:

| | | | | | | |
| | | | | | | |
|Y| | | | | | |
|R|Y| | | | | |
|R|R|Y| | | | |
|Y|R|R|Y| | |R|

is input as:

[
  '0110',
  '110',
  '10',
  '0',
  '',
  '',
  '1'
]

Output is a list of column indexes, 0-indexed, that could make the board; or None if it's not valid.

Accepts the empty board as valid (returns the empty list [] instead of None).

This approach is recursive from the last move to the first move: based on the parity of the total number of moves taken, we remove either the last Red move or the last Yellow move (or fail if that is not possible); check the resulting board to see if the opponent has 4-in-a-row (in which case fail, because the game should have stopped already); otherwise, recurse until the board is empty (which is valid).

The 4-in-a-row code is the most bloaty part. All the diagonal strings for the matrix b are generated by:

[
    ''.join(
        (u[j]+' '*14)[n-j] for j in range(7)
    )
    for u in[b,b[::-1]]for n in range(12) 
]

which first lists out the 'down-sloping' diagonals, and then 'up-sloping' ones.