I recently picked up this entertaining puzzle game - fitting 12 pieces into a 11x5 grid. The clearest picture is lower down the page, at Step 3 on the ‘How to play’ tab.
My first question relates to the claim, “There is only one solution per challenge.” While I can see that’s fairly obvious for beginner level puzzles where the majority of pieces are already in place for you, the highest level of challenges only have one piece in place.
So, how could that ‘single solution’ (for when only one piece is given) be proved?
I’ve now played around with a blank grid and found a few ‘unique’ arrangements of my own - not in the main or the bonus downloadable booklet. How many unique arrangements could there be? Likely hundreds… millions? And how would someone go about determining that, mathematically?
Not asking people to actually do that - just wanting to know the thought process and required mathematical tools for the job.
You could try to write a computer program to find all solutions, and check that it outputs a single answer. It would not be a surprise if Knuth’s Algorithm X came into play:
If you know Python and still have Python 2 installed somewhere, the scripts from Polyform Puzzler would would let you enter the pieces you have, the shape of the board, and find the solutions. (To be precise, you’d have to write a whole lot of code, but at least a lot of the hard work would be done for you.)
As it’s a bunch of Python scripts, you can read the code. Sure enough:
Snippet from /puzzler/exact_cover_dlx.py
#!/usr/bin/env python
# $Id: exact_cover_dlx.py 604 2015-03-09 16:03:11Z goodger $
# Author: David Goodger <goodger@python.org>
# Copyright: (C) 1998-2015 by David J. Goodger
# License: GPL 2 (see __init__.py)
"""
An implementation of Donald E. Knuth's 'Algorithm X' [1]_ for the generalized
exact cover problem [2]_ using the 'Dancing Links' technique [3]_ ('DLX').
.. [1] http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
.. [2] http://en.wikipedia.org/wiki/Exact_cover
.. [3] http://en.wikipedia.org/wiki/Dancing_Links
"""
Thanks (and to @DPRK as well) - I needed to look up a short YouTube tutorial on sorting lists using Knuth’s algorithm but I think I’ve grasped the basic concept behind it, where you build up a list of sorted pieces and check for columns where there is only one ‘1’ for each coordinate. A zero or a two would represent where you had overlapped pieces, leaving a gap.
And that puzzler website was very interesting. Looks like for smaller grids of pentominoes the number of solutions gets up into the thousands, and then presumably rises quite steeply as the grids increase in size. So I shouldn’t feel like I’ve been especially lucky in finding solutions ‘from scratch’, or that I’m in danger of duplicating solutions any time soon…
I don’t really have any coding skills to speak of, so I’m unable to write the code to do it, but I like the idea of the process. And nice to appreciate some of the maths behind a puzzle.
I was trying to work out how to use this for the problem, and ran into an issue, but then came up with a solution.
To make things more concrete, suppose you have 4 pieces and a 9+4+1=14-ball pyramid. To start, you might create a 14-wide matrix, where each row corresponds to a piece in some orientation. For instance, a 3-long linear piece would have 3 rows where it is flat on the base and pointing one way, 3 more rotated 90 degrees, and then 4 where it’s oriented along the pyramid’s edges. And for each row, there are 3 ones in the spots where the balls are positioned.
But this has the problem of allowing Algorithm X to play a piece multiple times, which isn’t allowed. To cover the base fully, it could just pick 3 rows for the same piece.
The answer is to add a few more columns: one for each piece. Then, each piece gets an index and has a 1 in that column for every row corresponding to that piece. Algorithm X then can’t pick more than one row for a given piece since that column would be covered more than once. Nor can it leave a gap.
So there are two cover problems that have to be solved simultaneously: every ball position is covered by one and only one ball, and every piece is used once and only once. But Algorithm X makes that easy since you can just paste the matrices side-by-side.
Yes, that’s the usual way to implement a tiling solver using Algorithm X. It’s described in the “Pentomino tiling” section of the Wikipedia article on the Exact Cover problem. I wrote a tiling solver program a few years ago using the technique and it works very well.
It’s good to see that the solution I came up with while taking a dump this morning is also the canonical solution. And no, I didn’t work it out with a pencil.
