What I’ve Been Working on Lately

Readers of this blog may notice that I haven’t been updating for the last 4 months. The purpose of this “filler” post is for me to say why.

First of all, I could easily blame the season. Summer, as is well known, is a time to “kick back and relax” as well as forgetting about important things you should be doing and reading webcomics instead.

I could also blame the wonderful 3D printer I’ve bought, which has quickly filled up my desk and emptied my wallet with tens of tiny plastic models and puzzles.

However plausible that may seem, I would more truthfully blame the projects I’ve been working on, especially my “work” in the field of sliding block puzzles.

As you may know from a post I made about a year ago, I’m quite interested in really hard sliding block puzzles such as the Panex Puzzle (30,000? moves) or Sunshine (729? moves). James Stephens, of puzzlebeast.com, is certainly a pioneer in making really hard sliding block puzzles by computer. Using his “Puzzlebeast” software, he’s made at least 23 progressively harder sliding block puzzles, ranging from 18 to 148 moves! What’s more, he restricts many of these puzzles to only having a few pieces, and in at least 11 of them the goals are “Simple Simple”, that is, move a single piece to a single corner! Even the puzzle which fits on a 4×4 grid and uses only 4 pieces and is only 18 moves to a solution, “Simplicity”, is really quite hard for a human to solve! Oskar van Deventer, maker of many mechanical monstrosities, has designed a 3d-printable version of the Simplicity puzzle, calling it the “Hardest sliding piece puzzle on a 4×4 grid”.

Gauging from Stephens’ description of Puzzlebeast, Puzzlebeast uses a genetic algorithm to create its puzzles. So far as I can tell, it starts with a random set of puzzles. It picks the hardest out of that set, then for the next generation it creates random “mutations” of the best puzzles of the last generation. For example, it may add a piece, move a piece, modify a piece, or remove a piece. Repeat this process over and over again, and eventually you’ll have a hard sliding block puzzle. I think because it seemed to work very well for him, I eventually tried to make a sliding block puzzle evolver for myself.

And so the SBP project began: The earliest version of my SBP evolver were coded in Mathematica, and was very manual.  I would start with 5 randomly generated 4×5 rectangular puzzles, without any restrictions on the number of pieces, and then for each puzzle I interpreted it as a “Simple simple simple sliding block puzzle”(see footnote 1) and then fed it into Analogbit’s online sliding block puzzle solver, which counts moves in steps, meaning that each “step” is sliding one piece one grid space in the puzzle. Once that was finished, I took the best two puzzles, converted them to 1-d arrays, “interleaved” them, and then influenced random mutations in their cells (That is, each cell had about a 1/5 chance of being added 1 to or being subtracted 1 from). Since that probably isn’t too clear, here’s an example:

Suppose the best two puzzles from the last generation were

 0,19, 1, 2      0,19, 0, 3
 2, 1, 1, 1      2,19, 1, 1
 0, 2, 0, 2 and  1, 3, 2, 0
 1, 1, 0, 0      0, 1, 1, 0
 1, 1, 0, 1      0, 1,19, 2

Then the “interleaving” of the two would be

0,19,1,2,2,1,1,1,0,2,0,2,1,1,0,0,1,1,0,1 +

0,19,0,3,2,19,1,1,1,3,2,0,0,1,1,0,0,1,19,2=

0, 19, 1, 3, 2, 19, 1, 1, 0, 3, 0, 0, 1, 1, 0, 0, 1, 1, 0, 2

and the “mutants” would be generated from there, and the process would repeat.

Notes: 1. “Simple simple simple sliding block puzzle” is my own term, based off of Nick Baxter’s definitions at the Sliding Block Puzzle Page . For me, it means that each piece is different from another only by its shape, and that the goal is to get the top-left-most piece down to the lower-right. The original definition was somewhat ambiguous, it actually means that if there is no piece with a square occupying the upper-left corner, it is not a valid simple simple simple sliding block puzzle. Additionally, many of the puzzles in this first section are copied straight from the Mathematica notebook, and so there is a distinct lack of proper number parsing. Parsing manually is simple: If two numbered pieces have the same number and are orthogonally adjacent, they both belong to one piece. Otherwise, they belong to different pieces. (Eventually I got a parser working to make these puzzles conform to standards, so the reading should get easier). Lastly, steps and moves are different, as one involves moving one piece one space and the other involves moving one piece any number of spaces. Edward Hordern’s book, Sliding Piece Puzzles, does a good job to clear this up.

Anyways, the very first incarnation of the SBP Evolver produced quite fantastic results! In about 10 generations, with populations varying from 4 to 10, the puzzles had progressed from 4 impossible puzzles and 1 8-stepper to  3 impossible puzzles and 7 possible, one a 58-stepper! Now of course this is no big result, as such puzzles as Bob Henderson and Gil Dogon’s “Quzzle-Killer” take 121 steps to solve, and so this early experiment was really just a proof of concept.

