14
$\begingroup$

Rules

  1. Place some pentominoes into an 8 x 8 grid. They do not touch each other. They can touch only diagonally (with corner).
  2. Pentominoes cannot repeat in the grid. Rotations and reflections of a pentomino are considered the same shape.
  3. Grid is 8 x 8.
$\endgroup$
3
  • $\begingroup$ Please clarify: 'diagonally (with edge).' 'Diagonally' usually means with a corner / vertex but not an edge / side $\endgroup$
    – CiaPan
    Apr 18 at 6:25
  • $\begingroup$ Correct word is corner. I thought that edge is synonymum for corner. Proper solution is in Rand al'Thor example. $\endgroup$
    – Ignac
    Apr 18 at 7:05
  • $\begingroup$ You can (and should) edit your question to clear up the confusion. $\endgroup$
    – No Name
    Apr 19 at 2:49

3 Answers 3

21
$\begingroup$

With integer programming, I managed to place

8 pieces, proved to be optimal

like this.

$$\begin{array}{cccccccc} 3&3&3&3& &5&5&5\\ 3& & & & &5& &5\\ &4&4&4&4& &A&\\ 6& & &4& &A&A&A\\ 6&6&6& &8& &A&\\ & &6& &8&8& &B\\ 2&2& &8&8& &B&B\\2&2&2& & &B&B&\\ \end{array}$$

Here is my formulation. I happened to solve a similar model to solve a puzzle called One puzzle a day. Let $B$ be the set of cells in the 8x8 board, and $P$ be the set of all kinds of pieces (rotating and flipping count difference here), so I have $|P|=63$, then we need to choose a subset of $P$ and place them only by translation. Let binary variable $x_{pb}$ indicate whether the piece $p$ is placed on the cell $b$ (some predefined reference point on the piece being on $b$). Let the set $P_i\subset P$ represent all flipped and rotated version of a same pentomino, and binary variable $y_i$ indicates whether the pentomino $i$ is placed on the board, so we have $$ y_i = \sum_{p\in P_i} \sum_{b\in B} x_{pb} $$ and the objective is to maximize $\sum_i y_i$.

Putting the reference point on some cells make the tile out of the board, let that set be $F_p$, we have $$ x_{pb} = 0 \quad\forall b \in F_p. $$

