just4fun

[Bornish]

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

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!

[RoboTact]

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...

[Bornish]

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,

[Joe Nellis]

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.

[Bornish]

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?
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.

[RoboTact]

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 :cool: ), from second of september I'll try to force the problem...

[Joe Nellis]

I'm curious who's the first to find the solution for n = 13!


Why would you wanna represent the factorial of 13 to solve this problem?
I'm sorry I participated in this thread now.

[Bornish]

Joe, please accept my appologies. :cry:
Didn't noticed that my original post was unclear. :blush:
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,

[DeepButi]

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

[Bornish]

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.

trivial solutions:
n=2*m -> always four m-sided squares
n=m^2 -> same solution as mCorrect! 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!

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 optimumIn 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,

[DeepButi]

Even if n=7 (8 squares) I can't figure out some (especially O(n^2) as I see n=9973!) heuristics...
:confused: 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 :confused:
My best for 7x7 is 9 squares (one decomposition, many arrangements) ... but 8? :sick:

My brain is not what it used to be :cry:

[Vasya]

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

[Bornish]

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,

[DeepButi]

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

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

(mine would take ages for n=9973 :D )

[RoboTact]

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...

[RoboTact]

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...

[DeepButi]

Step 1) recursive function to find a better decomposition than the actual solution.
Step 2) recursive function to arrange it. If success we have a new actual solution.

Forget about recursivity, it's nice but time consuming. It can be translated to iterations in a known way.

Reasonable guesses:
a) solution contains one (n+1)/2 and two (n-1)/2
b) located at [0,0], [0,(n+1)/2] and [(n+1)/2,0]

b) implies there is always at least one 1-square, so Step1 skips decompositions without 1-squares.

Only non brute force trick on Step2: squares of identical size to last located (they are tried in decreasing order) only try posterior placements.

Obviously, 1-squares are not tried to be placed: they fit always :rolleyes:

So, Step2 is by far THE problem. How do you improve it? Any ideas?

[RoboTact]

One more method: greedy dynamics.
You form any decomposition, then create a temporary decomposition by cutting the area with a parrern. Pattern may be for example a square with a lower side, then you "mark" all cells on that pattern and replace them with the least number of squares, then replace with the least number of squares the remnants of squares outside the pattern cutted by it. If the resulted decomposition has a smaller number of squares, then you replace the current decomposition with the resulted, and so on. I think that the rectangles and squares with cutted (by another square) corner as patterns would be enough to reach the minimum from any starting decomposition, but I have no idea how to prove any thing like that... I'll implement my method, but at any rate it can't catch n=9973... It is (n^5) at least...

[DeepButi]

Just a curious pattern,
being xi the size of the ith-square, best solutions (seem to) have:

old guess
a) x1=(n+1)/2, x2=x3=(n-1)/2
more guesses
b) x4+x5=x1
c) x6=x5
d) x4 placed at [x2,n-x2] i.e. top right of free area

:eek:

[dennisb_palma]

Still new in this forum!u

How's this going? I go with others that said by decomposition. I think by recursion. Cut the square, then cut remaining polygons until end.

By the way,

when n = 4, how many squares?

[DeepButi]

dennisb_palma,
for any n=2*k ... allways 4 squares size k. Only prime numbers are interesting, read the whole thread :).

... and I'm not on it anymore ... just working with some MTD(f) algorithms for other problems.

[Bornish]

Hi!
Prime numbers are interesting as input for this problem, but not only. Take for example n = 143. Since 11 and 13 are divisors of 143, the square can be divided as a square of 11 or 13, but which one you should choose? Both 11 and 13 squares can be devided in minimum 11 squares. Can anyone prove the following?
Theorem 1: Considering the mentioned problem's conditions, if n1 and n2 are two prime numbers such as n1 < n2, then the solution (minimum number of squares required to divide a square of side n) for n = n1 is <= than for n = n2.
The proof for the above theorem can be quite helpful in solving the problem for numbers that are not prime.

Another interesting statement that requires proof is:
Theorem 2: Considering the mentioned problem's conditions, if n is prime number, then for any valid division of this square (solution or not), the sum of sides of all squares used in the division is >= 3*n-2.
Can anyone prove it? Yes? Then, how about trying to prove that the solution will add up to exactly 3*n-2...

One more thing: this problem made me recall the generalized Fibonacci series, and if you want to make it more complex, just change it to a 3D problem, by having cubes instead of squares. :eek:

You'll never be bored again :D

[RoboTact]

I don't know if there would be an answer after so much time, but I still wonder how this problem can be solved, how these theorems are related to original problem and how these theorems can be proved... None was advanced for a long time...

[Pixlegamer]

Why is just prime numbers interesting in this problem? Why isn't, like say 9 interesting or something? or does it fit into the group n = prime * prime ???

This sounds really interesting, This will keep me some time with pen and paper ^^

EDIT: Aha maybe I understand the thing that the nonprimes are not interesting, is it because, a square that can be divided has it's smallest number of smaller squares = the smallest divided number * 2? Okay I didn't even understand my self, example:

If I have, let's say 21 than 21 can be divided into the factors 3 and 7, the smallest factor is 3, so the smallest number of squares in a 21 square, is 3 * 2 = 6 ?

EDIT: (again) noop sorry, that was a bad statement, I think I get it now, it is not that you take the smallest factor * 2 but you take the smallest factor, and than you see how many squares fit in a square with the side of the smallest factor, okay, taht makes it really stupid to look for things that are not primes...