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!

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?

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.