Need Help!!

This is a discussion on Need Help!! within the A Brief History of Cprogramming.com forums, part of the Community Boards category; i have a problem with this maths question: How many squares are on a chess board, including 2 x 2 ...

  1. #1
    shane
    Guest

    Need Help!!

    i have a problem with this maths question:
    How many squares are on a chess board, including 2 x 2 squares etc. can anyone help??????

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,705

    Post

    Try counting them.
    Code:
    #include <cmath>
    #include <complex>
    bool flip(bool value)
    {
           return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0)*(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    1x1 squares : 8x8 =64
    2x2 squares : 8x8 - 15 = 49
    3x3 squares : 8x8 - 15 - 13 = 36
    ...
    8x8 squares : 8x8 - 15 - 13 - ... = 1

    The number os positions for 1x1 squares is 64
    All but 15 positions can hold the top-left corner of a 2x2 square etc.

    To advertise a bit i wrote a simple program in Omicron to calculate the number of squares:
    Code:
    order = 8
    squares = 0
    repeat
      squares += 8*8 - (-order^2 + 18order - 17)
    until (order-=1)==0
    
    print squares
    Just run it using the online compiler
    I case you're in a hurry, the answer is 204.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  4. #4
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    So why didn't you write it in C? After all, this is a C-board .
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  5. #5
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Hehe, but this is General Discussions.
    And C++ requires main() and #includes

    Anyway, this should satisfy everyone:
    Code:
    #include <iostream>
    main()
    {
    	int order = 8;
    	int squares = 0;
    	do
    	{
    		squares += 8*8 - (-(order*order) + 18*order - 17);
    	} while (--order != 0)
    	std::cout << squares;
    }
    Last edited by Sang-drax; 10-20-2002 at 06:49 AM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  6. #6
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Sorry, SangDrax, but your function will only count the number of 8x8 squares (which is 1) thanx to your while condition .

    Anyway, if you want an even simplier function to calculate it, here:
    Code:
    #include <iostream.h>
    #include <conio.h>
    
    int Count()
    {
       int Squares = 0;
       for(int i=1; i<=8; i++)
       {
          Squares += (i * i);
       }
    
       return Squares;
    }
    
    int main()
    {
       cout << "Nr of squares: " << Count() << endl;
       getch();
    
       return 0;
    }
    (Output: 204)

  7. #7
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Originally posted by Magos
    Sorry, SangDrax, but your function will only count the number of 8x8 squares (which is 1)
    Oops! It's been corrected.

    Hehe, you're right that there is a simpler algorithm.
    I didn't think that much, just generated a formula for the sequence I wrote above.

    Now that I've thought a little, I have an even simpler solution:
    (faster for large n, at least)
    Code:
    squares = (2n^3 + 3n^2 + n) / 6
    where n is the width of the board
    Last edited by Sang-drax; 10-20-2002 at 07:40 AM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  8. #8
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Eh, n shouldn't be the number of squares, it should be the width of the board (8 in a chess board) .
    n=64 gives 89440.
    What did you use to get that formula. It doesn't look like the formula for a geometric sum.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  9. #9
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Sorry for the typo once again

    The formula can be proved using induction:
    Assume that it is correct for n=k, then use that assumption to prove that it must be true for n=k+1.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  10. #10
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Originally posted by Magos

    What did you use to get that formula.
    Ahh
    I used my program "Sequence finder".

    I've attached it here.
    If you want the source, download Omicron.
    Attached Files Attached Files
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21