Eventually, I got tired of feeding all these puzzles through Analogbit, so I decided to write a C# program to do it for me, except instead of using Analogbit, it would use Jim Leonard’s very speedy Jimslide software. Furthermore, it would have much larger populations (perhaps 100 or so) and do many more generations. Some time later, after writing many, many lines of code to process the puzzles for Jimslide’s use, and then processing the output, I finally got it working! Almost immediately, I set it going on a huge number of 4×5 puzzles (10 million) and let it run overnight. It actually took around 4 days, but the best it found was a 176-move puzzle!

1203-4253-4673-8879-ABCC

The 176-mover (by no means the best simple simple)

The SBP Evolver also displayed some behavior which I conjecture is common to most poorly-written genetic evolution programs: Once the program found a really good optimization, if there weren’t any tiny optimizations which would improve the puzzle, it would tend to stay with that puzzle for a while unless, by pure chance, the next generation happened not to contain that puzzle. As such, the 4 days might actually not have been long enough to find the best puzzle. Additionally, Bob Henderson’s Gauntlet #2, another simple simple sliding block puzzle, trumps the 176-mover with 235 moves!

As far as I can tell from his description on Andrea Gilbert’s clickmazes site, Bob Henderson uses a very different method of generating sliding block puzzles. He inputs a collection of shapes, and then his packing program generates all possible ways that those blocks could be placed in a sliding puzzle. He then feeds those through his sliding block puzzle solving program, which returns the best results. I expect it produces results much faster, albeit only with the blocks the designer chooses.

Having been thus discouraged, I set out to go through the much easier 4×4 puzzles instead. This time, after about a day, it generated a 125-move simple simple puzzle! However, it turned out that the puzzle could be backtracked to make a 132-move puzzle, presented below. Interestingly, when I ran the same computation again, it generated another descendant of the 132! Now, of course, the question was: Is this the best 4×4 simple simple simple SBP?

1123-4522-4678-0690

Red to lower-right.

The problem could be easily solved by just generating all possible 4×4 positions, interpreting a simple simple simple SBP out of them, and then solving each and every single one. But how would you do the former? After all, there can be 16 possible block types in a 4×4 (including holes) and each space could be one of the 16, so you’d have 16^16=18,446,744,073,709,551,616 possible combinations! My answer to this was to invoke the 4-color theorem, using 0 for the holes, and 1,2,and 3 for colors for the other pieces. After the 4-coloring of the board, a parser would assign each block a unique number, and then remove any duplicates (This was in fact WRONG; The holes could be separate, and so the 4-color theorem applied only to the blocks. I in fact had to eventually use 5-colors for the whole thing). After around a day or so, the puzzle-finder would process 4294967296 boards, and it returned only 52,825,604 different boards!

Two other methods which might have worked as well or better might be to either generate all 1-piece boards, then generate all 2-piece boards from all nonoverlapping combinations of the 1-piece boards, and so forth. There’s also a method based on dynamic programming which I currently use, which (while it is too long to write out here) is included in the SBPFinder source code, available at the bottom of the post.

