10270 - Bigger Square Please...

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Solving method.

Post by Algoritmo »

About 5 months ago I quit with this problem because I got lost in my code. I wished to make a fast program, that possibly wouldn't need "offline pre-calculation".
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 :P

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.
I solve 4 problems per day, then I expend 4 days stuck in a single problem. But I think I'm doing well... ID 37180

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

I also used this 'Forced Square Heuristic' (well only for the upper right and the lower left squares), but I'm not convinced that it will always lead to an optimal solution. I think it can be proven for the upper right square, but for the lower left square consider this optimal solution for N=19:

Code: Select all

AAAAAAAAAABBBBBBBBB
AAAAAAAAAABBBBBBBBB
AAAAAAAAAABBBBBBBBB
AAAAAAAAAABBBBBBBBB
AAAAAAAAAABBBBBBBBB
AAAAAAAAAABBBBBBBBB
AAAAAAAAAABBBBBBBBB
AAAAAAAAAABBBBBBBBB
AAAAAAAAAABBBBBBBBB
AAAAAAAAAACDDDEEEEE
FFFGGGHHHHHDDDEEEEE
FFFGGGHHHHHDDDEEEEE
FFFGGGHHHHHIIIEEEEE
JJJJJJHHHHHIIIEEEEE
JJJJJJHHHHHIIIKKKKK
JJJJJJLLLLMMMMKKKKK
JJJJJJLLLLMMMMKKKKK
JJJJJJLLLLMMMMKKKKK
JJJJJJLLLLMMMMKKKKK
It doesn't even have a second 9x9 square.

I think you can not rule out that there are big prime numbers for which the 'Forced Square Heuristic' leads to sub-optimal solutions (although it might take forever to find a counter-example).

Dizzle
New poster
Posts: 1
Joined: Mon Jun 11, 2007 8:15 am

Post by Dizzle »

This apparently doesn't seem to be a much discussed topic. However, I find it to be one of the more interesting problems, and would like to know how other people on this board have gone about finishing this problem.

