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

(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.

  • \$\begingroup\$ Related. \$\endgroup\$ Nov 11, 2015 at 14:13
  • \$\begingroup\$ @MartinBüttner Does that mean I will get downvoted, or is it okay to leave my question here? \$\endgroup\$ Nov 11, 2015 at 14:25
  • 4
    \$\begingroup\$ It just means the questions are related, nothing more, nothing less. The purpose of posting the link is for the challenges to appear in each other's "Linked" sidebar, so people can find related challenges more easily. If I considered your question a duplicate, I would have said so (or just closed it), so don't worry. :) \$\endgroup\$ Nov 11, 2015 at 14:27
  • 2
    \$\begingroup\$ Is "optimal play" well defined? If so, can you provide a link describing the algorithm for optimal play? \$\endgroup\$
    – Rainbolt
    Nov 11, 2015 at 14:28
  • 2
    \$\begingroup\$ @Rainbolt It has been solved and there exist perfect algorithms also. Read Wikipedia for more. \$\endgroup\$ Nov 11, 2015 at 14:34

1 Answer 1


Perl, 119 118 117 bytes

Includes +4 for -0p

Give rotated board padded with spaces on STDIN (gravity pulls stones to the right)



#!/usr/bin/perl -p0
y/XO/OX/if$^S|y/X//>y/O//;$_=$$_||=/Z@{[map"|O".".{$_}O"x3,0,5..7]}/sx||s% (?! )%$_="$`X$'";do$0%eg?/1/?3:1+/2/:2

Prints 3 if player to move wins, 1 if player to move loses and 2 for a draw.

On older perls you can use a literal ^S to gain one byte. If you don't mind extreme inefficiency you can leave out the $$_||= (transposition table) and gain 6 more bytes. If you leave out the $_= it will show you where to play instead of the result (play on 1 and win if there is one, play on 2 and draw if there is one or play on any 3 and lose)

Builds and evaluates a complete minimax tree. You will run out of memory and time unless the board is already reasonably well filled.

  • 2
    \$\begingroup\$ Why on earth did someone downvote? The golfing is truly amazing (I golf with perl and obtaining such a solution is extremly hard - I'm not sure any other perl golfer I know could have come up with that code). And the code has the required behavior. \$\endgroup\$
    – Dada
    Oct 19, 2016 at 19:56
  • \$\begingroup\$ This makes my brain hurt. +1! \$\endgroup\$ Oct 19, 2016 at 20:01
  • \$\begingroup\$ @Dada how do you know this answer is down voted? I see 3 as vote... \$\endgroup\$
    – user58988
    Oct 19, 2016 at 21:37
  • \$\begingroup\$ @RosLuP when I first saw this post, it had 1 downvote. Also, when you have enough rep, you can see how many up and down votes a post has : in that case, now it has 4 up and 1 down. \$\endgroup\$
    – Dada
    Oct 20, 2016 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.