Archive for January, 2010

Sliding Block Puzzles

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.

The 15 Puzzle with the 14 and the 15 interchanged.

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.

One of the puzzles of Rush Hour

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.

AAAUUUGGGHHH!!!

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.

Online Collections—

John Rausch’s Sliding Block PageHumongous 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:

Super-easy

I hope that you can come up with a better one.

The Rubik’s Cube

One of the presents I got for Christmas was the 3x3x3 Rubik’s Cube, possibly the most famous sequential movement puzzle ever, next to the 15 puzzle. It’s remarkably hard, and the best I can do (without a guide) is to either solve the top face of cubies, the 2*2*2 section of it, and any number of corner cubes. With the guide, I have only  managed to solve it a few times, certainly less than the number of times I’ve read a long scientific book.

There are any number of methods for solving the Rubik’s Cube, with some being able to solve any cube in at most 30 moves, (The minimum is thought to be 22) and one of the easiest to understand is Dedmore’s method, shown here. Computers are much better at solving the Cube, with some examples being Rob’s Rubix Repair, a service that solves Rubik’s cubes in near-minimum moves depending on how long you are willing to wait, A Rubik’s Cube-solving Lego Robot:

A program called ACube solving a 1000*1000*1000 Cube:

And MagicCube4D and 5D, programs for making and solving various 4-dimensional and 5-dimensional Rubik’s Cubes:

Of course, people aren’t too bad with solving various Rubik’s Cube’s, as shown by Guinness World Records (about 10 seconds for the 3*3*3), and the cubes that are available. Companies have made up to 11*11*11 cubes, and there are videos ,such as the one following, of people solving a 20*20*20 cube.

People have even solved the 4-dimensional and 5-dimensional cubes, as shown by the MagicCube5D Hall of Insanity, where even my computer lags on solving some of them.

I, of course, still can’t solve the 3x3x3.

Even More Animations

Ever since my last post, I’ve been making more and more animations, which, in their uncompressed form, has been taking a strain on my hard drive. However, these have produced some amazing results, and at some point I should  upgrade to the newer version of my simulation software so that I can make animations of  Wada basins and the newly discovered Mandelbulb,  a 3-dimensional version of the Mandelbrot Set discovered by Daniel White.

The first one this time around is an animation of Video Feedback, sort of what you get when you point a videocamera at the screen of the T.V.:

I also made one showing fractal patterns with gravity sources:

A repeatable one “ping-ponging” the Mandelbrot Set:

and one showing a part of the Mandelbrot Set as the number of iterations is changed.

Of course, I can also make animations which are rendered in 3D, such as the  following one showing DLA, or diffusion-limited-aggregation, which is a bunch of particles moving around randomly until one touches a stationary point, at which point it also becomes stationary:

And lastly, a flyover of the Mandelbrot Set, where iterations are mapped to height:

Some more software by the same person involves making timelapses via webcam, which can be pretty interesting when made.

The first one of these is a timelapse of Mount Fuji in Japan, which shows some very interesting details if you look at it closely, such as people getting out of a bus:

And lastly, the most interesting, a timelapse of the buildings in Los Angeles:

I might take a break from making all these animations, and focus on something else for a while, such as puzzles and recreational mathematics.

Of course, I’d make animations of those.

Websites and the Konami Code

UPDATE: The Konami code on neilbickford.com no longer  points to Kelly’s website, but to something else… Kelly’s website can still be acsessed from neilbickford.com/kelly.htm

Just recently, my friend Mitchell Riley showed me his new site, Interesting Numbers. It’s still in development, as some screens currently bring up errors. (not 404,though)

The idea behind Interesting Numbers is that people can submit facts for numbers, eventually creating a huge database of number facts. On the front page it has the first number that no facts have been entered in about, which would come in handy, when the screens are full with numbers, the newest entered in numbers, and the newest facts.

I was able to test his website for bugs, and relatively little showed with the Over-Customized-Browser-Test, which consists of me tweaking the browser, turning Java and JavaScript on and off, changing the window resolution and size, the character encoding, and even more… The only problem was that when JavaScript was off, the “Jump to…” drop down didn’t work.

Then I tried entering in random words in the number field. It didn’t accept it, which was good. Then I tried a fraction that I knew was important, 866/455, which was the average distance between points in a Sierpinski gasket.

Uh oh.

Decimals also didn’t work.

I notified Mitchell about this, and so there might be datatype errors while he’s fixing the bug, which should be quick.

Recently, I came across a javascript routine for seeing if the user enters in a code. For example, you could make it so that when the user types in “EULER LIKES PIE” a window pops up that has Euler eating pie. The code’s called Konami-JS , and you can guess what the default code is.

Of course, I had to try it out, so now on my website, there are 3 easter eggs, one being the simple “Press this!”  button, which brings up digits of pi, the second being when you type in he Konami Code on a computer (up,up,down,down,left,right,left,right,b,a,enter), which redirects you to my little sister’s home page, and the third is a secret.

Of course, you could look at the source.