The only way I have been able to solve this problem is through backtacking, like the other posters in this thread have done. I would like to know if anyone has any other methods that might help make the backtracking a lot faster, because it can be very slow with prime squares larger than 31, and to me there should be some way to make this faster( or maybe I'm just asking too much of myself :) )
Last edited by Dizzle on Mon Dec 08, 2008 5:08 am, edited 1 time in total.

evandrix
New poster
Posts: 8
Joined: Wed Oct 03, 2007 11:07 am

Re: 10270 - Bigger Squares Please

Post by evandrix »

How'd you achieve 16 squares solution for N=47? i only managed 17 squares...
g47.gif

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: 10270 - Bigger Squares Please

Post by DJWS »


poixp
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

Re: 10270 - Bigger Squares Please

Post by poixp »

Hello to everyone!
I'm just solved this problem and want to share some hints.
First of all I use exhausting search with several pruning techniques. My program needs about 15 minutes on my old AMD 2600+ computer to pre-calculate solutions for squares 2..50.
There what I use:
0. You need to generate cases only when N is prime number.
1. I consider that square with biggest width is on top left corner. It helps not to think about symmetry.
2. I assume that biggest square has width N/2 .. N-1
3. I use heuristic that square in top right and bottom left squares have width = N - width of biggest square
4. I assume that in one square there are no more then 5 tile squares with equal width
5. I assume that there is at least one tile square has width = 1
And solution for N = 47:

Code: Select all

AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCC
AAAAAAAAAAAAAAAAAAAAAAAADDEFFFFFFGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBHDDIFFFFFFGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBJJJJFFFFFFGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBJJJJFFFFFFGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBJJJJFFFFFFGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBJJJJFFFFFFGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKGGGGGGGGGGGGGG
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKLLLLMMMMMMMMMM
BBBBBBBBBBBBBBBBBBBBBBBKKKKKKKKKKLLLLMMMMMMMMMM
BBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNOOLLLLMMMMMMMMMM
BBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNOOLLLLMMMMMMMMMM
BBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNPPPPPPMMMMMMMMMM
BBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNPPPPPPMMMMMMMMMM
BBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNPPPPPPMMMMMMMMMM
BBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNPPPPPPMMMMMMMMMM
BBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNPPPPPPMMMMMMMMMM
BBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNPPPPPPMMMMMMMMMM

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Re: 10270 - Bigger Squares Please

Post by CMG »

Hi poixp,

You did a good job with the techniques you supplied. I have enjoyed this problem for quite some time and my solving program uses most all of those to find minimal solutions. My tip is to remove #5 in your list as there are minimal solutions that don't use a square of size 1, which are 19,31,37,43,47.

I do use the limit of 5 squares as well, although I have found it doesn't do much to improve time until you get to 47. If you want to mess around with the program more, you should be able to make it a good amount faster. Using just the techniques you listed except for #5 my java program takes

29 in 0.25 sec
31 in 1.11 sec
37 in 4.48 sec
41 in 9.62 sec
43 in 38.59 sec
47 in 72.37 sec
53 in 220.75 sec

to solve those individually on my old amd 2800+. The place that made the biggest improvement was the ability to remove the O(n^2) on placing and removing squares to make it O(n). I was able to do this since the way I place squares goes from top left to right and then continues down, I only needed to fill in/remove a linear row on the left most side of the placed/removed square instead of filling in/removing all of the square.
Last edited by CMG on Thu Dec 11, 2008 3:17 am, edited 5 times in total.

evandrix
New poster
Posts: 8
Joined: Wed Oct 03, 2007 11:07 am

Re: 10270 - Bigger Squares Please

Post by evandrix »

interesting...the last 2 posts...i've actually solved it myself as well, in a really much more inefficient way [coded in c++], would you mind to post your solutions so i can take a look at how these steps you listed are all implemented?

cheers

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Re: 10270 - Bigger Squares Please

Post by CMG »

This is my java code without my GUI stuff with it to view the squares once completed.

Code: Select all

    public BSP(int squareSize) {
        this.squareSize = squareSize;
        squareGrid = new int[squareSize*squareSize];
        amounts = new int[squareSize];
        solution = new int[squareGrid.length];
        calcDist = new int[squareGrid.length];
        for(int i=squareSize,k=0;i>0;i--) {
            for(int j=squareSize;j>0;j--,k++) {
                calcDist[k] = j<i?j:i;
            }
        }
        bestCount = squareGrid.length;
        getBiggerSquarePlease();
    }
    
    //Finds the minimal solution for a square of a size 'squareSize'
    //Starts by placing the 3 main squares each loop through.
    private void getBiggerSquarePlease() {
        for(int i=(squareSize>>1)+(squareSize&1);i<squareSize;i++) { // i = N/2 + (1 if N is odd)
            placeSquare(i,0); //Top Left
            placeSquare(squareSize-i,i); //Top Right
            placeSquare(squareSize-i,i*squareSize); //Bottom Left
            tile(squareSize*(squareSize-i)+i,3); //Place The Rest
            placeSquare(squareSize-i,i*squareSize); //Remove
            placeSquare(squareSize-i,i);
            placeSquare(i,0);
        }
    }
    
    //Places or removes a square in 'squareGrid' starting at 'point' which is at the top left corner of the square
    //Works in O(N) since it starts at 'point' and works down in only one column
    private void placeSquare(int size,int point) {
        if(squareGrid[point]==0) {
            amounts[size]++;
        } else {
           amounts[size]--;
        }
        for(int i=size;i>0;i--,point+=squareSize) {
            squareGrid[point] ^= size;  //Xor's 'size' into 'squareGrid', causing it to place
        }                               //a square when 'squareGrid[point]' = 0 and remove when 'squareGrid[point]' = 'size'.
    }
    
    //Place the rest of the squares.
    //Point = top left corner of square looking to be placed.
    //Count = current amount of squares that have been placed.
    private void tile(int point,int count) {
        int c1 = count+1; //temp vars to save a few operations
        int c2 = c1+1;
        //Start from maximum allowed square size at this 'point' and work down in size.
        for(int i=getMax(point);i>0;i--) {
            //Don't allow more than 5 squares of same size to be placed.
            if(amounts[i]<5) {
                placeSquare(i,point);
                //Find the next available point to place a square.
                int next = getPoint(point);
                if(next>=squareGrid.length) {//We completed placing all squares. We have a solution, but may not be minimal.
                    bestCount = c1; //Save the current amount of placed squares in bestCount.
                    //Save new solution
                    for(int j=squareGrid.length-1;j>=0;j--) {
                        solution[j] = squareGrid[j];
                    }
                    placeSquare(i,point);
                    return;
                } else if(c2<bestCount) {
                    //Not done placing squares.
                    tile(next,c1);
                } else {
                    placeSquare(i,point);
                    return;
                }
                placeSquare(i,point);
            }
        }
    }
    
    //Find the maximum square size at this 'point'
    private int getMax(int point) {
        int max = calcDist[point]+point;//Max distance horizontally or vertically, and Offset to make loop faster.
        for(int i=point;i<max;i++) {
            if(squareGrid[i]!=0) {
                return(i-point);
            }
        }
        return(max-point);
    }
    
    //Find the next available 'point' to place a square.
    private int getPoint(int point) {
        while(point<squareGrid.length && squareGrid[point]!=0) {
            point += squareGrid[point];
        }
        return(point);
    }
The attached rar contains all possible solutions for squares of size 2-47 prime. By all possible I mean a unique list of the squares used to make up the bigger square, since you could have thousands of solutions if you counted all the possible translations of each of the solutions I put in the attachment. The square of size 31 is quite interesting with 48 unique solutions. The solutions also don't force the 2 squares in the top right and bottom left corners like the fast program above does.

The images in the rar are named 'squareSize-minimalCount-solution#'.png
Attachments
BSP.rar
(230.9 KiB) Downloaded 274 times
Last edited by CMG on Thu Dec 11, 2008 3:11 am, edited 2 times in total.

poixp
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

Re: 10270 - Bigger Squares Please

Post by poixp »

Thanx for CMG, for replies. It's actually isn't good heuristic to assume that there is at least one square with width 1.
I also thought about squares placing algorithm optimization, but for n <= 50 I decided that It's not worth it ... But the results you have posted really amazing ...
To evandrix - I'll PM my solution to you ...

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Re: 10270 - Bigger Squares Please

Post by CMG »

Amazingly I found a couple places of improvement in my code above that resulted in about a 45% faster program. I updated the code in my post above, I edited 'tile' slightly by adding an extra else statement, and I also edited 'getMax' slightly by precalculating the startup maxvalue at the current point. The new times are:

29 in 0.25 sec
31 in 0.75 sec
37 in 2.48 sec
41 in 5.86 sec
43 in 21.85 sec
47 in 40.55 sec
53 in 136.42 sec

I also went ahead and updated the attachment in my post above to include solutions for 41, 43, and 47.

Post Reply

Return to “Volume 102 (10200-10299)”