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.

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.

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  188 bytes

Takes input as a matrix with $1$ for red, $2$ 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='')=>/1|2/.test(m)?[1,13,15,17].some(n=>eval(`/(5|6)(.{${n}}\1){3}/`).test(m))?o:p.map((y,x)=>m[(m[y][x]|=4)^c||p[g(c^3,s+x,p[x]--),x]++,y][x]&=3)&&o:o=s)(5)

Try it online!

How?

The recursive function $g$ attempts to replace $1$'s and $2$'s in the input matrix with $5$'s and $6$'s respectively.

It also makes sure that we don't have four consecutive $5$'s or $6$'s before all $1$'s and $2$'s 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]$.

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