# Thread: TicTacToe problem

1. ## 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:

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

and

but obviously NOT

Any ideas how these solutions can be generated?

2. ## Re: TicTacToe problem

Hello, Kratos!

Given a grid of $\displaystyle 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:

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

and

but obviously NOT

Any ideas how these solutions can be generated?

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

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

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

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

Therefore, there are: $\displaystyle 2(n-y+1)^2$ diagonals of length $\displaystyle y.$

3. ## Re: TicTacToe problem

Wow, that makes sense. Thank you Soroban.