wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> How many possible connect 4 games are there?
        
(Message started by: marsh8472 on Sep 20^th, 2012, 12:52am)

Title: How many possible connect 4 games are there?
Post by marsh8472 on Sep 20^th, 2012, 12:52am

http://upload.wikimedia.org/wikipedia/commons/a/ad/Connect_Four.gif

How many possible combinations of connect 4 games are there?

Title: Re: How many possible connect 4 games are there?
Post by marsh8472 on Sep 20^th, 2012, 8:00am

I wrote something that's cycling through every possible game and counting each one. Is that a feasible way to do this or would it take too long?

Title: Re: How many possible connect 4 games are there?
Post by towr on Sep 20^th, 2012, 8:54am

I think it's probably doable.

Title: Re: How many possible connect 4 games are there?
Post by marsh8472 on Sep 20^th, 2012, 9:59pm

I have 2.6 billion counted so far but looks like it's barely scratching the surface based on where it is.

From the looks of http://mathworld.wolfram.com/Connect-Four.html it's probably well over 10 trillion

Title: Re: How many possible connect 4 games are there?
Post by towr on Sep 20^th, 2012, 10:25pm

American trillions (10¹²), or European trillions (10¹⁸)?

Title: Re: How many possible connect 4 games are there?
Post by marsh8472 on Sep 20^th, 2012, 10:55pm

on 09/20/12 at 22:25:11, towr wrote:

American trillions (10¹²), or European trillions (10¹⁸)?

American but their numbers are probably counting games that probably are invalid. I wrote the counter in vb maybe I'll write one in another language that can go through them faster ;D

Title: Re: How many possible connect 4 games are there?
Post by marsh8472 on Sep 21^st, 2012, 6:07am

I think http://www.connectfour.net/Files/connect4.pdf has the answer (it's on the last page). Total combinations is: 70,728,639,995,483.

My program's still counting them. It's at 4 billion right now. I would probably have to leave it running for a few decades at this rate so I'll just take their word for it and quit that ;D

Title: Re: How many possible connect 4 games are there?
Post by towr on Sep 21^st, 2012, 7:07am

Yeah, you probably need a smarter approach to count the games then just brute-force it.

Title: Re: How many possible connect 4 games are there?
Post by Grimbal on Oct 12^th, 2012, 1:46am

Even with brute force, it is worth waiting now and run it on a faster computer later.

Title: Re: How many possible connect 4 games are there?
Post by skyrnin on Apr 2^nd, 2013, 2:43pm

There are many combinations for this game.. cant count.. ::)

Title: Re: How many possible connect 4 games are there?
Post by scottlouie on May 10^th, 2013, 3:03am

The number of possible Connect-Four game situations after n plies (n turns) is tabulated at OEISA212693. The total is 4531985219092. More in-depth explanation can be found at the links provided by the OEIS site.