Ok, this was fun (as always a little bit sobering to see the better solutions..), though strangely, so few people attempt this one. I think it might be a good idea to give a little more introductory info on the game rules like:
"(Mega)Connect4 is played on a vertical, rectangular board. The players tokens drop in a column and stack on top of each other. The win condition is met when the token of the current move connects N-1 other tokens of the same kind in a vertical or horizontal line or a line parallel to the boards diagonals."

I think that we should bend the rules a bit more, to ease testing the perf constraint: we could keep playing in the board even after the first True answer. What's your opinion?

(note: it looks like your solution has some kind of bug, btw... don't return from test_rand when res is True and you'll see it popping out.)

The Java verification solution is rather slow. It should at some point get replaced by a better method. Mine isn't that much faster.

I tried to read your test code: it's pretty hard to follow... ;o

• If you hope for translations, the validation function would need a rewrite (avoiding code duplication)
• I have a hard time to get how you generate the random inputs. Could you brief me about the general strategy you used? (a true and deterministic (as in: "always generate a valid input") shouldn't be hard to implement)
• you need more fixed tests (both in sample tests and test cases
• your solution is very slow, for now. Without making this a performance oriented kata, it would be good to have at the very least 100 random tests (my code passes the 15 tests in a blink while it's just "clever", not being really optimized)
• the validation function would benefit from a rewrite too, avoiding the console outputs when they aren't printing the shapes. Note that "invalid piece" isn't informative at all because you don't say which one is invalid and why it is.

Because of the size of the data, it's pretty hard to debug.
Not easy to do but some graphic representation would be useful.

Like green for good placements and red for conflicts or something like that.