Now the main part. Actually in every cell $b$, we could find all possible $(p,b')$ that will cover the cell $b$, say the set is $Covered(b)$. By constraining $\sum_{Covered(b)} x_{pb'} \leq 1$, we could prevent overlap. To prevent neighboring, I build sets $Edge(b) = \{(p, b')\}$ similarly, which means if putting $p$ in $b'$, the cell $b$ will be on the edge of that piece. Then we need some constraints like $$ \alpha \sum_{(p,b')\in Covered(b)} x_{pb'} + \beta \sum_{(p,b') \in Edge(b)} x_{pb'} \leq \delta $$

The parameters $\alpha, \beta, \delta >0$should satisfy that $\alpha \leq \delta$, $4\beta \leq \delta$, $\alpha + \beta > \delta$, $2\alpha > \delta$, meaning that "one cover is allowed", "four edges on the same cell is allowed", "one cover and one edge is not allowed" (that is when two pieces are next to each other) and "no overlap". I chose $\alpha=\delta=1, \beta=0.25$ (actually any $\beta > 0$ works...).

That is all constraints we need.

$\endgroup$
7
  • 2
    $\begingroup$ I was getting very close to this with pencil and paper: image $\endgroup$ Apr 17 at 13:22
  • 2
    $\begingroup$ Nice one. Just curious, why did you use 2, 3, 4, 5, 6, 8, A, B as the pieces names? $\endgroup$
    – justhalf
    Apr 17 at 14:50
  • 2
    $\begingroup$ @justhalf It's just based on the order of the pentominoes list in my code, which is basically random... the 0, 1, 7, 9 are the skipped shapes. I could have made it better. $\endgroup$
    – xd y
    Apr 17 at 14:56
  • 2
    $\begingroup$ I chucked this into my solver and it found only five tilings with 8 pentominos. Did you count flips twice, or do I need to look for a bug? $\endgroup$ Apr 18 at 2:12
  • 1
    $\begingroup$ @BlueRaja-DannyPflughoeft It is proved by the mip (mixed integer programming) solver, which is based on branch and bound algorithm. The algorithm guarentees global optimality. $\endgroup$
    – xd y
    Apr 18 at 5:00
19
$\begingroup$

I solved this completely by hand.

solution with 8 pentominos

Here is a clean proof of its optimality. No computer is needed. Mere pencil and paper suffice.

Expand each pentomino by adding little right-angled isosceles triangles with area 1/4 as follows:

  1. For each (unit) cell with edge $A$ along its perimeter, add a little triangle with hypotenuse $A$ beside that cell.
  2. For each pair of adjacent cells with adjacent edges $A,B$ along its perimeter, add a little triangle beside both the triangles that had been added beside those cells at $A,B$.
  3. For the V-pentomino, add 2 more little triangles to completely fill in the region between the two arms of the "V".

Here is an example (with added triangles yellow in step 1 and green in step 2):

F-pentomino with 12 triangles added in step 1 and 2 triangles added in step 2

Observe that the number of little triangles added is at least the perimeter, regardless of the pentomino. The perimeter is at least 12 except for the P-pentomino, but the P-pentomino has 4 little triangles added in step 2. Except the X-pentomino, every other pentomino has at least 2 little triangles added in step 2. Thus the expanded X-pentomino has area $5+12/4 = 8$, and the expanded P,F,W-pentominos have area $5+14/4 = 8.5$, and every other pentomino has area at least $5+16/4 = 9$.

It is easy to see that, for any solution to the puzzle, the expanded pentominos will still not overlap. So if there are 9 distinct pentominos, then their total area is at least $8 + 8.5×3 + 9×5 = 78.5$.

Now expand the 8×8 board as well in the same manner, which adds 15 little triangles to each side. The expanded board has area $8×8 + 15 = 79$, but at least one of the added triangles next to each side of the board will not be covered, so the actual covered area is at most 78. Hence 9 distinct pentominos cannot fit.


In fact, we can show that 9 pentominos cannot fit even if each pentomino can be used 4 times! To see why, observe that each pentomino can only cover 6 units of the board perimeter, after which there is a gap of at least 1 unit before the next pentomino along the board perimeter. Let T be the expanded board area. Due to the gaps, not all of T can be covered by the pentominos. First, each isolated gap 'reduces' T by 1 unit. Two adjacent gaps 'reduces' T by at least 1.5 units (attained at the board corner). In general, $(k+1)$ adjacent gaps 'reduces' T by at least $(k+1)/2$ units. Thus the average reduction is at least 1/7 per board perimeter. Thus the gaps 'reduces' T by at least $\lceil32×1/7\rceil = 5$, so the covered expanded board area is at most $8×8 + 15 − 5 = 74$. But 9 pentominos (even with quadrupled pentominos) would have total area at least $8×4 + 8.5×5 = 74.5$. I presume that these bounds can be improved to show that 9 pentominos regardless of how many repeats cannot fit, but I did not bother to squeeze this last bit.


An equivalent counting method is to count the cell edges instead of area. Each pentomino already has 15 or 16 cell edges, and between each pair of adjacent cells along its perimeter we can add 1/2 edge sticking out, because that goes at most halfway to any other pentomino. In total we would get at least 17 edges per pentomino except 16 for the X-pentomino, which corresponds to 8.5 area for each pentomino except 8 for the X-pentomino.

The slight advantage of this counting is that it is easier to see where we are making losses. For instance, every untouched corner incurs a loss of at least 1 edge (i.e. 1/2×2), and this applies at the boundary as well, so we automatically know that we want to minimize the number of untouched corners. Also, every empty 2×2 square in the board incurs a loss of at least 2 edges, twice as bad as an untouched corner.

I initially did not mention this approach because the area equivalent is a bit easier to understand. However, I have decided to add it in, because it is much easier to write a program that uses this for a branch-and-bound search that counts the total edges plus the (necessary) losses so far. This makes it easy to prune most branches of the search. We even get a reasonable heuristic for branch-ordering, namely to first try placing the next pentomino to minimize the total edges+loss so far.

$\endgroup$
2
  • 1
    $\begingroup$ "Observe that the number of little triangles added is at least the perimeter plus 2, regardless of the pentamino." - I'm trying to understand how this applies for the X pentomino. Does that not just have one triangle for each side on the perimeter? If I've understood your point 2 correctly I don't think it adds any more triangles onto this (though I'll admit I didn't really understand the wording, am just guessing what it means from the example). $\endgroup$
    – Chris
    Apr 19 at 9:36
  • 1
    $\begingroup$ @Chris: Whoops, I miscounted the X. So we're going to have to count at least one gap along the perimeter to make the inequality still work. I'll fix it, thanks. $\endgroup$
    – user21820
    Apr 19 at 10:00
5
$\begingroup$

I can manage

seven pentominoes, in a few different ways:

seven pentominoes seven again

There is an obvious upper bound of

twelve (the total number of distinct pentominoes, and $12\times5$ is still less than the number of squares on the board),

but this is nowhere near achievable given the restriction that pentominoes are not allowed to touch each other orthogonally. This means that

every placed pentomino creates at least 4 squares around it that no other pentomino can occupy. At least 4, in the best possible scenario where the pentomino is placed in a corner - usually more. (I think 4 is only achievable with the P-pentomino in the corner and 5 is only achievable with the symmetric L-pentomino in the corner, otherwise it's more.)

Because of this, I'm pretty sure the number I managed above is optimal and it's not possible to place more.

$\endgroup$
6
  • $\begingroup$ So apparently 8 is possible. But great work (manual, I suppose)! $\endgroup$
    – justhalf
    Apr 17 at 14:51
  • 1
    $\begingroup$ @justhalf Manual in the sense that I didn't use any programming like the other answerer, yes. I did use this site just in lieu of actual pentominoes or pencil and paper. $\endgroup$ Apr 17 at 15:06
  • 1
    $\begingroup$ I guess your intuition fails you at the end because perhaps you forgot to include the fact that the free space can overlap. $\endgroup$
    – justhalf
    Apr 17 at 15:52
  • 1
    $\begingroup$ @justhalf I realised it can overlap (otherwise even 7 wouldn't be possible), but as a rough estimation I guessed the overlap wouldn't be sufficient to allow 8. $\endgroup$ Apr 17 at 15:53
  • $\begingroup$ "every placed pentomino creates at least 5 squares around it that no other pentomino can occupy [...] in the best possible scenario where the pentomino is placed in a corner" — The best-best scenario is the P-pentomino in the corner, which borders only 4 other squares. (The pentominoes all have area 5, but various different perimeters. The worst case is the I-pentomino in the middle of the board, with perimeter 12.) $\endgroup$ Apr 18 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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