Andy Hertzfeld is a bona fide Software Wizard. I'm not kidding: it was his official job title, codified on his business card. And not just any old business card, but one from Apple Computer. You see, not only was Andy a key player on the Macintosh team, but he also had a knack for doing the impossible. One his feats was described in the September 1995 issue of Byte Magazine.

Besides everything else he did to help get the first Macintosh out the door, Andy Hertzfeld wrote all the first desk accessories. Most of these were written in assembly. However, to show that desk accessories could also be written in higher-level languages, Hertzfeld wrote a demonstration puzzle games desk accessory in Pascal. Like its plastic counterparts, users moved squares around until the numbers 1 to 9 were in order. As time began to get short, the decision was made that the puzzle, at 7KB [7KB = 7168 bytes], was too big (and too game-like) to ship with the first Macintosh. In a single weekend, Hertzfeld rewrote the program to take up only 800 bytes. The puzzle shipped with the Mac.

That's pretty impressive, especially considering that simply telling the story took a little under 800 bytes. Fortunately, Andy did have one thing going for him: sliding puzzles — especially of the 32 variety — are pretty simple. There are nine squares and eight pieces, and a piece can slide into the empty square.

1 2 3
4 5 6
7 8  

A solved puzzle will have the pieces arranged in left-right/top-bottom order, with the empty square being in the bottom right, as shown above.

Bring Your Own Code

Your exercise for the day: write a function that solves a 32 sliding puzzle.

  • The input should be a series of nine numbers (string, integer array, etc) that represent the eight pieces and the empty square.
  • The output should be a series of numbers that represent a solved puzzle.
  • The sort logic should follow the sliding puzzle rules and can take one of three forms:
    • Easy - whatever it takes to solve the puzzle, even random moves
    • Medium - an algorithm that makes a reasonable attempt to solve the puzzle
    • Difficult - an algorithm that solves using the most efficient path possible

As far as I'm aware, there are no impossible starting configurations and your function should be able to process any series of nine numbers.

[Advertisement] BuildMaster allows you to create a self-service release management platform that allows different teams to manage their applications. Explore how!