Connect Four: Grids

Date: 02/03/2003 at 12:57:46
From: Robert
Subject: High School Math

Recently I encountered a problem I cant seem to solve. It is related 
to the grids in the game in Connect 4. 

I need to investigate different ways of putting 4 counters in a 
straight line in different size grids (squares and rectangles). For 
example in a 4 by 4 grid, I can find 10 combinations of putting four 
counters in a straight line, and in a 5 by 5 grid 28. 

I've done several of these but I can't find a pattern or rule. What I 
want to find is a formula that allows me to find the combination of a 
rectangle or square of any size.

Date: 02/03/2003 at 17:09:26
From: Doctor Greenie
Subject: Re: High School Math

Hi, Robert -

The rows of 4 consecutive markers can be in either (a) horizontal 
rows, or (b) vertical rows, or (c) diagonal rows from lower left to 
upper right, or (d) diagonal rows from upper left to lower right.

For each of these types of 4 markers in a row, analyze the number of 
ways you can make them on an n-by-n board.

For vertical rows, there are n columns, and the number of rows of 4 
consecutive markers you can make in each column is (n-3), so the 
number of vertical rows of 4 consecutive markers on an n-by-n board 
is n(n-3).

The analysis is exactly equivalent for the horizontal rows; the 
number of horizontal rows of 4 consecutive markers on an n-by-n board 
is also n(n-3).

For the diagonal rows from lower left to upper right, the number of 
rows of 4 of consecutive markers you can make is (n-3) on the main 
diagonal, 1 less than that on each of the diagonals one square away 
from the main diagonal, 2 less than that on each diagonal two squares 
away from the main diagonal, and so on, until there is just room for 
one such diagonal row. The total number of such diagonals is then

  1 + 2 + 3 + ... + (n-4) + (n-3) + (n-4) + ... + 3 + 2 + 1

A little algebra shows this sum to be equal to (n-3)(n-3).

And again the analysis for the diagonals in the other direction is 
the same as for these diagonals.

So the total number of ways of making a row of 4 consecutive markers 
horizontally, vertically, or diagonally on an n-by-n board is

   n(n-3) + n(n-3) + (n-3)(n-3) + (n-3)(n-3)

 = (n+n+(n-3)+(n-3))(n-3)

 = (4n-6)(n-3)

 = 2(n-3)(2n-3)

Note that this result agrees with the numbers you found for n=4 and 
n=5:

  n=4:  2(4-3)(8-3) = 2(1)(5) = 10
  n=5:  2(5-3)(10-3) = 2(2)(7) = 28

I hope this helps.  Please write back if you have any further 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/05/2003 at 11:25:41
From: Robert
Subject: Thank you (High School Math)

Thank you very much. This seems reasonable. I appreciate your help.