After the 52,825,604 different boards were separated into files depending on the number of pieces, the host software would load up each file into a hash table, then solve the first puzzle. After the puzzle was solved, the software would process the output and remove the puzzles mentioned in the solution from the hash table. It would then solve the new first puzzle, and so on. While it isn’t very fast at all to use this algorithm (it took 48 days), it at least had an advantage: By separating the puzzles into files labeled with the number of pieces, it was possible to return the “hardest” puzzle for an arbitrary number of pieces in a 4×4 grid! Below is a table of the hardest simple simple simple SBPs in a 4×4 grid, from 2 to 15 pieces. Keep note, though, that since the computation missed out on a few million puzzles, all the below are unverified and the ones which are very dubious are removed. Also, because SBP determined which piece was the goal piece by going line by line, some of the puzzles below are simply simple simple SBPs and the ones which are just simple SBPs are removed. (Confused? Check http://www.johnrausch.com/SlidingBlockPuzzles/4×5.htm)

Note that these results are not to be trusted; for one, bugs have been found in both the problem finder and the puzzle-to-Jimslide converter itself, and so the results certainly aren’t rigorous. Also, the SBP Evolver (which also runs the puzzle-to-Jimslide converter and searcher) was originally designed to treat any puzzle as a simple simple simple, by choosing the goal piece as the first piece encountered going line by line through the board. Lastly, there’s a curious phenomenon around 12 pieces: Breaking a 1×2 into 2 1×1 pieces and shuffling the remainder about creates 9 more moves!

Since then, I’ve been trying to do a verification of the 4×4 computation, specifically by creating another program to rerun the entire search process, return the best results, and then check to see if the results are the same. The catch: I need it to be a few times faster. The optimizations I’m working on including are:

•Using one of the alternative methods to find potential SBPs faster,

•Only storing the “justsolved” puzzles, that is, puzzles in which the goal piece is already in the lower-right and can move out of it’s current position. (Based on an idea from “Rush Hour Complexity” , by John Tromp and Rudi Cilibrasi. It turns out that about 1/4 of 4×4 SBP positions are justsolved, a rather large value, mostly because in most positions there is a piece in the lower-right corner, and the only real limitation is that it must be able to move), and

•Using a custom-written sliding block puzzle solver to find the hardest puzzle in the entire group of positions the justsolved puzzle is linked to. (This can be done in 2 diameter searches, one to find the other justsolved puzzles in the group, and the other to find the starting position the furthest away from all the justsolved positions. My custom solver is about 3x as slow as Jimslide, but it makes up for it by that it’s solving the entire group of puzzles and removing the other justsolved puzzles from the list. There can be a stunning amount of other justsolved positions reachable from a puzzle- some have been found with over 14,000 !)

However, I’ve hit upon a gypsy moth in my solver causing it not to search the puzzle completely! Preliminary tests of the program though, have revealed the expected running time to be about a day, so stay posted!

Anyways, that’s my explanation as to what’s been going on, and I apologize for my relative silence.

  1. Your posts are always illuminating :)

    Is there any chance that you might share some of your code on something like github? These sort of searches sound like the type of computation that would benefit greatly from a parallel approach; if the code were visible more broadly, someone might be willing to give a program (or a port of it) a run on a cluster and get it finished much faster. Thanks for writing!

    • Thanks! I had actually planned to release the source code for the various programs once I got the solver working on my website, but github might work a bit better for open source projects like this.

  2. Very nice work! Bill Gosper emailed me that you had found a 26 move puzzle with the Simplicity set of pieces. I decided to crank up the PuzzleBeast software and to my considerable surprise out popped a 28 move puzzle with the same set of pieces in just a couple of minutes! I have no idea why I had never found it before. I can send you puzzle if you are interested.

    • sq
    • November 15th, 2011

    Interesting stuff, thanks!

  3. Neil, any sort of algorithm for searching this space which is pieces-based rather than whole arrangement based will be at a big computational advantage for the simple reason that if you want to find out how long it takes to solve the puzzle from a given position that requires almost as much computational time as figuring out how long it takes to solve the puzzle from all positions using those pieces (counting reorientations as different pieces, of course).

    • Shenyen
    • September 22nd, 2012

    That fourth puzzle – seven pieces, 68 moves – seems to quickly hit a wall. Is the diagram correct? Also, i remember a maths book back in the 1980s which included a few huge sliding block puzzles. Do you know the one? And can you recommend links to other, similar types of puzzle, thanks!

    • Thanks for noticing! The error in the 7-piece puzzle above was actually noted in the follow-up post to this one (http://nbickford.wordpress.com/2012/01/22/sliding-block-puzzles-part-3/):
      “Additionally, the 7-piece 68-move puzzle in the previous article is impossible to solve! The upper-left triomino should be flipped vertically in place. I expect this to have been a typing error, …”

      I don’t know of the specific book you’re referring to- there’s always Edward Hordern’s 1986 “Sliding Piece Puzzles”, generally the treatise on the subject, but it’s nether strictly on maths nor does it contain only a few sliding block puzzles. If the book you’re referring to consists of articles, it’s almost certainly Martin Gardner’s 1971 “Sixth book of Mathematical Diversions”, collecting his articles, one of which, originally published in 1964, was on sliding block puzzles. (It included the 15 puzzle, Dad’s Puzzle, L’Ane Rouge, Line Up the Quinties, Ma’s Puzzle, and the Tiger Puzzle, many of which are available online at Nick Baxter’s site.)

      The last question is simply too hard. Slocum’s puzzle classification puts Sliding Block Puzzles in the same category as the more general Sliding Piece Puzzles category, which consists essentially of puzzles involving pieces which slide. Notable examples, some covered in Hordern’s book, are Sokoban, Rush Hour (and Unit Rush Hour), Sliding Block puzzles (but with pieces that can rotate), Bricks Game (bricks-game.de), Railroad Shunting puzzles, Plunger puzzles (e.g. Ten Billion Barrel), Mirrorkal You and Einstein, etc. That in itself is a subcategory of Sequential Movement puzzles, which includes not only solitaire puzzles, but also mazes, counter puzzles, and every twisty puzzle ever made. In short, there are lots of puzzles which are similar to Sliding Block puzzles.

      -NB

    • Shenyen
    • September 27th, 2012

    A generous response. Thanks. I am enjoying the nice range of problems in these three posts of yours (the simpler ones I memorise and do while falling asleep – it’s good concentration training!). And I have now seen all the links at the end of post #3. Plenty to check out!

  1. January 22nd, 2012
  2. November 13th, 2013

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: