# Fit small squares in a large square

Fit the given square pieces in a larger square!

### Warmup

In a 10x10 square, fit 5 1x1 squares, 8 2x2 squares, and 7 3x3 squares.

### Puzzles

1. In an 11x11 square, fit 3 1x1 squares, 12 2x2 squares, 5 3x3 squares, and 1 5x5 square.
2. In a 12x12 square, fit 2 1x1 squares, 10 2x2 squares, 5 3x3 squares, 2 4x4 squares, and 1 5x5 square.

### Notes

For each size of the large square, the set of square pieces has been selected to make the puzzle as hard as possible in a certain sense. I let the computer go through all sets of square pieces that can tile the large square and pick the hardest set. The measure of hardness is given by a simple rule and of course it does not agree with the perceived difficulty. I found the 10x10 puzzle easy but the 11x11 and 12x12 puzzles rather tricky (without computer assistance, of course).

• Maybe add a no-computers tag? Commented Dec 29, 2023 at 15:05
• @JaapScherphuis I think computers can be allowed for those who prefer that. A descent program will quickly find the solutions, but you still have to code it up. Commented Dec 29, 2023 at 16:05

I found solutions via integer linear programming, with a binary decision variable for each tile, a partitioning constraint for each cell, and a cardinality constraint for each size.

10:

11:

12:

A bit late to the party, but I have found:

For square 10:

18 distinct solutions

For square 11:

5 distinct solutions

For square 12:

2 distinct solutions

Solved in under a second by automated tile placing.

• Neat. What does "by automated tile placing", recursive backtracking or which algorithm? Which language and library, or did you code it yourself?
– smci
Commented Dec 30, 2023 at 23:42
• @smci I only used standard C libraries, apart from converting my .bmp files to .png for publication. So as Pontus wrote above "you still have to code it up". I needed to tackle the problem twice though – my first attempt would not have solved the 12 this year. And "under a second" obviously doesn't include all that :) Commented Dec 30, 2023 at 23:57
• I ran these through my aging solver program, it agrees with all your counts Commented Dec 31, 2023 at 1:55