The bank has been broken into, and all the local mafia thugs have an unusual alibi: they were at home playing Connect 4! In order to assist with the investigation, you are asked to write a program to validate all the Connect 4 boards that have been seized in order to check that the positions are indeed positions from a valid Connect 4 game, and have not been hastily put together as soon as the police knocked on the door.

The rules for connect 4: players R and Y take it in turns to drop tiles of their colour into columns of a 7x6 grid. When a player drops a tile into the column, it falls down to occupy the lowest unfilled position in that column. If a player manages to get a horizontal, vertical or diagonal run of four tiles of their colour on the board, then they win and the game ends immediately.

For example (with R starting), the following is an impossible Connect 4 position.

| | | | | | | |

| | | | | | | |

| | | | | | | |

| | |R| | | | |

| | |Y| | | | |

|R| |Y| | | | |

Your program or function must take in a Connect 4 board and return either

• A falsy value, indicating that the position is impossible or


• A string of numbers from 1 to 7, indicating one possible sequence of moves leading to that position (the columns are numbered 1 to 7 from left to right, and so the sequence 112, for example, indicates a red move in column 1, followed by a yellow move in column 1, followed by a red move in column 2). You may choose a column-numbering other than 1234567 if you like, as long as you specify in your solution. If you want to return the list in some other format; for example as an array [2, 4, 3, 1, 1, 3] then that is fine too, as long as it is easy to see what the moves are.

You can choose to read the board in in any sensible format including using letters other than R and Y for the players, but you must specify which player goes first. You can assume that the board will always be 6x7, with two players.

You may assume that the positions you receive are at least physically possible to create on a standard Connect 4 board; i.e., that there will be no 'floating' pieces. You can assume that the board will be non-empty.

This is code golf, so shortest answer wins. Standard loopholes apply.

Examples

| | | | | | | |

| | | | | | | |

| | | | | | | |

| | | | | | | | --> 1234567 (one possible answer)

| | | | | | | |

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



| | | | | | | |

| | | | | | | |

| | | | | | | |

| | |R| | | | | --> false

| | |Y| | | | |

|R| |Y| | | | |



| | | | | | | |

| | |Y| | | | |

| | |R| | | | |

| | |Y| | | | | --> 323333 (only possible answer)

| | |R| | | | |

| |Y|R| | | | |



| | | | | | | |

| | | | | | | |

| | | | | | | |     

| | | | | | | | --> false (this is the position arising after

| |Y|Y|Y|Y| | |     the moves 11223344, but using those moves

| |R|R|R|R| | |     the game would have ended once R made a 4)



| | | | | | | |

| | | | | | | |

|Y| | | | | | |     

|R|Y| | | | | | --> 2134231211 (among other possibilities)

|R|R|Y| | | | |

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



| | | | | | | |

| | | | | | | |

|Y| | | | | | |     

|R|Y| | | | | | --> false (for example, 21342312117 does not

|R|R|Y| | | | |     work, because Y has already made a diagonal 4)

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



| | | | | | | |

| | | | | | | |

| | | | | | | |     

| | | | | | | | --> 112244553 or similar

|Y|Y| |Y|Y| | |

|R|R|R|R|R| | |

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.