The 8-puzzle

Eight numbered tiles in a three by three frame, one empty square, and the job of sliding them back into order. I wrote this one in October 1999 with Theodoros Theodorou, for the Artificial Intelligence Laboratory at the University of Piraeus, supervised by Themis Panayotopoulos. It ran as a Java applet, under the handle I used then (ReneGade/TiS), so it stopped running when browsers dropped Java. In September 2026 it was written again, twice: once in JavaScript, which is the board below, and once as a desktop application. The tile faces, the logo and the about screen are the originals, and everything behind them is new.

How it plays

Click a tile next to the empty square, or push it with the arrow keys. Undo is unlimited. The applet's two modes are still there: play slides tiles under the rules, and arrange exchanges any two tiles, which is how you set up a particular board. Exchanging two tiles is not a move, so it starts a fresh run rather than counting against you — and it flips the puzzle's parity, so the status line tells you whether what you built can be solved at all.

Ask it to solve and it lists the shortest solution, one line per move, with the arrangement each move produces. Click a line to jump there, or let it play the whole thing. Playing the solution counts as playing; the moves go through the same rules and you can take them back one at a time.

The solver that never solved anything

The 1999 applet has a "Solve Problem" button, a search thread and a tree of states. It never put a solution on the screen, and it took this rebuild to establish why. The search tree shares one array between every node: the method that produces a child state does int[] _tmp = state;, which copies the reference and not the array, and then writes into it. Every "move" corrupts the position it came from. Hand it a board one slide away from solved and it wanders through 43 positions, none of them a legal successor of the last, and never sees the goal.

Even a correct answer would not have arrived. The end of a successful search walks up the chain of parents and prints each state with System.out.println, which on a web page in 1999 went to the Java console, and nobody had the Java console open. The list on screen was only ever filled by clicking tiles by hand.

And the build that actually ran on this website could not have started the search at all: it ships eight class files, and the one the search thread constructs first is not among them. Three independent reasons, in a program written for an artificial intelligence course.

Two more things it did not do. "Generate Random Game" swapped eighteen random pairs of squares, which lands on an unsolvable arrangement exactly half the time (50.00% over 200,000 runs of its own shuffle, which is what the parity argument predicts). And nothing anywhere checked whether you had won.

Shortest, not just solved

The rebuilt solver is A* with the Manhattan distance plus linear conflicts. The Manhattan distance is how far the tiles would travel if they could pass through each other; linear conflicts add the part it misses, which is that two tiles already in their goal row but the wrong way round cannot shuffle past each other — one has to leave the row and come back, two moves. Both estimates stay at or below the true distance, so the first solution the search completes is a shortest one.

No arrangement of eight tiles is more than 31 moves from solved. The tests search the whole space breadth-first — 181,440 arrangements, half of 9! — and check the solver's answer against the true distance for 300 random boards and for both of the 31-move worst cases. On those worst cases it settles the matter in about 3,800 arrangements and 12 milliseconds.

The other half of the space is the interesting half: sliding a tile never changes the parity of the number of inversions, so 181,440 arrangements can reach the goal and 181,440 can never reach it, whatever you do. The solver checks the parity first and says so, instead of searching for something that is not there. The applet had no idea, which is why its random games were a coin flip.

Two builds, and they are not the same program

The development directory survived, and so did the compiled applet, in this site's own repository under programs/2dapplet/on-line/. They are not the same program. The deployed one has an about screen — the credits above, and a piece of artwork — whose source is nowhere in the development directory. The development directory has a fourth skin, White Star, that never went online: the one skin that is a photograph cut into nine pieces rather than a set of numerals, so putting it in order gets you the picture. Every image the two builds share is byte-identical.

Both are kept in the repository, and both of the things only one of them had are back in the rebuilt game: the about screen with its artwork under Help, and the fourth skin in the picker.

How the browser version is built

One file of plain ES2020, no build step, no dependencies, served as a static page with nothing behind it. The board is a canvas drawn from the model on every change, and the search runs on the same thread as everything else — it can afford to, because the whole space is small: the worst board on this page takes about 5,000 arrangements and 20 milliseconds, and the page has time to put "Searching…" on screen first.

Its tile faces are copied out of the desktop game's own resources rather than by hand, which is also what keeps the two honest: the generator records a checksum per file, so a well-meant pass over the artwork would show up as a stale build rather than as a board that quietly looks different here.

On the desktop

The source is at bkarak/8puzzle (external link, opens in a new tab), which also keeps the 1999 sources under legacy/ (external link, opens in a new tab). It needs JDK 17 or newer; build it with mvn and run java -jar target/eight-puzzle-2.0.0.jar.

Neither 1999 build compiles today, and the reason is older than the applet ban: import imgCanvas; imports a class from the default package, which was legal in Java 1.1 and an error from 1.4 onwards. javac stops at the imports before it reaches anything else. So the rewrite kept the artwork and the rules and threw the rest away — an immutable board, a game model with undo, the search on a background worker, and a window that repaints from the model instead of poking single tiles through getGraphics() from whichever thread happened to be running.

The 1999 page

Everything from here down is the original page, transcribed as it was written.

Program developed by ReneGade/TiS and RoadRunneR.

The C source that solves the 8-puzzle was written by Anthony Petropoulos.