# Connect 3 on different board sizes

Two players, White and Black, sit down to play a few rounds of Connect 3 on a rectangular board of any size. White plays first. Assuming both players play perfectly:

What will be the outcome of this game (depending on the dimensions of the board)?

To make this game precise: A valid board is any rectangular grid of dimensions $$H\times W$$, where $$H$$ can be any positive integer or $$\mathbb{N}$$ (which gives a board of unbounded height), and $$W$$ can be any positive integer, $$\mathbb{N}$$ or $$\mathbb{Z}$$ (for an infinitely wide board in one or both (resp.) directions). The players then alternate in placing a token of their respective colour in any column, which will then occupy the lowest height that is not already taken up by a previous token. The game continues until either player has placed three tokens in a (horizontal, vertical or diagonal) line. (Otherwise the game continues forever or until the board is full, in which case there is no winner).

To give a fair warning, I was only able to solve this for most (in an appropriate sense) but not all grid sizes, so you should please feel free to also post partial progress.

Have fun! :)

• (I too can currently do "most but not all" but am attempting to turn this into "all"...) Commented Jul 29 at 14:51
• I can figure out a 2x2 board pretty easily but after that it gets tricky... :) Commented Jul 29 at 22:14

Note: this answer is not a complete solution; see final spoiler block for the remaining open cases.

3x5

or larger and tackle some smaller boards later. On this board the game is an easy win for

the first player.

The first player plays:

. . . . .
. . . . .
. . X . .

The second player then

must play in column 2 or 4. Otherwise the first player will do so on the next move so as to create a double threat, and the second player can only block one of them. So suppose the second player plays in column 2 (column 4 is the same in mirror image):

. . . . .
. . . . .
. O X . .

The rest is then forced:

. . . . .
. . X . .
. O X . .

. . O . .
. . X . .
. O X . .

. . O . .
. . X . .
. O X X .

. . O . .
. . X . .
. O X X O

. . O * .
. * X X *
. O X X O

As you can see, the left column was unused, so let's try a smaller board of size

3x4

The first player plays:

. . . .
. . . .
. X . .

The second player cannot play in columns 1 or 2, as that leads to the same play as in the previous larger board.

If the second player plays in column 3 we get the following sequence that leads to a winning position for the first player (who will then play column 4 at the earliest opportunity).

. . . .
. . . .
. X O .

. . . .
. X . .
. X O .

. O . .
. X . .
. X O .

. O . *
* X X *
. X O .

Alternatively, the second player could

play column 4, leading to this simple win for the first player which is essentially the same as seen in the 3x5 case:

. . . .
. . . .
. X . O

. . . .
. X . .
. X . O

. O . .
. X . .
. X . O

. O . .
. X . .
. X X O

. O . .
. X . .
O X X O

. O * .
* X X *
O X X O

So the only board sizes remaining are

1xn, 2xn, nx3, nx2

The 1xn and 2xn board result in a draw. A simple proof was described in the comments by DqwertyC and FlorianF.
Imagine the board is tiled by horizontal dominos, and for odd n there is an additional single square (1xn) or vertical domino (2xn) in the last column. Whenever the first player fills the first square of a domino, the second player will be able to complete the domino (or play anywhere if the other player did not create an uncompleted domino). All winning lines contain one horizontal domino so cannot be completed. Either player can use this strategy to avoid losing, so the game is drawn.

Similarly, nx2 is a draw, as either player can avoid losing by always playing the same column as the other player whenever possible.

The board sizes for which I do not have a solution are:

nx3
This seems tricky, and may need to be split into cases of even height and of odd height.

• Why nx2 differs from 2xn?
– z100
Commented Jul 29 at 17:47
• @z100 Because pieces fall down but don't fall left/right. Commented Jul 29 at 20:39
• For 2xn, I believe it's ROT13(n qenj sbe gur fnzr ernfba nf 1ka. B pna fgvyy nyjnlf cynl nqwnprag gb K. Rirel fcbg K pbhyq cynl ba gur frpbaq ebj jvyy unir na nqwnprag fcnpr jurer B pbhyq nyfb cynl bagb gur frpbaq ebj, fvapr rirel bpphcvrq fcnpr ba gur svefg ebj jvyy unir na nqwnprag bpphcvrq fcnpr). Commented Jul 29 at 23:23
• To formalize DqwertyC's take on 2xn, ROT13(Tebhc gur pbyhzaf va cnvef. Sbe rnpu zbir cynl gur bgure pbyhza. Vs a vf bqq gurer vf n fbyb pbyhza. Whfg cynl gur fnzr pbyhza.) This works for 1xn too. Commented Jul 30 at 3:13
• I have edited my answer to include this proof for 2xn (and 1xn). Thanks! Commented Jul 30 at 4:56

For 3-column grids that are tall enough but finite:

For easier illustration, let's turn the board sideways so that the gravity applies to the left instead of down. o is White, x is Black, and . is empty space. I'll call the three lanes rows, and each row as R1, R2, R3 from top to bottom.

Case 1:

Let's assume White plays R1.

If Black plays R1, White can respond with R3. Black is forced, White can play R2, and the next two moves are forced:

oxxo.
xo...
o....

Black cannot play R3 (White will play R3 immediately to win), and there is no way Black can turn R3 into their own win. White can wait until all of R1 and R2 are exhausted and Black is forced to play R3, at which point White wins.

If Black plays R2, White can respond with R2.

o....
xo...
.....

If Black plays R1, White can play R3 to force the same state as the first case.

ox...  oxxo.
xo...  xo...
o....  o....

If Black plays R3, White can play R3 which forms two immediate winning moves.

oA...
xo...
xoB..

If Black plays R2, White can play R3. Then the only way for Black to avoid immediate loss is R2. White can wait until R2 gets filled up. Whether White or Black gets forced to play R1 or R3 depends on the height, but it doesn't matter because White wins in both cases.

o.A..  ooA..
xox..  xox??
o.B..  oB...

If Black plays R3, this is where the things get complicated. With some aid of computer search, it turns out that most paths are losing for the current player. Pretty much the only way to ensure draw for both players is to (mostly) fill up R3 with alternating colors first, and then (mostly) fill up R1 with alternating colors that are opposite of R3, e.g.

oxoxo
o....
xoxox

at which point all vertical and diagonal runs of 3 are blocked, and no one can make a 3-in-a-row on R2 for obvious reasons.

White playing R3 first is the same by symmetry.

Case 2:

If White plays R2, Black playing R1 seems to be an eventual draw when the height is odd and a win for White when the height is even. Black playing R2 is a draw, though the correct response for White differs between odd and even height. The only pattern I can see is that the drawn boards look like a mix of the following two patterns:

oxoxo  oxoxo
oxoxo  xoxox
xoxox  xoxox

The program I used to do a computer search is here. In the code, 0 is White and 1 is Black.