11
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Maybe add a no-computers tag? $\endgroup$ Commented Dec 29, 2023 at 15:05
  • 3
    $\begingroup$ @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. $\endgroup$ Commented Dec 29, 2023 at 16:05

2 Answers 2

8
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Neat. What does "by automated tile placing", recursive backtracking or which algorithm? Which language and library, or did you code it yourself? $\endgroup$
    – smci
    Commented Dec 30, 2023 at 23:42
  • $\begingroup$ @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 :) $\endgroup$ Commented Dec 30, 2023 at 23:57
  • $\begingroup$ I ran these through my aging solver program, it agrees with all your counts $\endgroup$ Commented Dec 31, 2023 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.