# TicTacToe problem

• March 13th 2012, 09:07 AM
Kratos
TicTacToe problem
Hi guys, hopefully this is an easy one for you.

Given a grid of nxn squares, where each square has an id, the first(top left) square has id 0 (so a 5x5 grid will have ids 0-24) like below:

Attachment 23365
I need to generate all diagonal solutions of length Y. So if Y is 3, then some of the solutions will be:

Attachment 23366
and
Attachment 23367

but obviously NOT
Attachment 23368

Any ideas how these solutions can be generated?
• March 13th 2012, 11:00 AM
Soroban
Re: TicTacToe problem
Hello, Kratos!

Quote:

Given a grid of $n\times n$ squares, where each square has an ID.
The first(top left) square has IDd 0 (so a 5x5 grid will have IDs 0-24) like below:

Attachment 23365
I need to generate all diagonal solutions of length Y. So if Y is 3, then some of the solutions will be:

Attachment 23366
and
Attachment 23367

but obviously NOT
Attachment 23368

Any ideas how these solutions can be generated?

We have an $n\times n$ grid.
And we want diagonals of length $y.$

Across the top row, there are $n - y + 1$ diagonals.

And there will be $n-y+1$ such rows.

Hence, there are $(n-y+1)^2$ diagonals of this form $\searrow$
. . and $(n-y+1)^2$ diagonals of this form $\swarrow$

Therefore, there are: $2(n-y+1)^2$ diagonals of length $y.$
• March 15th 2012, 09:11 AM
Kratos
Re: TicTacToe problem
Wow, that makes sense. Thank you Soroban.