11

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.

Solution

solution to 10x10 puzzle

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).

Pontus von Brömssen
  • 213
  • 4

2 Answers2

8

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:

enter image description here

11:

enter image description here

12:

enter image description here

RobPratt
  • 13,685
  • 1
  • 29
  • 56
3

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

For square 10:

18 distinct solutions
enter image description here

For square 11:

5 distinct solutions
enter image description here

For square 12:

2 distinct solutions
enter image description here

Solved in under a second by automated tile placing.

Weather Vane
  • 14,420
  • 1
  • 22
  • 54
  • Neat. What does "by automated tile placing", recursive backtracking or which algorithm? Which language and library, or did you code it yourself? – smci Dec 30 '23 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 :) – Weather Vane Dec 30 '23 at 23:57
  • I ran these through my aging solver program, it agrees with all your counts – theonetruepath Dec 31 '23 at 01:55