Sliding Block Puzzles, Part 4 of 3

And you thought it was over! 1 2 3

I was originally planning to finish the series of articles on SBPs at this post, concluding with the announcement of the optimal puzzles for a 4×4 grid. Partially, this was because the SBPFinder algorithm would have taken prohibitive amounts of time to compute the boards for any larger size. For example, for the classic 4×5 grid, it would take somewhere around 128 days! A much worse problem is that it would have used approximately 64 GB of RAM, which, even at its cheapest, is an investment I cannot reasonably justify.

Fortunately, however, I soon realized how utterly stupid I had been when designing the SBPFinder algorithm. In case the reader doesn’t want to read the thousands of words in the previous posts, I’ll quickly describe it: Essentially, the algorithm used dynamic programming and a peculiar way of indexing into a 2D array to, cell by cell, generate all possible positions. The primary flaw with this technique is that it generates lots of duplicates, which both slows it down and requires the use of a hash set or other method of eliminating duplicate positions. (To go into the technical details, this is because certain oddly shaped pieces, which -not coincidentally- appear in the list of hardest simple^3 SBPs, cause the dynamic programming stage to consider too many branches of the tree. This, in turn, is because the computer cannot currently time travel and see what it does before it does it)

    The solution is to place entire pieces (or voids) in undecided spaces, proceeding left-to-right and top-to-bottom. Currently, this has been implemented as a recursive function, as follows:

Given a board B (which may be partially filled):

  1. Find the first cell which has not been decided yet- that is, does not contain a cell of a piece or a void, but rather exists in a state of indecision between the two. (This is implemented as a third cell type)
  2. If there are no undecided cells, the board is a valid placement of pieces and voids. (It may not be justsolved, though, so these are typically placed in a file to be processed further)
  3. Otherwise,
    1. Recurse to the case where that cell is filled with a void,
    2. Find all pieces which can be placed on the board and which cover only undecided cells and which covers the cell determined in step 1.
    3. For each of those pieces, recurse to the case where that piece is placed on the board.

Here’s the search tree for 2×2 SBPs using this method:

Click to enlarge; the search tree is really wide

Click to enlarge; the search tree is really wide. Also, the post continues after the break.

This approach fixes basically all of the problems with the previous algorithm: it doesn’t duplicate positions (the nth piece will always have label n), it uses little memory (once each board has been generated, it can immediately be written out to a file), and it doesn’t require complicated data structures. However, the search tree contains lots of redundancies- for example, see the first and second branches of the root node. There, the shapes of the subtrees are identical, and aside from the topmost square being either a 1×1 or blank, the nodes are identical as well. Here, it’s possible to use memoization/caching/memorization/value-storing, since future choices are dependent only on the shape of the collection of cells which have not been determined yet-not on the specific values of the cells that have been determined. Even better, every case which this algorithm evaluates corresponds to a polyomino fitting within the board containing the upper-left cell. Sorry if this is a bit verbose- here’s an example.

After the case for, say,

11111?1??11?????we can get all possible positions for the casesbpboard-2by replacing the large piece in the first case with the two other pieces and a void, then renumbering the pieces consistently. What I mean by this last step is that, inside SBPFinder, boards are represented as arrays of nonnegative integers, with 0 representing a void, 1 the first piece, 2 the second, and so forth. This is to prevent pieces unexpectedly merging- for example, in 1D, this would come up when the 1 piece (a domino) in {1,1,2,2} was replaced by {1,2} (that is, two 1x1s), resulting in {1,2,2,2}. tl;dr: if the program skips this step, bad things happen. This still requires storing a huge number of boards, but it’s actually possible to implement this as a series of not very complicated read/write operations on files- in other words, I have the file system do the memoization. Here’s what the search tree looks like under this approach:

2x2sbpanalysis-2

The lower left gets a lot of use.

Anyways, the resulting algorithm can also be used to quickly enumerate the number of ways of packing polyominoes, with holes, into an n*m grid. For example, I can tell you that there are 6,904,653,755 ways of doing so for a 5*4 (height*width) board, 3,117,469,335,485 ways for a 5*5 board, and 168,315,938,005,873 ways for a 15*2 board. Each of these considered 53341, 1054066, and 803760 cases respectively, which took a few minutes. The 5*4 board is just within the range of possibility, since it would take only around 145 GB to store each possible position; the other grid sizes would take up 81 TB and 5217 TB, which, while technically possible, are certainly infeasible.

