3×3 Sliding Tile Puzzle

Resident Evil 4 has a Sliding Tile Puzzle, similar to the 15 Puzzle but 3×3 instead of 4×4.  There are several cookie-cutter solutions available online, such as this one, that assume a starting configuration.  But what do you do if the first thing you did when you came upon the puzzle was mess it all up?  What’s interesting about the 3×3 puzzle is that there’s a very simple solution starting with any configuration.  It can be solved using only 3 different moves:

1. Clockwise movement of outer tiles:  If the empty square is on the outer ring, move the tile next to it into it so that the tile moves in clockwise direction.
2. Moving a tile from the outer ring into the center (if the center is empty)
3. Moving a tile from the center into the outer ring (if an edge square is empty)

The idea is to make the outer ring look like a clockwise-rotated version of the final solution.  This is done tile by tile, by inserting each piece in its correct position relative to the outer ring of tile.  Follow these steps: First, visualize what the outer ring (excluding the center) should look like.

1. Pick any outer ring tile that is on the outer ring in your current configuration.  It doesn’t have to be in its final place.  Call it tile 1.
2. Now, identify the tile that comes behind tile 1 clockwise in the outer ring in the final solution.  Call it tile 2.  We will try to correctly move tile 2 into the spot just behind tile 1.
3. Get tile 2 into the center: if the center is not empty, empty the center by moving the center tile to the outer ring.  If tile 2 is in a corner, rotate the entire outer ring clockwise until it is not in a corner, then move tile 2 into the center.
4. Now again rotate the entire outer ring so that tile 1 is in a corner and has a space just behind it in clockwise orientation.  Move tile 2 to the empty space.  Now tile 1 and tile 2 are in the right order.
5. Tile 3 is the tile that comes after tile 1 and tile 2 in clockwise orientation in the final solution.
6. Move tile 3 into the center.  If it’s in a corner, rotate the entire outer ring clockwise until it’s not in a corner and then move it into the center.
7. Now rotate the entire outer ring clockwise until tile 2 is in a corner and there’s a space just behind tile 2 in clockwise orientation.
8. Move tile 3 to the empty slot.
9. Now repeat these steps for tile 4, tile 5 and so on.
10. Once all the outer ring tiles are in place, move the center tile from the outer ring to the center.  Now rotate the outer ring clockwise until the puzzle is complete!

Ubuntu and Whizzytex

I have an earlier post in which I pointed out that whizzytex was causing emacs to freeze intermittently.  After a lot of searching and a bit of system tool use (specifically, iotop) I think I’ve pinpointed the problem (but not solved it yet).

It looks like the problem is not with Whizzytex at all, but related to known a known bug in Firefox and/or Tracker and/or Google Desktop.  Or maybe something about the way fsync() and kjournald interact.  These programs access disk a lot, which is what was causing the delays.  Apparently this is compounded because Firefox 3 issues a large number of calls to fsync(), which in turn causes kjournald and pdflush to activate on a regular basis.  This is what sometimes ties up the disk for a second or two.

A potential solution is to tell firefox to do asynchronous updation of history and bookmarks, and use a ramdisk for the Firefox cache.  I tried this and also disabled tracker and gdl_indexer indexing, but I’m not sure it’s helping yet.

Update (Feb 25, 2009):

Fixed!  I am fairly sure that google desktop was one of the factors behind the annoying slowdowns.  I am not sure which (if any) of the other issues (firefox and tracker) was responsible.  But if I disable all three, I don’t see the delays any more.  I’ve been freeze-free for about 3 weeks now!  I like google desktop, so I simply disable indexing before starting whizzytex and re-enable it after.