You are given a partially filled Connect 4 grid (7x6).
O X
O X
X O X O O
X O X O X X
O X X X O O X
O O O X X O X
(Input can be given as a 1D or 2D array and as letters or numbers, etc.)
Assume that
- X started the game.
- Nobody has won yet.
- Players may not have played well until now, but now onwards they will both employ optimal strategies.
- Input grid is not faulty.
You must output a single value that indicates which player wins (or a draw)
Code golf challenge; so shortest code wins. Your program does not have to actual compute the output in reasonable amount of time, but you should be able to prove that the output will be obtained correctly in a finite amount of time.