Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By Soroban

Math Help - TicTacToe problem

  1. #1
    Newbie
    Joined
    Mar 2012
    From
    UK
    Posts
    2

    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:

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

    TicTacToe problem-grid1.png
    and
    TicTacToe problem-grid2.png

    but obviously NOT
    TicTacToe problem-grid4.png

    Any ideas how these solutions can be generated?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,676
    Thanks
    608

    Re: TicTacToe problem

    Hello, Kratos!

    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:

    Click image for larger version. 

Name:	grid.png 
Views:	2 
Size:	2.8 KB 
ID:	23365
    I need to generate all diagonal solutions of length Y. So if Y is 3, then some of the solutions will be:

    Click image for larger version. 

Name:	grid1.png 
Views:	2 
Size:	3.3 KB 
ID:	23366
    and
    Click image for larger version. 

Name:	grid2.png 
Views:	1 
Size:	3.3 KB 
ID:	23367

    but obviously NOT
    Click image for larger version. 

Name:	grid4.png 
Views:	1 
Size:	3.3 KB 
ID:	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.
    Thanks from Kanwar245
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2012
    From
    UK
    Posts
    2

    Re: TicTacToe problem

    Wow, that makes sense. Thank you Soroban.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum