10
$\begingroup$

The following Pentomino board has exactly one solution:

enter image description here

The solution is known:

Z Z W Y Y Y Y - F L L L L
V Z W W Y N N - F F F X L
V Z Z W W T N N N F X X X
V V V T T T - P P P U X U
I I I I I T - - P P U U U

I'm trying to solve this board manually, but it is so difficult that I came to believe it is impossible.

I noticed there must be five pieces in the right side, either in a 5x5 shape or in this similar shape with a small 'dent':

.#####
.#####
xx####
######
.#####

(xx denote a piece from the left side)

How would more experienced puzzlers go about this?

$\endgroup$
4
  • 1
    $\begingroup$ What are the rules the puzzle follows? Do we put in all twelve unique pentominoes, or can there be repeats? If this board weren't exactly sixty cells, I'd assume the rules were traditional. $\endgroup$
    – DontMindMe
    May 15 at 19:07
  • 2
    $\begingroup$ @JosephParkes Each of the 12 unique pieces must be used exactly once. All 60 open cells must be filled without overlaps. I do not know which other rulesets there are - does this answer your question? $\endgroup$
    – mafu
    May 16 at 2:46
  • $\begingroup$ I'd guess the only other question would be whether rotated or flipped versions of the same tile would count as different - and the answer apparently is that they wouldn't, but it helps to clarify that up front. $\endgroup$ May 16 at 16:12
  • $\begingroup$ Yes, that answers my question. I was thinking of Pentominous puzzles $\endgroup$
    – DontMindMe
    May 16 at 19:47

1 Answer 1

9
$\begingroup$

How would more experienced puzzlers go about this?

We - or at least I - would use a solving program.

I think you're right: there's likely no "nice" human-understandable path to solving this. The board is a 5×13 grid with 5 cells removed, which is very regular. That would make me suspect that the puzzle was computer-generated, even if you hadn't included what appears to be code output in your screenshot. And more importantly, there's no reason to assume there would be a "nice" solution. Packing puzzles are hard - if they weren't designed with a particular logical path in mind, it's very unlikely that they have one at all.

I agree with your deduction about the cells taken up by the five rightmost pentominoes, but that's the only real in-road. If we take "there is exactly one way to do this" as a given, we can rule out the 5×5 grid (because if there was a solution involving it, we could rotate only that grid to produce a different solution). But then there's nothing else you can do.


So, brute force is likely the only option. But I imagine you're looking for something better than "use a computer". If I was, say, locked in a room with only pencil and paper until I solved this by hand, and told that there is exactly one solution, here's what I'd do:

  • Use the logic above to show that the "dented" shape must be correct.
  • Calculate 12 choose 5, and get 792.
  • Enumerate all 792 5-subsets of the pentominoes.
  • Try filling the dented square with each 5-subset; cross out all the ones that don't work. (If I'm unsure of whether I've missed anything, I can pick a certain square to branch on - look at all pieces that can fill that square, and then try out each individual case there.)
  • When I can successfully fill the dented-square with a 5-subset, attempt to pack the remaining pieces into the left side of the board. It would likely be easiest to bruteforce by branching first on whatever goes into the dent (which must be one of LINVY), and then I'd probably pick a nearby square to further branch on if necessary.

It would still be a slow, laborious process... but it would at least be guaranteed to end eventually.

$\endgroup$
5
  • $\begingroup$ It is indeed computer generated. Thank you for the paper, I was looking for this one! $\endgroup$
    – mafu
    May 16 at 3:07
  • 3
    $\begingroup$ Guaranteed is such a strong word.. (The piece that goes in the dent isn't any of LIVY.) :-) $\endgroup$
    – Bass
    May 16 at 3:48
  • $\begingroup$ One more general technique that is often helpful for these kinds of puzzles but probably doesn't do much here: chess board coloring. Apply a chess board coloring to the finished shape and to all the individual pieces. This can give you constraints that some pieces can or cannot lie in certain positions because the total number of black and white squares doesn't add up otherwise. Unfortunately for pentominos 11 pieces have a 2/3 black/white distribution and only the cross has 4/1 so you probably don't get very much out of this method here. $\endgroup$
    – quarague
    May 16 at 7:30
  • $\begingroup$ There are 1332 ways to fill the left part of the board, and 114 ways to fill the right hand side. And when you split off the RHS as a 5x5 square, then there are 1962 and 856 ways. I think it is quite remarkable that there is only one combination possible for the board as a whole. $\endgroup$ May 16 at 9:48
  • 1
    $\begingroup$ "Packing puzzles are hard" [Citation Needed] $\endgroup$ May 16 at 17:07

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.