CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 24

Thread: just4fun

  1. #1
    Join Date
    Aug 2004
    Location
    Bucharest, Romania... sometimes
    Posts
    1,039

    just4fun

    For those who enjoy spending time solving algorithmical problems, here's one:

    Quote Originally Posted by dontrememberauthor
    Given a square having side a positive integer (n > 0, n belongs to N*), find the smallest number of squares having also positive integer side, in which can be devided.
    Examples:
    - n = 2, 4 squares of side 1;
    - n = 3, 6 squares (1 of side 2 + 5 of side 1);
    - n = 5, 8 squares (1 of side 3 + 3 of side 2 + 4 of side 1)...
    I'm curious who's the first to find the solution for n = 13!

    If you care to write the implementation of your algorithm, try as input n = 9973.

    Have fun!
    Bogdan Apostol
    ESRI Developer Network

    Compilers demystified - Function pointers in Visual Basic 6.0
    Enables the use of function pointers in VB6 and shows how to embed native code in a VB application.

    Customize your R2H
    The unofficial board dedicated to ASUS R2H UMPC owners.

  2. #2
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: just4fun

    Do you have a proved solution (don't give one, just I wonder if there is).
    Even if n=7 (8 squares) I can't figure out some (especially O(n^2) as I see n=9973!) heuristics...
    "Programs must be written for people to read, and only incidentally for machines to execute."

  3. #3
    Join Date
    Aug 2004
    Location
    Bucharest, Romania... sometimes
    Posts
    1,039

    Re: just4fun

    Proved solution? I think so. Even that I didn't publish any complete mathematical study and proof of my implementation, doesn't mean that my solution is incorrect.
    I can assure you of one thing: my post is not trying to waste your time, and strongly believe that there is a flawless solution to this problem.
    So, find it if you can and enjoy doing this kind of activities.

    Thanks for showing interest. Hope we'll soon discuss about possible solutions.

    Have fun,
    Bogdan Apostol
    ESRI Developer Network

    Compilers demystified - Function pointers in Visual Basic 6.0
    Enables the use of function pointers in VB6 and shows how to embed native code in a VB application.

    Customize your R2H
    The unofficial board dedicated to ASUS R2H UMPC owners.

  4. #4
    Join Date
    Apr 2003
    Location
    Los Angeles area
    Posts
    776

    Re: just4fun

    It could be solved by backtracking or knapsack style and I see many optimizations available. The runtime is the bother.

    Also 13! can't be represented by a 32bit integer I believe so this would be a hassle.

  5. #5
    Join Date
    Aug 2004
    Location
    Bucharest, Romania... sometimes
    Posts
    1,039

    Re: just4fun

    Hi Joe!
    Considering the complexity of this problem, backtracking is more a theoretical solution, as it can be for most ever invented problems. As for knapsack style, there are no similarities with the coins problem, since coins doesn't have to be arranged in any way to fit the sum, so there, you can apply greedy. But in our square problem, there's no way to tell what relationship must exists in a set of squares, assuring us that they form a bigger square.
    You see, we know that our solution set of squares must satisfy some mathematical conditions, for example the area formula:
    sum(x[i]^2) = n^2, where n is the side of the input square and x[i] is the side of the i-th square in our solution; of course, sum() is a pseudo-function computing the sum.
    But only this formula is not enough to ensure a valid solution, because not all such sets can form the square of side n. Take for example the pitagoric numbers 3^2+4^2 =5^2; they are respecting the above formula, but a square of side 5 cannot be made out of a square having side 3 and a square with side 4. The arrangement is not possible.
    How else can you optimize a backtraking based algorithm? Maybe "Branch & Bound" by stoping the search at the last best solution, or "Divide & Conquer" by finding a way to reduce the problem to a smaller square?
    As RoboTact already mentioned, did you try to figure out "some heuristics" that might work for this problem?
    Quote Originally Posted by Joe Nellis
    Also 13! can't be represented by a 32bit integer I believe so this would be a hassle.
    Why would you wanna represent the factorial of 13 to solve this problem? This ain't a permutation problem, and even if it would've been, why to store the number of permutations? For a square with side n, there's no reason to store or work with numbers bigger than n^2 (as you use for area testing).

    Guys, yet nobody can give me the solution for n=13? It's a tiny little square that you can draw on a paper or a board... and divide it a few times, counting the number of squares required for a complete division.
    Bogdan Apostol
    ESRI Developer Network

    Compilers demystified - Function pointers in Visual Basic 6.0
    Enables the use of function pointers in VB6 and shows how to embed native code in a VB application.

    Customize your R2H
    The unofficial board dedicated to ASUS R2H UMPC owners.

  6. #6
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: just4fun

    It would be not an algotithmic solution it I just draw a square and try to figure out a solution... More of that: I even don't know a way to prove that some solution for n=13 is optimal. So, I think the only thing worth doing is to solve the general algorithmic problem. However, I just enjoing holidays before new term (writing my project ), from second of september I'll try to force the problem...
    "Programs must be written for people to read, and only incidentally for machines to execute."

  7. #7
    Join Date
    Apr 2003
    Location
    Los Angeles area
    Posts
    776

    Re: just4fun

    Quote Originally Posted by Bornish
    I'm curious who's the first to find the solution for n = 13!
    Quote Originally Posted by Bornish
    Why would you wanna represent the factorial of 13 to solve this problem?
    I'm sorry I participated in this thread now.

  8. #8
    Join Date
    Aug 2004
    Location
    Bucharest, Romania... sometimes
    Posts
    1,039

    Re: just4fun

    Joe, please accept my appologies.
    Didn't noticed that my original post was unclear.
    The exclamation sign was not supposed to be the factorial of 13, but the end of the sentence. I should've put a dot instead.

    Regards,
    Bogdan Apostol
    ESRI Developer Network

    Compilers demystified - Function pointers in Visual Basic 6.0
    Enables the use of function pointers in VB6 and shows how to embed native code in a VB application.

    Customize your R2H
    The unofficial board dedicated to ASUS R2H UMPC owners.

  9. #9
    Join Date
    Dec 2003
    Location
    St. Cugat - Catalunya
    Posts
    441

    Re: just4fun

    With n=13 a total of 12 squares (8, 5 three times, 3 two times, 2 two times, 1 four times)

    trivial solutions:
    n=2*m -> always four m-sided squares
    n=m^2 -> same solution as m

    Just a guess: the minimum number of squares is accomplished with the first (biggest) square being:
    1) for n=4*m-1 -> 2*m
    2) for n=4*m+1 -> 2*(m+1)


    in 1) there is always a solution with n+3 squares, but far from optimum
    in 2) there is always a solution with 2*(m+3), but again far from optimum

    ... will continue
    Did it help? rate it.

    The best conversation I had was over forty million years ago ... and that was with a coffee machine.

  10. #10
    Join Date
    Aug 2004
    Location
    Bucharest, Romania... sometimes
    Posts
    1,039

    Re: just4fun

    Quote Originally Posted by DeepButi
    With n=13 a total of 12 squares (8, 5 three times, 3 two times, 2 two times, 1 four times)
    It is possible to divide it in less than 12 squares.

    Quote Originally Posted by DeepButi
    trivial solutions:
    n=2*m -> always four m-sided squares
    n=m^2 -> same solution as m
    Correct! Moreover, if n is not prime number, then:
    for any prime divisor x, the square of side n can be devided in the same number of squares as the square of side x.
    Proof: take the division of the square with side x and scale it with n/x... a division of a square with side n will be obtained, because n/x is a positive integer!

    Quote Originally Posted by DeepButi
    Just a guess: the minimum number of squares is accomplished with the first (biggest) square being:
    1) for n=4*m-1 -> 2*m
    2) for n=4*m+1 -> 2*(m+1)


    in 1) there is always a solution with n+3 squares, but far from optimum
    in 2) there is always a solution with 2*(m+3), but again far from optimum
    In 1) you might be correct, because I have no proof that you cannot obtain a solution starting with the biggest square of (n+1)/2. In 2) you should've put 2*m+1, without brackets, so you have also (n+1)/2. Otherwise, you are wrong, because n=5 is a counter-example: the only division that can be made starting with a square of side 4 (n=5 means m=1 means 2*(m+1)=4) is a division of 10 squares! The solution for n=5 is 8 squares (one of side 4, three of side 2, four of side 1).

    Seems you're on a good track... hope you enjoy it.

    Good luck,
    Bogdan Apostol
    ESRI Developer Network

    Compilers demystified - Function pointers in Visual Basic 6.0
    Enables the use of function pointers in VB6 and shows how to embed native code in a VB application.

    Customize your R2H
    The unofficial board dedicated to ASUS R2H UMPC owners.

  11. #11
    Join Date
    Dec 2003
    Location
    St. Cugat - Catalunya
    Posts
    441

    Re: just4fun

    Quote Originally Posted by RoboTact
    Even if n=7 (8 squares) I can't figure out some (especially O(n^2) as I see n=9973!) heuristics...
    I must be missing something ... the only 8 squares decompositions of a 7x7 square are 4-3-2-2-2-2-2-2 and 3-3-3-3-2-2-2-1 ... and there is no arrangement possible with such ones
    My best for 7x7 is 9 squares (one decomposition, many arrangements) ... but 8?

    My brain is not what it used to be
    Last edited by DeepButi; September 1st, 2004 at 07:01 AM.
    Did it help? rate it.

    The best conversation I had was over forty million years ago ... and that was with a coffee machine.

  12. #12
    Join Date
    Sep 2004
    Posts
    1

    Re: just4fun

    I've written very short brute-force program. It's printed the following results:

    Brute-force method. Starting with N=5 and Opt=10
    Pass 1: Searching for optimal value...
    Found better solution: old=10, new=8
    Pass 2: Optimal value already found(8), restoring optimal map...
    AAABB
    AAABB
    AAACC
    DD.CC
    DD...



    Brute-force method. Starting with N=7 and Opt=14
    Pass 1: Searching for optimal value...
    Found better solution: old=14, new=10
    Found better solution: old=10, new=9
    Pass 2: Optimal value already found(9), restoring optimal map...
    AAAABBB
    AAAABBB
    AAAABBB
    AAAADD.
    CCC.DD.
    CCCEEFF
    CCCEEFF



    Brute-force method. Starting with N=11 and Opt=22
    Pass 1: Searching for optimal value...
    Found better solution: old=22, new=14
    Found better solution: old=14, new=12
    Found better solution: old=12, new=11
    Pass 2: Optimal value already found(11), restoring optimal map...
    AAAAAAABBBB
    AAAAAAABBBB
    AAAAAAABBBB
    AAAAAAABBBB
    AAAAAAACCCC
    AAAAAAACCCC
    AAAAAAACCCC
    DDDDFF.CCCC
    DDDDFFEEEGG
    DDDDHHEEEGG
    DDDDHHEEE..



    Brute-force method. Starting with N=13 and Opt=26
    Pass 1: Searching for optimal value...
    Found better solution: old=26, new=16
    Found better solution: old=16, new=14
    Found better solution: old=14, new=13
    Found better solution: old=13, new=12
    Found better solution: old=12, new=11
    Pass 2: Optimal value already found(11), restoring optimal map...
    AAAAAAABBBBBB
    AAAAAAABBBBBB
    AAAAAAABBBBBB
    AAAAAAABBBBBB
    AAAAAAABBBBBB
    AAAAAAABBBBBB
    AAAAAAAGGDDDD
    CCCCCC.GGDDDD
    CCCCCCEEEDDDD
    CCCCCCEEEDDDD
    CCCCCCEEE.FFF
    CCCCCCHHIIFFF
    CCCCCCHHIIFFF



    Brute-force method. Starting with N=15 and Opt=30
    Pass 1: Searching for optimal value...
    Found better solution: old=30, new=18
    Found better solution: old=18, new=10
    Found better solution: old=10, new=6
    Pass 2: Optimal value already found(6), restoring optimal map...
    AAAAAAAAAABBBBB
    AAAAAAAAAABBBBB
    AAAAAAAAAABBBBB
    AAAAAAAAAABBBBB
    AAAAAAAAAABBBBB
    AAAAAAAAAACCCCC
    AAAAAAAAAACCCCC
    AAAAAAAAAACCCCC
    AAAAAAAAAACCCCC
    AAAAAAAAAACCCCC
    DDDDDEEEEEFFFFF
    DDDDDEEEEEFFFFF
    DDDDDEEEEEFFFFF
    DDDDDEEEEEFFFFF
    DDDDDEEEEEFFFFF

  13. #13
    Join Date
    Aug 2004
    Location
    Bucharest, Romania... sometimes
    Posts
    1,039

    Re: just4fun

    Congratulations Vasya!
    You are the first to reply with the solution for n=13.
    Indeed, this square can be devided in minimum 11 squares, as you've already proved in your post.
    Have you tried your implementation with 9973 as input square?
    If your implementation is finding a solution (don't display the map), please let me know in how much time was found and please send me your implementation, or at least post the algorithm as pseudocode.

    Thanks,
    Bogdan Apostol
    ESRI Developer Network

    Compilers demystified - Function pointers in Visual Basic 6.0
    Enables the use of function pointers in VB6 and shows how to embed native code in a VB application.

    Customize your R2H
    The unofficial board dedicated to ASUS R2H UMPC owners.

  14. #14
    Join Date
    Dec 2003
    Location
    St. Cugat - Catalunya
    Posts
    441

    Re: just4fun

    12 for n=17 ... but pure brute force was not what I expected

    22222222111111111
    22222222111111111
    22222222111111111
    22222222111111111
    22222222111111111
    22222222111111111
    22222222111111111
    22222222111111111
    5555777B111111111
    55557778833333333
    55557778833333333
    5555C666633333333
    44444666633333333
    44444666633333333
    44444666633333333
    4444499AA33333333
    4444499AA33333333

    (mine would take ages for n=9973 )
    Did it help? rate it.

    The best conversation I had was over forty million years ago ... and that was with a coffee machine.

  15. #15
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: just4fun

    2 DeepButi
    Sorry, I meant "8 squares but for biggest"...

    Anyway, I don't think brute-force is a subject of consideration since you are talking about n=9973...
    "Programs must be written for people to read, and only incidentally for machines to execute."

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured