Slide24: Sliding Tile Puzzle for iOS
Posted by Jeffrey
I’ve put together another iOS app in OCaml, one that interacts with you. It lets you solve the well known 5 x 5 sliding tile puzzle, or if you’re pressed for time it will use a heuristic search algorithm to solve the puzzle itself.
In the instructions below I show how to get the sources from Psellos and compile the app using Xcode. If you’ve registered as an Apple developer, you can run it on your iOS device.
Most likely you’re familiar with the puzzle. But if not, the goal is to shuffle up the 24 numbered tiles, then slide them around until they’re back in numeric order. The app, called Slide24, has a button (at the lower left in the screenshots) for shuffling the tiles. Each tile is itself a button. When you touch a tile, it moves itself toward the empty spot. If the tile isn’t adjacent to the empty spot, the tiles in between move as well. If a tile isn’t on the same row or column as the empty spot, you can’t move it—just as with the physical puzzle.
There’s also a button at the lower right that solves the puzzle. It runs a specialized version of the A* heuristic search algorithm to find a solution, then animates the buttons to show the solution.
There is always a solution for the shuffled position—the app generates only solvable ones. However, the current heuristic can’t always find a solution in a reasonable amount of time. The search space is very large, and the heuristic occasionally fails when there’s a time limit. If you move some tiles around or shuffle again it will be able to solve from the new position. It would be an interesting project to improve the heuristic so that it finds a solution more often.
I built and tested the app using Xcode 3.2.5, the latest available at the time of writing. I would expect it to work with any recent (or future) Xcode release.
Please note that a few of the command lines of the following discussion are too long to fit on a single line of a typical browser window. In a lot of cases there is no good place to split them into smaller lines, usually because of a long filename or URL. Take care that you enter them as a single line if you are typing them in by hand.
My first OCaml iOS app, Portland, shows how to compile, link, and package an OCaml iOS app. However, the app itself doesn’t do anything very interesting. The Slide24 app, while still pretty simple, has more of the feel of a real app.
It has real GUI components.
It uses the Cocoa Touch animation facility to make the interface lively.
It performs some non-trivial computation.
To keep things simple, Slide24 is built entirely from one GUI element: the button. However, Cocoa Touch buttons are quite complex. The OCaml and Objective C wrapper code shows how to wrap a class that has many ways to control its appearance and behavior.
There are two forms of the Cocoa Touch animation facility. The most recent form is based on Objective C “blocks,” a simple implementation of first-class functions (also known as closures). Like many other programming languages these days, Objective C is adopting powerful structures like closures from functional languages.
Since blocks-based animation is only supported in the most recent
versions of iOS, I chose to use the previous animation interface, which
uses pairs of begin/end method calls to encapsulate animations. They
are available through wrappers for the
In the future it would be interesting to build an interface to blocks-based animation using OCaml closures in place of Objective C blocks. I’ve found that closures are especially powerful when you combine them with other functional language features, like partial application.
While the Portland app does no interesting computation, Slide24 does at least a little bit: it solves the puzzle using a heuristic search. As a result, the amount of OCaml code compared to Objective C code in Slide24 is a bit higher than in Portland. Depending on how you count, Portland is around 35% OCaml code, while Slide24 is around 55% OCaml code. For a realistic app such as Master Schnapsen/66 or Cassino, the ratio is much higher, and the amount of Objective C code even starts to become negligible. At Psellos we have a mostly fixed amount of Objective C, and write wrappers in OCaml. So the amount of Objective C is relatively small and independent of the size of the project.
I’ll discuss a few more interesting points in detail after I describe how to build and run the app.
Before starting, make sure you have installed Apple’s Xcode and iOS SDK. As I said, I tested with Xcode 3.2.5. Later versions of Xcode will work, but may require some adjustments. You also need an OCaml-to-iOS cross compiler. I use a modified version of OCaml 3.10.2, with patches from others and from us (Psellos). Our OCamlXARM page describes how to download this compiler, or build it for yourself.
Get Slide24 Sources
Choose a place to work (an empty directory would be good).
<good place to work>
Download the sources for Slide24 1.0.3 from Psellos:
$ curl -O -s http://psellos.com/pub/slide24-1.0.3/slide24-1.0.3.tgz
$ ls -l slide24-1.0.3.tgz
-rw-r--r-- 1 psellos staff 73178 Feb 1 13:45 slide24-1.0.3.tgz
To save typing, you can download it directly from this link:
Unpack and Check Particulars
$ tar -xzf slide24-1.0.3.tgz
Most of the work of building Slide24 is done by a
Makefile. You may
need to change some of the specific settings in this file:
PLAT = /Developer/Platforms/iPhoneOS.platform
SDK = /Developer/SDKs/iPhoneOS4.2.sdk
OCAMLDIR = /usr/local/ocamlxarm
PLAT to the location of your iPhoneOS platform directory, part
of the Xcode iPhone SDK. Change
SDK to the iOS SDK you wish to use.
Probably you want to set it to the most recent SDK that you have
OCAMLDIR to the location of your OCaml cross
Open Xcode and Change Project Parameters
To open Xcode, you can use the following command:
$ open Slide24.xcodeproj
This starts Xcode and opens Slide24 as an Xcode project. You can also open the project file (actually a directory) from Xcode’s File -> Open menu.
To simplify the discussion, I assume Slide24 is always your active project. This will be the case if you have only one project open in Xcode. (You might want to close any other projects temporarily—it will make things simpler.) Otherwise, begin each step by clicking the Slide24 project window to make Slide24 your active project.
Make sure Xcode is building for an iOS device (not the simulator) and is building the Slide24 target (not Slide24bin).
Go to the Project -> Set Active SDK menu item, and select Device.
Now go to the Project -> Set Active Target menu item, and select Slide24.
Next make sure code signing is configured properly. This is hard to describe, but not so hard to do.
Click on the Project -> Edit Active Target “Slide24” menu item. This brings up a multi-paned window for manipulating the target.
In the Properties pane, set the app Identifier to an appropriate value for your development environment. In the downloaded example, the initial value of the app id is
com.psellos.Slide24. If you’re using Automatic Device Provisioning, you probably don’t need to change the identifier. The wild-card profile will allow you to compile an app with any identifier.
In the Build pane, look at the Code Signing section. Make sure the Code Signing Identity is set to something reasonable for your development environment. For me it says: currently matches ‘iPhone Developer: Jeffrey Scofield (XXX)’ in ‘Team Provisioning Profile: *’. The Team Provisioning Profile is the one created for Automatic Device Provisioning; it’s a wild-card profile that matches every app id.
Build and Run
You can now build the app. If you have an iOS device attached, you can build and run it.
To build, click on the Build -> Build menu item.
To build and run, click on the Build -> Build and Run menu item.
If things go right, you’ll see an app running on your iPhone (or iPod Touch) that looks like the screenshots above. It’s actually quite entertaining, especially the shuffle animation and the automated solving. Or at least, I like them.
Theory of Operation
Slide24 essentially follows the MVC paradigm. The model is a small data
int array—representing the current configuration of the
tiles. The view is the grid of square buttons plus the two extra
Shuffle and Solve buttons—all instances of
UiButton. These are
coordinated by the controller, an instance of the class
When you touch a button, Cocoa Touch calls a method in the
(inverse) wrapper class, which is translated directly into an OCaml
method call of the controller. The controller adjusts the positions and
appearance of the buttons through the
UiButton wrapper instance, and
Cocoa Touch adjusts the display accordingly.
To keep things simple, the controller participates in the
UIApplicationDelegate protocol to receive notifications of changes in
the application state. This avoids having an extra class that would
just pass the notifications along to the controller anyway.
When you touch a tile button, the calculations for the new tile
positions are performed directly by the controller. When you touch the
Solve button, the controller passes off the calculations to be performed
Solve module, which guides the underlying heuristic search so
that it finds the answer quickly enough to be fun to watch. The
underlying search, in turn, is performed by the
When the controller is displaying a solution to the puzzle, the model is
expanded to include a list of future configurations along with the
current one. A timer periodically calls the controller’s
method. It advances to the next configuration in the list, and displays
it as usual.
The startup of an iOS app is controlled by a nib file, generated by
Interface Builder. For Slide24, the file is
Slide24.xib. This file
says to create the controller, and to make it the delegate for the
containing Slide24 app. It also contains descriptions of the Shuffle
and Solve buttons. The 24 numbered buttons, however, are created
dynamically at startup, mostly to avoid the tedium of specifying 24
nearly identical buttons with Interface Builder. The controller also
creates the animation timer at startup and tells it to call the
If you open
Slide24.xib with Interface Builder, you’ll see that it’s
still pretty simple. There are only a few interesting objects: the main
window, the Shuffle and Solve buttons, and the controller. There is
a connection to the controller from the
delegate outlet of the
application (represented by File’s Owner). There are connections from
the controller to the window and the two buttons. Each button also has
an action that tells it to invoke an appropriate method of the
One of the strengths of a language like OCaml is its formal type system, compared to the more ad hoc systems of languages in the C family. Where C makes exceptions in its typing rules to support things like operations on generic values, functional languages can capture the generic quality directly using parametric polymorphism. This gives a surprising combination of rigor and flexibility, one of the things that attracted me to OCaml in the first place.
As a small example of this, the wrapper for
UIButton captures its
subset of the Cocoa Touch design pretty faithfully, while using the
extra rigor of the OCaml type system to catch errors that Objective C
would miss. It’s not possible, for example, to use a touch event value
where a button state is expected. In Objective C, these are both just
unsigned integer values and can be freely interchanged or mixed.
Although its type system is unusual for an OO language (based on structure rather than naming), OCaml supports many of the usual OO idioms. For example, the following method is used to tell a button what to do when you touch it:
method addTarget'action'forControlEvents' : #Wrappee.t -> string -> controlEvents -> unit
The type of the first parameter specifies that it can be any object that is (inversely) wrapped by an Objective C object. In essence, this is any object whose “real” implementation is in OCaml but that can be accessed from Objective C. This is, in fact, precisely the set of objects that make sense as targets of button touches.
#Wrappee.t notation represents a light-weight kind of subtyping
similar to a protocol in Objective C. This has proven to be quite handy
in our larger projects at Psellos.
Another strength of OCaml is that its rigorous type system allows you to make changes to code while being sure it still makes sense. This plasticity was, again, one of the things that attracted me to OCaml originally.
I wrote the heuristic search code over quite a short time, rewriting it many times as I discovered problems or thought of new approaches. I probably wrote at least 25 versions, but there were no detours caused by errors in the modifications. For me at least, a strong and flexible type system helps focus on the problem I’m trying to solve.
It’s worth mentioning that the search is written in a functional style, which is my preferred way to write OCaml. It uses the Set and Map modules from the OCaml standard library (rather than imperative structures like hash tables). Even on a small device like the iPhone, the performance is excellent.
If you have comments, questions, or corrections please leave them below, or email me at email@example.com.