Psellos
Contemporary Development With Functional Programming

Slide24: Sliding Tile Puzzle Webapp

August 26, 2020

Posted by Jeffrey

In my youth I really enjoyed the 5 × 5 sliding tile puzzle, so a few years ago I coded it up as an example of an iOS app written in OCaml. More recently, I ported the OCaml code to run in the browser. As a result you can try out the puzzle right here:

To try it out, click on the tiles to shuffle them up. Then the goal is to put them back in numeric order with 1 at the upper left. When you click on (or 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. The Shuffle button at the lower left shuffles the tiles en masse.

If you’re pressed for time, the app will solve the puzzle for you. Just click the “Solve” button at the lower right and it will solve using a best-first algorithm.

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.

It turns out that this is called the “24 Puzzle” and has had a secret life as a test case for heuristic search algorithms.

I recently heard from a guy named Phil Shapiro who plans to use the Slide24 puzzle to teach elementary school kids about puzzle solving. He proposed a version of the puzzle with much milder shuffling, so as to be solved more easily. You can see this new remix on the Shapiro Remix page. The sources for Slide24 can be used to build either version of the puzzle.

The rest of this page describes how to get the OCaml sources for Slide24 and how to build and run it in your browser.

Overview

This new Slide24 is written completely in OCaml, and can be compiled to JavaScript using the latest release of BuckleScript. When running in a browser, the JavaScript code draws the puzzle in a rectangle the size of the original iPhone, and reproduces exactly the behavior of the original iOS app.

The code is self-contained: aside from the BuckleScript Js module, it uses no framework or outside resources. It’s my hope that it makes an interesting specimen of a small (but non-trivial) webapp written in OCaml.

Preliminaries

Before you build Slide24 you need to install BuckleScript and some associated tools from the nodejs ecosystem. I’m going to specify the exact version numbers I used in my testing, but later versions will almost certainly work. These instructions are for Linux or a similar Unix-like system.

First install npm, the nodejs package manager, using your native package manager (such as apt or yum). Afterward you should be able to execute npm as a command:

$ which npm
/usr/bin/npm

Now install the following 4 packages:

bs-platform@8.2.0BuckleScript compiler
browserify@16.5.2package JavaScript for browser
common-shakeify@0.6.2eliminate dead code
uglify-js@3.10.1compress code

It looks like this from the command line (with npm’s voluminous output elided):

$ cd
$ npm install bs-platform@8.2.0
$ npm install browserify@16.5.2
$ npm install common-shakeify@0.6.2
$ npm install uglify-js@3.10.1

Set your shell’s PATH to contain the nodejs executables. For bash and similar shells it looks like this:

$ export PATH=$PATH:$(pwd)/node_modules/.bin

Your shell should now be able to find bsc, the BuckleScript compiler:

$ which bsc
/home/myself/node_modules/.bin/bsc

Get Slide24 Sources and Unpack

Download the sources for Slide24 4.0.4 from this link:

After you unpack the tarfile you’ll find a directory with a Makefile (since I am old school).

$ tar xf slide24-4.0.4.tgz
$ cd slide24-4.0.4
$ ls
gbfsearch.ml     pselbutton.ml   s24anim.ml   shapiro.html
index.in         pselbutton.mli  s24defs.ml   shapiro.in
main.ml          pseldom.ml      s24look.ml   slide24ctlr.ml
main_shapiro.ml  pseldom.mli     s24look.mli  slide24ctlr.mli
Makefile         psipath.ml      s24path.ml   VERSION

The default Makefile rule makes a web page index.html containing the puzzle. So you should be able to build like this:

$ make

If you direct your browser to index.html you should see the puzzle as at the top of this page.

To build the Shapiro Remix you can type this:

$ make shapiro.html

This builds a file named shapiro.html that contains the puzzle with milder shuffling as explained above.

Theory of Operation

Slide24 essentially follows the MVC paradigm. The model is an int array representing the current configuration of the tiles. The view is a grid of square buttons (the visible tiles) plus the Shuffle and Solve buttons. Buttons are defined at a fairly high level by the Pselbutton module. The controller is defined by the Slide24ctlr module.

At a lower level, the interface to the browser’s DOM is given by the Pseldom module. It defines a small set of abstract types (node, text, element, canvas, div, span, button) and a subtyping relationship among them that mirrors the subclassing in the browser’s DOM.

Note that these OCaml types are completely abstract; in particular, they aren’t classes. I’ve found through the decades that classes and inheritance are as much a source of error as of expressivity and convenience. For this small DOM subset, anyway, a pure subtyping relation is much cleaner, and is sufficient to make things work. Of course the implementation relies on the underlying subtyping in the DOM.

The Gbfsearch module performs a best-first search when you touch the Solve button. I’ve been working on the search code recently, and the generated solutions are now pretty good. They generally have around 150 steps, while optimal solutions I’ve seen are about 100 steps. But finding optimal solutions is still too slow to make an entertaining app.

iOS Versions of Slide24

Earlier versions of Slide24 were built to run on iOS devices and used Cocoa touch components. The most recent iOS version was Slide24 3.0.4. Unfortunately, it’s so old that it’s now mostly of historical interest. However, given an OCaml-to-iOS compiler it could almost certainly be resurrected by a sufficiently motivated programmer.

Information about version 3.0.4 and all previous versions of Slide24 can be found in the OCaml Programming Archives.

Other OCaml and iOS resources are listed on our OCaml Programming page. Many of them are similarly of historical interest, but we’ll do what we can to keep them up to date as things change in the OCaml programming world.

Comments

blog comments powered by Disqus