Note: Software to simulate these sliding block puzzles will be given and reviewed at the end of the post.
Recently I’ve gotten interested in various sliding block puzzles (or klotski) , which are sequential movement puzzles where you have to move a certain block to another position, often involving moving other blocks out of the way.
I mentioned in an earlier post the 15 Puzzle, which is one of the most famous examples of puzzles. In the late 1800’s, it sparked a 15 puzzle craze which apparently “drove hundreds of people mad”. In it, you would scramble up the blocks and then try to reorder them to it’s initial position. It’s moderately hard, but easy if you know the 1 algorithm needed to solve it. (This is unlike the Rubik’s Cube, where you may need to learn lots of algorithms) The thing which sparked the puzzle craze, though, was that Sam Loyd, the famous puzzlist, offered a $1,000 dollar reward for simply interchanging the positions of the 14 and the 15, while keeping all the other pieces the same.. At this point, if you have a 15 puzzle, or can make one, you should definitely try to solve this problem. Software for simulating the 15 puzzle is everywhere, and shouldn’t be too hard to find. An online version is here.
Loyd’s money was safe, though, because the puzzle is impossible. Mathematicians have proved that you can only obtain half of the solutions from any starting position.
Soon after that came sliding block puzzles with differing shapes. Some good examples of these are Dad’s Puzzle, Get My Goat, and the Tit-Bits Teaser#4. These puzzles could often be easy, or they could be extremely hard, requiring hundreds of moves for the smallest solution.There are even 3-dimensional sliding block puzzles, called burr puzzles, of which are sometimes easier than sliding block puzzles, but some, like Gordian’s Knot (by Thinkfun) are harder, having much more pitfalls and requiring 63 moves to complete.
Sliding block puzzles are still popular today, as there are many recent products. The most well-known is Rush Hour by ThinkFun, which has cars sliding only in straight lines on a rectangular grid, where the object is to remove the red car through an opening. The Rush Hour set comes with 40 challenges as well as an opportunity to make your own. ThinkFun also makes Gordian’s Knot, an insanely hard burr puzzle, and a version of the 15 puzzle.
The hardest sliding block puzzle that has recently been made, though, is the Panex Puzzle. It’s like the Tower of Hanoi except that the pieces can go no lower down than their original starting position, and the object is to switch the two towers. It’s so hard that it requires approximately 30,000 moves for the minimum solution, and even that is not known.
There are many software programs for simulating, solving, and making Sliding Block Puzzles, and so I will list the best ones that I have found. Sliding block puzzle solvers have to work by trial and error, as an algorithm to solve sliding block puzzles in even polynomial time has not yet been found.
Taniguchi’s Sliding Block Puzzle Solver- A good program for quickly solving sliding block puzzles with any shape, usually solving even the hardest ones in a matter of seconds, and supports constraints, and comes with a number of built-in puzzles. However, the designer and the solver are separate programs, and there is not a playing program for the sliding block puzzles that you make. You can download it here.
Klotski– (as done by a person named Phil) – A program mainly for creating and playing sliding block puzzles, which it does rather well, and has a great collection of puzzles to start out with, including the evil, evil Sunshine Two-part puzzle, which I have not even got close to solving. The way of making new puzzles lacks a good GUI, though (you have to edit a file), and the hosting servers are often down. Download it here.
SBPSolver– A program which designs, plays, and solves sliding block puzzles. Almost perfect except for the fact that some of it (“Oui” or “Non”?) is in French, and that the pieces can only be rectangular. It comes with a huge library of puzzles, though, and solves puzzles insanely quickly. Download it here.
John Rausch’s Sliding Block Page– Humongous collection of sliding block puzzles, old and new, with least known solutions to them. Some of them are easier than they look (Junk’s Hanoi, even though requiring 161 moves, is super-duper easy), and some of them are much, much harder.
New and Old Sliding Block Puzzles- Small collection of some of the hardest sliding block puzzles there are, from Dad’s Puzzler to the Devil’s Nightcap, requiring well over 600 moves. Could use a few more puzzles, though. (NOTE: The site, as of 11/26/2010, appears to be somewhat hazardous to visit (malware). All of the puzzles, though, are either on one of the above links or on Dries’s site, puzzles.net23.net, under Bob Henderson)
I end this blog post with a small competition. Who can make the puzzle requiring the most moves, with the next three rules:
1. Empty spaces must take up 1/5 of the total area of the puzzle, not including walls.
2. You may use any constraints you like, as long as you follow these rules.
3. The puzzle must fit inside a 20×20 grid.
You can email your submissions to me at techie314 [at+at-at] gmail [dot*dash/dash] com
I will reveal the winner and runner-ups in a future blog post, the winner being the one who’s puzzle requires the most moves.
For an example, here’s my terrible example which takes three moves:
I hope that you can come up with a better one.