Slide24: Sliding Tile Puzzle for iOS
Posted by Jeffrey
Note: This is an archived version of the Slide24 page, for those interested in earlier versions. The most recent version is at Slide24: Sliding Tile Puzzle Webapp.
In my youth I really enjoyed the 5 × 5 sliding tile puzzle shown below, so a few years ago I coded it up as a semi-credible example of an iOS app written in OCaml. It turns out that it’s called the “24 puzzle” and has had a secret life as a test case for heuristic search algorithms. My implementation lets you shuffle and solve the puzzle, but if you’re pressed for time it’ll use a heuristic search algorithm to solve the puzzle for you.
On this page I show how to get the sources from Psellos and compile and run the app using Xcode. If you’re registered as an Apple developer, you can run it on your iOS device. (If you’re not, you can still run OCaml apps in the iOS Simulator. See Gamut: Explore Colors in iOS Simulator for a description of how to run an app in the iOS Simulator.)
This most recent version of Slide24 is 3.0.4. I built it under OS X 10.11 using Xcode 7.2 and tested it under iOS 9.2. Previous versions of Slide24, for earlier versions of OS X, Xcode, and iOS, can be found in the OCaml Programming Archives.
Most likely you’re familiar with the puzzle in the screenshots. If not: you first slide the 24 tiles around to shuffle them up. Then the goal is to put them 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 greedy best-first algorithm to find a solution, then animates the tiles to show the solution.
There is always a solution for the shuffled position—the app generates only solvable ones. However, very occasionally the heuristic can’t find a solution in a reasonable time. If you move some tiles around or shuffle again it will be able to solve from the new position.
Overview
The sibling 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. For now I’m
using the simpler animation interface, which uses pairs of begin/end
method calls to encapsulate animations. They are available in OCaml
through wrappers for the UIView class.
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 43% OCaml code, while Slide24 is around 51% OCaml code.
Preliminaries
If you want to build and run Slide24, make sure you have installed Apple’s Xcode and iOS SDK. You also need an OCaml-to-iOS cross compiler. I use OCamliOS, a modified version of OCaml 4.02.3. You can download a binary, or build it from source yourself. See Compile OCaml for iOS for details.
Get Slide24 Sources
Download the sources for Slide24 3.0.4 from this link:
Unpack and Check Particulars
$ tar -xf slide24-3.0.4.tgz
$ cd slide24-3.0.4
$ ls
Slide24 Slide24.xcodeproj
Most of the work of building Slide24 is done by Slide24/Makefile. You
may need to change some of the specific settings near the beginning:
IOSMINVER = 7.0
PLATFORM = iPhoneOS
ARCH = arm64
OCAMLDIR = /usr/local/ocamlios64
IOSMINVER is the minimum version of iOS that you want to run on. If
your app depends on recent features of iOS (which Slide24 doesn’t), you
would want to change this to a bigger number. ARCH is the CPU
architecture that you want to build the app for. It can be armv7 or
arm64; you should set it according to the iOS device you want to run
on. OCAMLDIR is the location of your OCaml cross compiler.
(If you like, you can change PLATFORM, ARCH, and OCAMLDIR together
to compile for the iOS simulator rather than an actual device:
PLATFORM is iPhoneSimulator, ARCH is i386 or x86_64, and
OCAMLDIR is something like /usr/local/ocamliossim32 or
/usr/local/ocamliossim64.)
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 from Xcode’s File -> Open menu, or double click on
Slide24.xcodeproj in the Finder.
Make sure Xcode is building the Slide24 target (not Slide24bin) and is building for the desired iOS device.
- Click the left side of the scheme selector at the left end of the toolbar. From the menu select Slide24.
- Then click a little bit to the right and select your iOS device from the top section.
Note that the device must support the architecture (32-bit or 64-bit) of the
cross compiler you’re using. 32-bit iOS devices are becoming more and more
rare, so I’ve set Slide24/Makefile up to specify 64 bits initially.
Next make sure code signing is configured properly. This is hard to describe, but not so hard to do.
Under the Navigate menu, select Reveal in Project Navigator. This should show the project as a whole and its two targets near the top of the second pane.
Click on Slide24, the target. It’s the last listed item in the second pane, with a miniature app icon. (You don’t want Slide24, the project, which is at the top.)
Click on Build Settings in the third pane. This brings up a zillion settings for the Slide24 target.
In the build settings, look at the Code Signing section. Make sure the Code Signing Identity and Provisioning Profile are set to something reasonable for your development environment. For me the code signing identity says “iOS Developer” and the provisioning profile says “Automatic”.
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 Product -> Build menu item.
To build and run, click on the Product -> Run menu item.
If things go right, you’ll see an app running on your iOS device 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.
Most Recent Changes
The most recent changes to Slide24 (for iOS 9.2) are the following:
Greedy Heuristic Search The new search finds a good solution to the full problem rather than stitching together optimal solutions for a set of smaller subproblems. The results are more various and interesting to watch.
Improved Heuristic As I mentioned, the 24 puzzle has been looked at by heuristics researchers over many years. I read some (humblingly old) papers on the subject and extracted some excellent advice on effective heuristics. In particular, I added “linear conflicts” to the heuristic, which improves performance tremendously. (Hansson et al., Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models, Tech Note CUCS-219-85, Department of Computer Science, Columbia University, New York, New York, December 1985.)
Tile Scaling Tiles are scaled in size to match the screen. To make this work, I generate full resolution images at startup. The results are pretty good on every iOS device.
Theory of Operation
Slide24 essentially follows the MVC paradigm. The model is a small data
structure—an 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 view controller delegate, an instance of the class
Slide24ViewControllerD.t. Let’s call this instance “the controller.”
The controller is created as specified in the storyboard file
Main.storyboard.
When you touch a button, Cocoa Touch calls a method in the
Slide24ViewControllerD (inverse) wrapper class, which is translated
directly into an OCaml method call of the controller. The controller
adjusts the model and calculates the new positions and appearances of
the buttons. It applies them through the UiButton wrapper instance,
and Cocoa Touch adjusts the display accordingly.
There is also an OCaml class named Slide24AppDelegate.t that
participates in the UIApplicationDelegate protocol (through a wrapper)
to receive notifications of changes in the application state. An
instance of this class is created at startup, as specified in the main
program main.m.
When you touch a tile button, the new model for the tile positions is
determined directly by the controller. When you touch the Solve
button, the controller invokes the Gbfsearch module, which runs a
greedy best-first search for a solution.
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 timerTick'
method. It advances to the next configuration in the list, and displays
it as usual.
Interface Builder
If you click on Main.storyboard in the leftmost pane, you’ll activate
Interface Builder to show the storyboard for Slide24. There are only
five interesting objects: the view controller, the main view, the
Shuffle and Solve buttons, and the view controller delegate (which
we’re calling the controller).
The interesting connections are as follows. There’s a connection from
the view controller’s delegate outlet to the controller. There are
connections from the controller’s shuffle and solve outlets to the
two buttons. Each button also has an action that tells it to invoke an
appropriate method of the controller (doShuffle: or doSolve:).
Discussion
As mentioned above, you can also run OCaml apps in the iOS Simulator. This is particularly easy, as it doesn’t require an iOS device or any code signing. You can download an OCaml-to-iOS Simulator compiler binary from Psellos, or build your own from sources. See Compile OCaml for iOS Simulator for more information.
Many other resources, including more example apps for both iOS and the iOS Simulator, are listed on our OCaml Programming page.
If you have comments, questions, or corrections please leave them below, or email me at jeffsco@psellos.com.