This problem is representative of a class of problems that I can solve – but only thought brute force. In some cases – like this one – I can winnow my guessing spaces though the use of logic and algebra – but it is still a brute force attack. What I don’t see is how to make a non-brute force algorithmic attack on this problem.
This problem was phrased with five rectangles tiled to cover a square – with a much larger number of squares I could not easily do it by hand and if I was to write a program to do it that attack would also be brute force.
Ugly as it is – here is how I solved this problem.
I just looked at the Mathproblems.info site where I saw this problem and they show three more solutions. One more with side length of 13 and two more with side length of 11. I was less thorough with my search of the 11 options and stopped on 13 after I found the first solution but the techniques seem to be the same for all solutions. Still brute force-ish though. There must be a better way to formalize solving this type of problem.
One reply on “Find five rectangles that tile a square”
Talking to Konrad this morning this is apparently a linear constraint optimization problem – which for integers is NP complete. So if I am understanding this correctly a certain about of brute force is unavoidable.