Slide24: Sliding Tile Puzzle Webapp

Posted by Jeffrey

In my youth I really enjoyed the well-known 5 × 5 sliding tile puzzle, so some 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, the time to finish an automated search can grow quite long in rare cases. To avoid an overly long pause, the search gives up after a reasonable amount of looking around. Hence once in every 23 times or so it won’t find a solution. If you move some tiles around or shuffle again it will be able to solve from the new position.

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

A few years back I heard from a guy named Phil Shapiro who wanted 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 milder version on the Shapiro Remix page.

The code for the webapp is self-contained: aside from the Js_of_ocaml browser interface modules, 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.

If you’re an OCaml programmer interested in looking at Slide24 in detail, the rest of this page describes how to get the OCaml sources for Slide24 and how to build it on a Unix-like system and run it in your browser.

Overview

This new Slide24 is written entirely in OCaml, and compiled to JavaScript using Js_of_ocaml. 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.

Preliminaries

If you’re an OCaml programmer, most likely you’ve already installed Opam. If not, please visit this link and install Opam before continuing.

You can use Opam to install different versions of the OCaml compiler using the switch create command. I’m currently using version 4.14.0, but almost any recent version should be sufficient. Here’s what I see when I ask Opam what switch I’m using (i.e., what compiler version is currently selected):

$ opam switch show
4.14.0

Next, you should use Opam to install the three packages that make up Js_of_ocaml: js_of_ocaml, js_of_ocaml-compiler, and js_of_ocaml-ppx. The current JSOO version is 4.0.0, so this is what I see when I ask Opam for a list of installed JSOO packages:

$ opam list --installed 'js_of_ocaml*'
# Packages matching: installed & name-match(js_of_ocaml*)
# Name               # Installed # Synopsis
js_of_ocaml          4.0.0       Compiler from OCaml bytecode to JavaScript
js_of_ocaml-compiler 4.0.0       Compiler from OCaml bytecode to JavaScript
js_of_ocaml-ppx      4.0.0       Compiler from OCaml bytecode to JavaScript

Make sure your shell’s PATH is set so that you can locate the OCaml bytecode compiler and Js_of_ocaml:

$ which ocamlc
/home/psellos/.opam/4.14.0/bin/ocamlc
$ which js_of_ocaml
/home/psellos/.opam/4.14.0/bin/js_of_ocaml

If this doesn’t work, you might try adding Opam’s current definitions to your shell’s environment:

$ eval $(opam env)

Get Slide24 Sources, Unpack, Build

Download the sources for Slide24 5.0.3 from this link:

• Slide24 5.0.3

After you unpack the tarfile you’ll find a directory with sources and a Makefile.

$ tar xf slide24-5.0.3.tgz
$ cd slide24-5.0.3
$ ls
bfsearch.ml      pselbutton.ml   s24anim.ml   shapiro.in
index.in         pselbutton.mli  s24defs.ml   slide24ctlr.ml
main.ml          pselcss.ml      s24look.ml   slide24ctlr.mli
main_shapiro.ml  pselcss.mli     s24look.mli  VERSION
Makefile         psipath.ml      s24path.ml

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

$ make
ocamlc -I /home/psellos/.opam/4.14.0/lib/ocaml/../js_of_ocaml -I /home/psellos/.opam/4.14.0/lib/ocaml/../js_of_ocaml-compiler/runtime -ppx '/home/psellos/.opam/4.14.0/lib/ocaml/../js_of_ocaml-ppx/ppx.exe --as-ppx' -c pselcss.mli
. . .
ocamlc -I /home/psellos/.opam/4.14.0/lib/ocaml/../js_of_ocaml -I /home/psellos/.opam/4.14.0/lib/ocaml/../js_of_ocaml-compiler/runtime -ppx '/home/psellos/.opam/4.14.0/lib/ocaml/../js_of_ocaml-ppx/ppx.exe --as-ppx' -o main jsoo_runtime.cma js_of_ocaml.cma pselcss.cmo pselbutton.cmo s24defs.cmo s24look.cmo s24path.cmo psipath.cmo s24anim.cmo bfsearch.cmo slide24ctlr.cmo main.cmo
js_of_ocaml compile  -o bundle.js main
sed -n '1,/<script/p' index.in > index.html; \
        cat bundle.js >> index.html; \
        sed -n '/<\/script/,$p' index.in >> index.html

These commands run the OCaml bytecode compiler ocamlc to compile the sources and link them into a bytecode executable. Then js_of_ocaml translates the bytecode to JavaScript. Finally the JavaScript is inserted into the test page index.html.

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:

$ 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.

The lower-level interface to the browser is handled through the Js, Dom, Dom_html, and CSS modules of Js_of_ocaml. I find that these modules do a very good job of adapting the rather loose JavaScript API style to the more careful OCaml style.

The Bfsearch module performs a best-first search for a solution when you touch the Solve button. I’ve been working on the search code again recently (autumn 2022), and the generated solutions are now a little better. They average around 140 steps for randomly generated configurations. The optimal solutions I’ve seen average around 100 steps. However, 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 final version for iOS was Slide24 3.0.4. Unfortunately, these iOS versions are so old now that they’re mostly of historical interest. Nevertheless, given an OCaml-to-iOS compiler and a sufficiently motivated programmer they could be resurrected.

Information about the iOS 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, too, are of mostly historical interest, but I’ll do what I can to keep them up to date as things change in the OCaml programming world.

Comments

blog comments powered by Disqus