Even better, it gives an upper bound: A110, the Bell numbers! To derive this, first “unfold” a 2D n*m board by flattening the array to get an array, of length n*m (redundant syntax, I know), but with disconnected pieces. Since the set of ways of placing disconnected polyominoes into a 1D array is a superset of the set of unfolded packings of polyominoes into a 2D board, and is much easier to compute the size of, we’ll use that as our simplified model. Then, the number of ways is defined by

a_{n+1}=a_{n}+\sum\limits_{k=0}^{n}\binom{n}{k} a_{n-k} , a_{0}=1

i.e., a board with n+1 cells either starts with an empty cell, or a disconnected piece (formed by choosing the first cell, and then adding on k of the n remaining cells). There are two ways to prove that a[n]=BellB[n+1]; the first is to try to express things as an EGF, which involves calculus and knowledge of binomial convolution, and eventually lands you at

a_{n}=n![z^{n}]e^{e^{z}+z-1} .

Integrating this to get an-1 gives

BellB(n)={\int a_{n} \partial z}=n![z^{n}]e^{e^{z}-1}

An alternative approach is “proof by OEIS”- specifically, 1D non-connected SBPs with n cells have a simple bijection to rhyme schemes of n+1 lines: Add an empty space to the front, then add 1 to each cell (turning the voids into piece 1, piece 1 into piece 2, and so forth. Convert numbers to letters, and you’ve got a rhyme scheme, listed in the Comments section of OEIS A110 !

I guess "death by SBP" falls into the "Ice" category?

A slightly more understandable colored version is here

Unfortunately, the Bell numbers are not a terrific upper bound. An example: There are 55,807,716 ways of placing pieces on a 4*4 board (see post 2 in the series). BellB[16+1] is 82,864,869,804 – only three orders of magnitude off! Even a revised estimate from the old SBPFinder algorithm gives 3*4^6*5^9 = 24,000,000,000. Clearly, it could use some work.

So what’s the point of all this counting? Well, it takes about 100 seconds for SBPFinder to compute and write out all 1.42 GBs of 4*4 positions and about 20 seconds to reduce those to the 12,595,006 justsolved positions. Extrapolating linearly, it should take only 4 hours to process every single 5*4 board. The time’s OK; the space can be handled- what’s stopping us?

Categorization

or, 2073 boxes in a warehouse

The problem is memory. Again. Originally, SBPFinder would sort the positions into (n*m-1) files, with the kth file containing those positions with k pieces. Typically, the largest of these files contains one fourth of all positions, or about 14 million or a modest 226 MB for 4*4 boards. Even reduced to just the justsolved positions, this comes out to 7.5 GB on the 5*4s. Furthermore, due to 64-bit aligning, C#’s garbage collector, and the use of a HashSet, boards take up about 7 times as much space as they should, turning this into 52 GB to store a single file. Even better, because of some much-needed changes (see the “Computation” section below), two HashSets momentarily each contain all the boards, although this, at least, could be remedied without switching to C++. I’m not exactly willing to dual-boot into a 32-bit OS, and I don’t know how to buy RAM. The solution is, of course, more algorithms.

We start by defining an SBP Categorization Algorithm as an algorithm that sorts justsolved boards into different files (or boxes, if you prefer) such that all justsolved states reachable from any particular board are also in the same file. The simplest one of these is to put all the boards in the same file- trivially, this satisfies the requirements. The previously defined algorithm is also an SBP categorization algorithm: since the number of pieces is invariant under the Moves metric, all states reachable from a particular puzzle will have the same number of pieces, and thus will be in the same file. Under the same trivial logic, since the pieces themselves never change under the Moves metric, sorting puzzles by the number of pieces of each shape they contain is also an SBP categorization algorithm. Unfortunately, since there are well more than 53340 polyominoes that can fit in a 5*4 board, and presumably an enormous number of combinations of polyominoes, this would result in a lot of files. Currently, what seems to be a correct balance is to categorize boards by a list of the number of n-ominoes that each one has, with n going from 1 to 20. For example, if an SBP position had 3 monominoes, 1 tetromino, and 2 pentominoes, it would be given the list (3,0,0,1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0) and placed in the file with all other boards with that list.

It’s easy to see that the number of files that will be generated using this technique is at most the sum of A000041, the partition numbers, from 1 to n*m-1. (This is because we are “partitioning” the n*m cells into blocks, and there must be a number of holes from 1 to n*m-1). Checking this, we get 2086 files for a 5*4 grid, which is a very close upper bound- but in practice, there are only 2073 files. Where do these extra 13 come from?

(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0)
(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0)
(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0)
(0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0)
(0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0)
(0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0)
(0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0)
(0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0)
(0,0,0,0,0,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0)
(0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0)
(0,0,0,0,1,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0)
(0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0)
(0,0,0,0,2,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0)
The Impossible Files

In each of the cases just listed, there are no puzzles with the specified numbers of polyominoes because there are no justsolved positions. In an earlier blog post, I defined a justsolved position as one where a piece had just moved into the goal position (as far to the lower-right as it can possibly go). This would mean that the piece in question had moved right or down, and thus must be able to move left or up (since moves are reversible). This quickly rules out the first of these files, since it is impossible to place a 19-omino in a 5*4 board such that it can move at all. The other files are a bit more difficult, but can be eliminated in a similar way. For example, in the last file (2 pentominoes and 1 nonomino), each of the pieces needs at least two empty spaces to move, which can be seen by ruling out the I-pentomino and noting that the minimum dimension of any bounding box is 2. However, there is only one empty space, so no movement can occur, and so there can be no justsolved boards.

Ambiguity

Way back in Part 3, I poorly attempted to justify avoiding a few thousand puzzles which had ambiguous goal pieces. Specifically, in cases like

0000000001110102

Which piece has just moved into the lower-right?

it’s impossible to tell which piece is the goal piece in this justsolved state. Turns out there is a way to deal with such ambiguity and still find the hardest simple3 SBP, suggested by a remarkably foreseeing Navy gunner:

When you come to a fork in the road, take it!

Furthermore, at the time, it seemed like there would be no puzzle which was harder if the goal piece was the one second from the lower-right-hand corner. However, I eventually stumbled upon one of Dries de Clerq’s many unnamed SBPs, which turned out to be a bit of a wake-up call:

That notch in the P-pentomino just happens to be the right shape for a monomino- which introduces ambiguity.

That notch in the P-pentomino just happens to be the right shape for a monomino- which introduces ambiguity.

So, SBPSolver now considers all cases where there may be multiple goal pieces. (There is a slight inefficiency in that the operation to move boards from one HashSet to another [lines 296-297] momentarily takes up twice the memory as storing the file itself, but this hasn’t posed a problem so far, and could be fixed with some work.) Lastly, I also multithreaded it. This shouldn’t really need explanation; all the threads just work on different files.

Results

a tour of interesting simple3 SBPs

In total, it takes about 16 days to generate and solve every single simple3 SBP: two days to write out all the justsolved positions, a few hours to sort them into individual files, and two weeks to compute the “best” puzzles for each of these files. This comes at a cost of a whopping 180 GB of disk space (most of which is temporary- only 29GB of positions are justsolved) but uses a relatively low amount of memory. So, after all these weeks (and a restart due to fixing the ambiguity problem), I finally managed to find and confirm the hardest 5*4, simple3 SBP. But as it turns out, it’s been discovered before.

HENDERSON

The hardest 5*4: Bob Henderson’s “Gauntlet #2″ from Dries De Clercq’s 3S Puzzle Ring. Red block to upper-left. “Actions” here refers to the SuperMove metric, as discussed in the third post.

I’ve mentioned Bob Henderson in the context of sliding block puzzles before, but it turns out he’s actually a rather active member of the puzzling world. He created many of the levels for Andrea Gilbert’s (clickmazes) BoxUp and Extreme TJ-Wriggle (TJ here standing for Tom Jolly) puzzles, independently discovered the advertising-invalidating “Quzzle-Killer” SBP along with Gil Dogon, analysed almost every puzzle on Nick Baxter’s Sliding Block Puzzle Page , and even created a whole new set of puzzles for that site. He’s contributed problems and solutions to any number of puzzle sources, including Ed Pegg’s Mathpuzzle. He may also have co-written a huge number of auto repair manuals, though I’m not sure of that last part.

Sometime before June 2002, Henderson devised the incredibly difficult “Gauntlet” series of puzzles, which he later posted to Dries De Clerq’s 3S Puzzle Ring. Each of these 8 puzzles is a standard sliding block puzzle, requiring you to move a monomino to a corner in a rectangular board no larger than 25 cells. The easiest takes 183 moves; the hardest, 484. The second of these, pictured above, just happens to be a 5*4 simple3 SBP. Oddly enough, he missed a 3*6 simple SBP which is a predecessor of a simple3 SBP:

A to lower-right.

A to lower-right.

Anyways, he posted a surprisingly specific description of how he finds hard SBPs while writing about a different topic on the Extreme TJ-Wriggle page, here excerpted:

About 20 years ago I entered an annual nationwide puzzle competition in the USA. One of the challenges was to solve a simple sliding block puzzle in the fewest possible moves. Having taken a few computer programming classes and automated the solutions to various block-packing puzzles, I felt sure that sliding-block puzzles would yield to a similar approach. The method I used was a full-width search: finding first all of the positions that could be reached in one move from the initial state, then those that could be reached in two moves, etc. until the goal state was found. It sped up the process considerably to store only the states that had not already been reached, which was most easily handled by storing the new states for each generation in their own file for comparison with states found in later generations.

As it happened, I won that competition, which led to a deepening interest in slide puzzles. I read L. Edward Hordern’s book Sliding Piece Puzzles, corresponded with David Singmaster (who wrote its foreword), visited Nick Baxter’s Sliding Blocks site, and provided Nick with several shorter slide puzzle solutions. I collected the sliding block solver software available over the Internet and even had Rik van Grol send me a floppy disc with his own original program allowing human solvers to create and solve slide puzzles on-screen.

I soon became interested in creating as well as solving such puzzles. The movement rules for most slide puzzles (as well as many other sequential-movement puzzles) allow any legal move to also be made in reverse. It followed that a solver that could take all possible winning positions as its initial state and perform a full-width search to first find all new states one move from winning, then all new states two moves from winning, etc. would eventually reach some end states from which no new states could be reached. The other sliding block solvers all seemed to be limited to only one initial state, but my solver used an input file that could include any number of states within the computer’s processing and memory limits. It was not difficult to write a block-packing program to generate a file containing all the winning states for any given board (grid) and set of block shapes. Running my solver program backward (without specifying a winning state), I was able to find those states the largest number of moves away from the goal and verify that they represented the most difficult possible slide puzzles (those requiring the most moves to solve) for a given grid, set of blocks and goal. …

If you’ve been following along (and if my writing hasn’t been too vague) you might notice that this is very, very similar to how SBPSearcher works. I don’t know why, and honestly I got the “justsolved” idea from Tromp & Cilibrasi. I think the main difference is that his program probably takes a list of pieces as input and finds the hardest puzzle using those, while SBPFinder just brute-forces all possible combinations.

A Tour of the 5*4s

It would be a bit uninteresting, or even cruel, to get through nearly 3000 words of technical analysis and end with “…and somebody already found it” (although this has happened before: for instance, Bill Cutler ran a distributed, three-year search on all 35,657,131,235 different “holey” 6-piece burrs in an attempt to find the one which takes the most moves to disassemble… and found that Bruce Love had discovered the hardest before, by hand.)

For the sake of completeness, I went and ran the set of three programs on all rectangular boards with less than 21 cells, recorded the results for each file, and ran a fourth Processing program to generate images for each of these. The result is a massive website which allows you to browse through the hardest puzzles for more than 5,400 sets of polyominoes, from 2*2 to 5*4 and even 10*2. Here‘s a link to the page for 3x3s, which shouldn’t immediately crash your browser. All of the pages are interconnected- that is, you’ll be able to access any page from any other one, including itself. (In other words, its adjacency graph is the constant 1 matrix of size 15*15) As it turns out, when you have a lot of puzzles, a few will tend to be interesting. I’ve collected some of my favorites from the list below, ranging from unexpectedly difficult puzzles to novel but short positions. In each case, the goal piece is in the upper-right-hand corner (yes, there may be ambiguity), and needs to be moved into the lower-right-hand corner.

(2,8): This is probably the simplest of the ridiculously difficult puzzles to construct, requiring only dominoes, quarters, and a frame to create a position that requires 186 moves to solve! There’s also a neat stairstep pattern visible on the right-hand side. (If you’re really on a budget, see the substantially easier (0,9))

(0,2,0,0,0,1): Remember how the hardest 3-piece 4*4 simple3 SBP took 9 moves to solve? Turns out that with a 5*4 grid, we can do better by just 1 move! This is also the only 3-piece list which has a 10-move problem.

(14): This puzzle is trivial to solve. Matching the 10 move record, though, is much more difficult.

(0,0,4): If you happen to be a triomino purist, this is probably the SBP for you. Incidentally, this 18 move puzzle also happens to be the longest puzzle with no pieces smaller than a triomino. (No pieces smaller than a domino: the 102-move (0,5,2))

(2,1,1,0,0,0,0,0,1): There’s an interesting subset of simple3 SBPs which I call the “packing-sliding puzzles”, where there is one piece occupying the entire top row, all but the lower-right square of the right column, and the goal is really just to move that piece a single square. To do this, the other pieces have to be rearranged into exactly the right shape, which can occasionally be difficult. This is the longest of these puzzles for the 4*5 board; it takes 26 moves to solve.


(0,2,1,0,0,1) and (0,3,1,1): are respectively the longest 4 and 5-piece simple3 SBPs on a 5*4 grid. That’s about it.

(4,5,0,1): The second-hardest simple3 SBP requires 226 moves. Interestingly, it doesn’t have any triominoes, while most of the other high-move puzzles do.

(2,1,4): Speaking of triominoes, there are many 5*4 puzzles with a large number of triominoes which are still very difficult. Here’s one which requires 115 moves.

(3,2,1,0,1): The sparsest puzzle that requires more than 100 moves to solve, possibly making this the most unintuitively difficult by some metric. (Just barely: It takes 101 moves)

(2,0,5): And in case you can’t get enough triominoes… 29 moves. (5 is the maximum)

(3,6,1): Finally, here’s a puzzle which is very, very similar to many 5*4 tray puzzles such as L’Ane Rouge or Minoru Abe’s Block 10, perhaps because of the symmetric voids. I feel like I’ve actually seen this particular design before, but I haven’t been able to find it anywhere else. It takes an amazing 193 moves to solve!

Wrapping up

So, that about does it for all the 5*4 simple3 SBPs. Hopefully I’ve provided you with some insight into the problem of solving puzzles via computer, and that some of the puzzles generated have been interesting. This isn’t done, by any means (the set ℤ*ℤ is infinite, after all), but I at least plan to take an indefinite hiatus from this problem.

Over the last four blog posts on this subject, we’ve discussed puzzles that combine ridiculous difficulty with ridiculous size, a general program for generating hard SBPs using genetic algorithms which tends to get stuck, and created and improved a pipeline of programs designed to quickly and efficiently solve billions of these puzzles, all motivated by a somewhat sadistic impulse to create the most frustrating puzzle possible in the smallest box. We’ve also discussed metrics (I still haven’t gotten around to implementing the BB metric), numbering, and cases where five-word instructions aren’t enough.

In case you wish to verify the results, I’ve posted the code on github, as well as a list of hashes for each of the files generated by SBPSorter. (The entire 29GB directory compresses really well, all the way into a single 400MB file which I’ll be more than willing to send to anyone who emails me about it.)

Also, if you somehow managed to get through all that and somehow would like to solve more SBPs, I recently learned about two collections/programs which are both well done: Rodolfo Valeiras’ (somewhat unstable) Deslizzzp, which also happens to have the earliest occurrence I know of Bob Henderson’s “Gauntlet” puzzles, and the totally nonminimalistic Bricks Game. Finally, the sliding block puzzles in Professor Layton are kind of the inspiration for this whole thing, so I would definitely recommend those (especially as they’re actually solvable by humans! Except Puzzle 170 in The Last Specter. I have no idea what is up with that).

One last thing

Richard Hess manufactured the 132-move 4*4 puzzle for the 32nd International Puzzle Party!

I WANT YOU to procrastinate on blogging for half a year!

Happy puzzling!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 37 other followers

%d bloggers like this: