Fortran to solve square packing problem/ Mrs. Perkin's quilt

[babakk]

Hi this is my first time posting on this forum, mainly because I am new to Fortran.

I have to do a project based on a problem called Mrs. Perkin's Quilt. I posted a link at the end for further info in case of any confusion. The basic idea is to take an nxn square and dissect it into smaller squares. These dissections must be prime, which I take to mean that there must be at least a single one by one square used. All the surface area of the square must be covered, and the goal is to do this using the least amount of squares. That link also has a nice visual, which one would understand the general thing I am trying to program.

I know most of the basics to programming, and I was wondering if anyone can help me step in the right direction as to how to approach programming a program that can solve this. The program doesn't need to find the exact solution, but a good solution. My goal is to get the least solution for n=1-15 and for n> 15 a decent solution would be optimal. I am unsure how I can create an algorithm using fortran to place squares within the main square and what not.

I figure that the user would input n for the initial square size. Then the program would start with the biggest possible square that is n-1, and find a solution for that (solution being the number of squares used). Then it would do this starting with a block n-2, and it would continue as such then compare the amounts used and determine which one was minimum. Then it would output the least # of squares used and maybe possibly i can draw this solution in PGplot but that would be done after I get the basics first. Could anyone please give me some advice,

Thanks

here is the link

http://mathworld.wolfram.com/MrsPerkinssQuilt.html

 

[xwb]

Had a look at the site - and solutions. Can't quite work out the rules for it. The thing with problems like these is working out the rules first. Once you have figured out the rules, you can start on the algorithm for the solution.

Something like Sudoku, the rules are easy. The algorithm is just a depth first search. Coding in any language is purely mechanical.

Somthing like Mrs Perkins Quilt, the rules are not clear. They talk about prime disections but it is not clear what a prime dissection is. The examples have 4 squares; not even a prime number. If you can figure out what the rules are, could you post them.

 

[babakk]

Yeah that is true, I am unsure of the rule to it as well. But the rules I want to program for are the following:

1)Only squares can be used to break down the main square.

3)The solution should be done using a minimum number of squares.

2)The solution must contain at least one 1x1 square. For example, as in the picture for n=4, the solution contains 3 2x2 squares and 4 1x1 squares. That 4 1x1 squares could have been another 2x2 square and that would have been a minimum solution, but the requirement for at least one 1x1 square made it so that the 4th 2x2 had to be broken down.

So what I think it means for prime dissection is that there cannot be a solution that is symmetric, not so much related to prime numbers. Also, one way I was considering doing this is representing the squares as arrays (matrices), such as for a 4x4 square have a 4 by 4 matrix with all entries are 1.

Thanks for the reply.

 

[babakk]

Well I figured out a working algorithm and programmed it sufficiently well. It can calculate the solutions of n=1-6 exactly. n > 6 the calculated solution is off by 1 compared to the known until n = 17. From N= 17- 400 it ranges from 2 to 3 off the known best solution. I represented the squares using arrays. I only need to be able to draw the pictorial solution now on pgplot.

 

[xwb]

Why not just draw it using +, - and |. Something like

+---+---+
|   |   |
+---+---+
|   |   |
+---+---+

Alternatively use the line drawing characters. It may be a lot easier than using pgplot.

 

[babakk]

Yeah that is true I can try that. I am going to work on it today and see how I can integrate the drawing scheme into my program. I think pgplot might be easy too though, they have built in subroutines to draw rectangles using coordinates. And those coordinates I can extract from my matrices. But I will try your method as well.

The reason is related to how I represented the squares: For an n=4 square for example. I used the following matrix :
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

then say i wanted to put in a 2x2 square into the 4x4, i would subtract
1 1 0 0 0 0 0 0
1 1 0 0 or 0 0 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1

so it might be easy to pull out coordinates from the matrices since i am only working with squares. I'd just need to know the location of the first one and the size of the square to get the other 3 coordinates.

 

[xwb]

It would probably be easier if you set the squares to different numbers

A 2x2 would be
1 2
3 4

A 3x3 would be
1 1 2
1 1 3
4 5 6

A 4x4 would be
1 1 2 2
1 1 2 2
3 3 4 5
3 3 6 7

Then you can pull the coordinates of any square.

 

[babakk]

Thanks for your help, I managed to complete the code. It works sufficiently well. I ended up using PGplot because it looks nicer lol and I used squares with only 1's. If you ever want to see the code I wrote, which is actually very long even though I used recursive subroutines I can show you.

Thanks again.

 

[xwb]

Well done - just interested in what rules you used. Once you've worked out the rules, the program is just mechanical.

 

[babakk]

The rules I used, and which I believe to be exactly what Mrs. Perkins's Quilt problems are governed upon are:

1) All dissections must be squares, and cannot just be themselves.

2) Only prime dissections are allowed

NOTE* I figured out that prime dissection means that all the pieces cannot have a common factor other than 1. To elaborate, if the 4x4 square is broken into 4 2x2 squares, since all the pieces contain a common factor of 2. Thus one of the squares has to be broken further into 4 1x1 squares so that the common factor is now only 1.

3) The solution is the minimum number of squares used to accomplish the above two rules.

Those are the three rules, my program can only approximate the solution. Meaning that it does not get the exact minimum solution for every size only select ones.

 

[xwb]

Thanks - I'll give it a try sometime.