I wanted to make a code that searched for solutions the same way my brain did. But at that time my way of solving was unclear.
This week I got encouraged to continue the work, after a friend of mine said he solved it. He did this way:
1 - Created by hand non-optimal solutions just to count how many squares he would use in maximum.
2 - For each prime number, he generated all the square sets that could generate a better solutions. For example, a set for prime number 5 is:
3, 3, 2, 1, 1, 1 because: 5^2 = 3^2 + 3^2 + 2^2 + 1 + 1 + 1
3 - Then, for each prime number, he tried to find solutions with 1 square less than his hand-made solutions, and then 1 less (if possible), and so on.
His program needed to run for long and the final submitted code had all the prime number solutions pre-calculated. But he god AC before me
Note that he based himself strontly in this rule:
The sum of the areas of squares of each solution is the equivalent to the area of the bigger square.
I talked with him about this rule, as a tip, but I had never tried to implement this. It was not clear for me how to do it. After he got AC, I tried it (a bit different than him though), but I generated milions of sets. I tried to reduce the number of sets, but my code started to get complicated and again I saw myself trying to do the same intelligent program I had tried before.
Not to get lost in my code again, I paused the coding and tried to clarify my ideas. I made progress using excel and the info from posts above (minimum number of smaller squares required to fill each prime square).
I made so much progress that I could find all the solutions by hand with the minimum number os squares. I transposed all the drawings into the output format of this problem, made functions to check my output, fixed typing errors, submitted it, and got Accepted in 0.000 seconds (see me in ranking as Murilo Perrone).
Now, analysing all the solutions I made by hand, I see that there is an extremelly efficient method that can find all of that solutions extremelly fast. My next step is coding something that implements such method. If I succeed, I will probably be able to find solutions for squares so much bigger than 50x50.
I have even thought about extrapolating this problem into the 3rd dimension. This would mean finding minimum number of cubes required to fill up a cubed space. The method would be the same. In fact the algorithim would only receive one more loop in each space sweep.
OK, now some info about my method (after implementing it I will give more details):
- It's a recursive backtracking method.
- Each node of this backtracking insert one square by trial and error.
- Before each recursive call there is a search and execution of all for "forced square placements". That's when there is a chance to place a square with at least 3 full of it's 4 walls touching something (a boundary or another square placed previously).
No more than 4 non-forced placements are required (only 3 recursive calls). That's because most of the squares are placed forcedly.
As an example, let's take the solution for 41, posted by little joey.
- Square A, or size 23 was placed by first node, as a trial. Note that the first node may also tests for 22, 24, 25, etc...
- Squares B and I are forced placements.
- Square N is placed by the 2nd node of the backtracking. It forces squares E and O.
- Square J is placed in 3rd node.
- Square D is placed in 4th node. Forces all other squares in this order: C, F, G, H, K, L, M.
Note that all non-forced placements (A, N, J and D) did always stick in a corner, touching at least 2 full walls in something.
In a normal backtracking, each node does analyze everything from each branch before analysing another branch. This may be bad, as the searching tree may have very long branches.
To avoid losing time with eventual bad placements, we could limit the depth of backtracking into 4 nodes or change the way it processes the searching tree. Limiting the depthness is simplest method. If we analyzed only 1 node deep, then only 2 nodes deep, then 3, etc, we would need lots of memory to store leaf node calculated. Else, we would have to calculate everything again each time the tree should to got 1 node deeper.
Maybe others are implementing a simillar method. I would be glad if someone could talk about a different method here.
By the way, dieter must have miss-typed 16 instead of 15 for the prime number 41. Else the judge must have been corrected. As an experience, I sent a program that gives solutions with 16 squares for the number for 41 but it got WA.
)