GODRICH
#css-animation#button#loader#transition#scroll#dashboard#ui#design-trends

Sliding Puzzle: 9 Canvas Scenes, Parity to Search

· Godrich · 9 items · 27 min read

gameVanilla JSSCSSAutoplayGames & playHero section

Why are some sliding puzzle boards unsolvable? 02 counts flipped pairs to sort them, 05 raises a Manhattan distance bound to find a shortest solve, and 07

A Sliding Puzzle Is Not a Game of Shuffling Numbered Tiles Until They Fit but a Calculation Where Boards Split Into Solvable and Unsolvable Under the Rule That a Tile Beside the Blank Swaps With It: Building a Sliding Puzzle Starts by Choosing How to Shuffle and Which Values to Judge By

A Row of Tiles Sliding Toward the Blank in a Chain01 sp-row-chain-slide Telling Solvable Boards by Counting Flipped Pairs02 sp-parity-solvable-check A Manhattan Distance Heat Map for Each Tile03 sp-manhattan-heat-map Shuffling by Walking Away From the Finished Board04 sp-legal-walk-shuffle An Iterative-Deepening Search That Raises Its Bound to Find a Shortest Solve05 sp-ida-star-solve One Picture Cut Into Tiles With Visible Seams06 sp-image-tile-cut A Pointer Drag That Snaps Into a Cell on Release07 sp-drag-clamp-snap Undo History and a Solve Replay08 sp-undo-replay-cancel States and Search Nodes Compared by Board Size09 sp-size-state-count-ramp

Auto-plays · click a tile to jump to its section · all nine in one zip

The nine scenes share one board array, and each scene differs only in the function that reads it. Once the board is a number array the puzzle is a single state, and pressing or dragging only paints that state. If you want a sliding puzzle maker you can read in one sitting, this is its shape: a state, a few plain functions over it and a canvas that draws the result.

The board state comes from the real puzzle logic only

The bd array changes only through real move functions such as rowChain, walkMoves and idaStar. The screen then paints the changed array at cell coordinates, and no scene draws a faked board beside the logic.

A fixed 1/60 second step and an integer hash

The frame gap is cut at DT_MAX (0.05 s), stacked up and spent in fixed STEP_S (1/60 s) steps. No random number is used: an integer hash hash2(a, b) picks the shuffles and the demo presses, so one seed gives one board and one demo. When the tab hides the loop stops, and on return the stacked time is dropped.

        const order = [];
        for (let k = 0; k < list.length; k += 1) {
            order[list[k]] = k;
        }
        retarget(function (v) {
            const o = order[v];
            return (o ? o : 0) * STAGGER_MS / 1000;
        }, SLIDE_MS / 1000);
        recordPress(list, i);
    }

Sliding Puzzle in JavaScript: 9 Scenes — a Whole Row Slide, a Solvability Check, a Manhattan Distance Heat Map, a Shuffle by Walking, a Shortest-Solve Search, a Picture Tile Cut, a Drag and Snap, an Undo With Solve Replay and a Count of States by Board Size

Area, frames and intensity from the latest render

Each scene was rendered and measured for cumulative area, moving frames out of 23 and mean intensity.

Scene Area Moving frames Intensity
01 Row slide 27.1% 23/23 97.9
02 Solvability check 23.4% 22/23 120.5
03 Manhattan heat map 18.9% 23/23 154.4
04 Shuffle by walking 27.6% 23/23 119.9
05 Solve search 26.8% 22/23 126.0
06 Picture tiles 32.7% 21/23 106.1
07 Drag and snap 12.7% 19/23 110.3
08 Undo and replay 14.8% 21/23 153.0
09 State counts 12.9% 21/23 143.8

Scene 06 covers the most area at 32.7% and 07 the least at 12.7%. Scene 07 also has the fewest moving frames at 19/23, while 01, 03 and 04 reach 23/23 and 03 has the highest mean intensity at 154.4.

01A Row of Tiles Sliding Toward the Blank in a Chain

Press a tile in the same row or column as the blank and each tile between them moves one cell toward the blank, which suits an input where one press moves several tiles. A tile slides for SLIDE_MS (140) ms but starts STAGGER_MS (30) ms after the one before it, and the array swap finishes first, so the board state is settled the instant you press.

A Row of Tiles Sliding Toward the Blank in a Chain
Open in a new tab

01 · A Row of Tiles Sliding Toward the Blank in a Chain — Measured area 27.141% · moving frames 23/23Original by GODRICH · SCSS and React ship in the zip · See the password

SLIDE_MSSTAGGER_MSrowChain
    function rowChain(b, n, i) {
        const z = b.indexOf(0);
        if (i === z) {
            return [];
        }
        let step = 0;
        if (Math.floor(i / n) === Math.floor(z / n)) {
            step = i > z ? 1 : -1;
        }
        else if (i % n === z % n) {
            step = i > z ? n : -n;
        }
        else {
            return [];
        }
        const moved = [];
        for (let p = z; p !== i; p += step) {
            b[p] = b[p + step];
            moved.push(b[p]);
        }
        b[i] = 0;
        return moved;
    }

rowChain returns the moved tiles in order, that order sets each start time, and a chain of three tiles finishes after SLIDE_MS + 2 × STAGGER_MS = 200 ms.

02Telling Solvable Boards by Counting Flipped Pairs

Lay the tile numbers out in one line and count inversions, the pairs where an earlier number is larger than a later one; on a 4x4 board the layout is solvable only when that count plus the blank's row from the bottom is odd. I checked the rule in Node: breadth-first search from the finished 3x3 board reached 181,440 boards and each one judged solvable, while search from a board with only tiles 1 and 2 swapped reached 181,440 boards and each one judged unsolvable, with no overlap between the two sets.

Telling Solvable Boards by Counting Flipped Pairs
Open in a new tab

02 · Telling Solvable Boards by Counting Flipped Pairs — Measured area 23.449% · moving frames 22/23Original by GODRICH · SCSS and React ship in the zip · See the password

inversionsparityblankRow
    function inversions(b) {
        let c = 0;
        for (let i = 0; i < b.length; i += 1) {
            for (let j = i + 1; j < b.length; j += 1) {
                if (b[i] !== 0 && b[j] !== 0 && b[i] > b[j]) {
                    c += 1;
                }
            }
        }
        return c;
    }
    // which row the blank is on, counted from the bottom (bottom row = 1)
    function blankRow(b, n) { return n - Math.floor(b.indexOf(0) / n); }
    // the judging sum: inversions + blank row for an even width, inversions only for an odd width
    function parity(b, n) { return n % 2 === 0 ? inversions(b) + blankRow(b, n) : inversions(b); }
    function solvable(b, n) {
        return n % 2 === 0 ? parity(b, n) % 2 === 1 : parity(b, n) % 2 === 0;
    }

In the first demo board the start has 27 inversions and a blank row of 2, a sum of 29 (odd, solvable), and swapping tiles 5 and 9 at 1.8 s moves the sum to 32 (even) and the next 8 moves carry it through 34, 36 and 40 with the parity staying even.

03A Manhattan Distance Heat Map for Each Tile

For each tile the Manhattan distance, the columns plus the rows between its current cell and its home cell, sets how deep its color is, so the tile farthest from home reads at a glance. heatColor blends from pale mint at 0 through yellow at 3 to rose at 6 and above, and the sum H over the board is printed as a number too.

A Manhattan Distance Heat Map for Each Tile
Open in a new tab

03 · A Manhattan Distance Heat Map for Each Tile — Measured area 18.897% · moving frames 23/23Original by GODRICH · SCSS and React ship in the zip · See the password

manhattanheatsumH
    function manhattan(b, n, i) {
        const v = b[i];
        if (v === 0) {
            return 0;
        }
        const h = v - 1;
        return Math.abs((i % n) - (h % n)) + Math.abs(Math.floor(i / n) - Math.floor(h / n));
    }

On the four boards each move changes H by 1 and the end is 0; the seed 7 board starts at H 22 and solves in 26 moves over 700 nodes (2 moves up, 24 down), while the seed 18 board is the shortest at H 18, 20 moves and 236 nodes.

04Shuffling by Walking Away From the Finished Board

From the finished board the blank steps to a neighbor SHUFFLE_STEPS (60) times, so the result was reached by legal moves and the 02 check calls it solvable. A step straight back to the cell it just came from is skipped, and an integer hash picks which neighbor to take.

Shuffling by Walking Away From the Finished Board
Open in a new tab

04 · Shuffling by Walking Away From the Finished Board — Measured area 27.604% · moving frames 23/23Original by GODRICH · SCSS and React ship in the zip · See the password

SHUFFLE_STEPShashnoBacktrack
    function walkMoves(n, steps, seed) {
        const b = solvedBoard(n);
        const out = [];
        let noBacktrack = -1;
        for (let s = 0; s < steps; s += 1) {
            const opts = [];
            for (let d = 0; d < 4; d += 1) {
                if (d !== noBacktrack && canStep(b, n, d)) {
                    opts.push(d);
                }
            }
            const d = opts[Math.floor(hash2(s, seed) * opts.length)];
            blankStep(b, n, d);
            out.push(d);
            noBacktrack = d ^ 1;
        }
        return out;
    }

With seed 41 the check says solvable at 60 of 60 steps, H climbs by 1 per step over the first 10 steps and ends at 30 with 0 tiles in place, while only 490 of 1,000 hash-random layouts (49.0%) were solvable.

05An Iterative-Deepening Search That Raises Its Bound to Find a Shortest Solve

The search goes depth first guided by the Manhattan sum H, folds a branch when the moves so far plus H pass the bound, then raises the bound one step and goes again, and it shows that it stopped when the node count passes NODE_CAP (4000).

An Iterative-Deepening Search That Raises Its Bound to Find a Shortest Solve
Open in a new tab

05 · An Iterative-Deepening Search That Raises Its Bound to Find a Shortest Solve — Measured area 26.812% · moving frames 22/23Original by GODRICH · SCSS and React ship in the zip · See the password

NODE_CAPboundidaStar
        function dfs(g, h, bound, last) {
            nodes += 1;
            if (nodes > cap) {
                capHit = true;
                return INF;
            }
            const f = g + h;
            if (f > bound) {
                return f;
            }
            if (h === 0) {
                return -1;
            }
            let min = INF;
            for (let d = 0; d < 4; d += 1) {
                if (last >= 0 && d === (last ^ 1)) {
                    continue;
                }

Needing little memory, it makes a fair classroom example of an iterative-deepening search: the four 3x3 boards took H 10 to 18, solves of 20 to 26 moves and 1,429 to 2,800 nodes, and the seed 2 board took 3, 8, 57, 313, 1,261 and 1,158 nodes at bounds 14 to 24. On the four 4x4 boards the same search reached NODE_CAP each time, and the screen shows the count as min(nodes, NODE_CAP).

06One Picture Cut Into Tiles With Visible Seams

A noise gradient of sunset sky, sun and hills is painted on a canvas once, cut into TILE_N (4) by TILE_N cells and copied onto the tiles with drawImage, which gives a puzzle solved by picture instead of numbers. The last cell stays empty, and each tile gets a dark SEAM_PX (2) edge plus a highlight along the top.

One Picture Cut Into Tiles With Visible Seams
Open in a new tab

06 · One Picture Cut Into Tiles With Visible Seams — Measured area 32.667% · moving frames 21/23Original by GODRICH · SCSS and React ship in the zip · See the password

drawImageSEAM_PXtileCut
    function tileCut(v, px, py, wk) {
        const hc = (v - 1) % BN;
        const hr = Math.floor((v - 1) / BN);
        const sz = BSZ / BN;
        const x = BX + px * CS + 1;
        const y = BY + py * CS + 1;
        const s = CS - 2;
        ctx.save();
        ctx.beginPath();
        ctx.roundRect(x, y, s, s, lerp(6, 0, wk));
        ctx.clip();
        ctx.drawImage(picCv, hc * sz, hr * sz, sz, sz, x, y, s, s);
        ctx.restore();

As you place tiles the picture appears and the seams fade over 0.6 s after completion; a 216x216 picture cut at 54px gives 15 tiles, a 16-move solve and completion at 2.37 s, and the cut is the source-to-destination copy that the MDN drawImage page describes.

07A Pointer Drag That Snaps Into a Cell on Release

Press and drag a tile and it follows only along the axis toward the blank, clamped to one cell width. On release it settles into the blank if the offset passes SNAP_RATIO (0.5) and returns to its cell if not.

A Pointer Drag That Snaps Into a Cell on Release
Open in a new tab

07 · A Pointer Drag That Snaps Into a Cell on Release — Measured area 12.728% · moving frames 19/23Original by GODRICH · SCSS and React ship in the zip · See the password

SNAP_RATIOpointerclamp
    function dragMove(x, y) {
        if (!dragging) {
            return;
        }
        ptrX = x;
        ptrY = y;
        rawK = ((x - startX) * axX + (y - startY) * axY) / CS;
        const k = clampK();
        dragCx = (dragCell % BN) + axX * k;
        dragCy = Math.floor(dragCell / BN) + axY * k;
    }

One pointer path serves mouse and touch, as the MDN Pointer events page lays out; eight drags gave 5 snaps and 3 returns, with 0.85, 0.62 and 0.7 cells snapping, 0.3, 0.42 and 0.25 returning, and 1.45 and 1.2 clamped to 1.00 before they snap.

08Undo History and a Solve Replay

Moves are pushed on a stack and each undo pops one, so a slip is taken back one move at a time. For a replay, two opposite moves sitting side by side are both erased to shorten the line, then the moves show one by one every REPLAY_MS (220) ms with the shortened count and the original count written as numbers.

Undo History and a Solve Replay
Open in a new tab

08 · Undo History and a Solve Replay — Measured area 14.764% · moving frames 21/23Original by GODRICH · SCSS and React ship in the zip · See the password

REPLAY_MSstackcancelPair
    function cancelPair(ms) {
        const out = [];
        for (let i = 0; i < ms.length; i += 1) {
            if (out.length > 0 && out[out.length - 1] === (ms[i] ^ 1)) {
                out.pop();
            }
            else {
                out.push(ms[i]);
            }
        }
        return out;
    }

On four boards, 14 pressed moves minus 3 undos left 11 on the stack, the shortened counts were 5, 7, 7 and 3 (pairs erased 3, 2, 2 and 4), and replaying only the shortened line gave the same board as stacking the 11 moves, cell by cell; the first replay took 5 moves × 220 ms = 1.1 s.

09States and Search Nodes Compared by Board Size

The count of possible layouts for 2x2, 3x3 and 4x4 boards is worked out at the solvable half, which is the factorial of n×n divided by 2, and drawn as log-scale bars, with the node count from the 05 search on the same shuffle seed beside it.

States and Search Nodes Compared by Board Size
Open in a new tab

09 · States and Search Nodes Compared by Board Size — Measured area 12.89% · moving frames 21/23Original by GODRICH · SCSS and React ship in the zip · See the password

TILE_NstateCountlogBar
    function stateCount(n) {
        let f = 1;
        for (let i = 2; i <= n * n; i += 1) {
            f *= i;
        }
        return f / 2;
    }
    // log-scale bar: the base-10 log of the value over the log of the top, 0 to 1
    function logBar(v, top) {
        return clamp(Math.log10(Math.max(1, v)) / Math.log10(top), 0, 1);
    }

That makes 12, 181,440 and about 1.05e13 layouts, a jump of 15,120 times and then about 57.7 million times, and with seed 8 the nodes are 7 (a 6-move solve), 303 (14 moves) and 3,600 (28 moves), so the search grows with the board. It is a gauge for how difficulty jumps when you pick a board size.

When You Build a Sliding Puzzle in Code, How Many Values Decide One Tile Move?

The board array and the blank direction are the whole state

The board is one number array bd (0 is the blank and tile v belongs at cell v-1), and the blank direction d is one of four: 0 right, 1 left, 2 down, 3 up, with the opposite direction written d ^ 1. One move is no more than a swap of two cells in that array.

Value Meaning Changed by
bd board state (0 is the blank) rowChain, blankStep, walkMoves
d direction the blank moves arrow keys, drag, search
H sum of Manhattan distances manhattan, sumH (03, 05)

Several calculations come off the same board

inversions reads the judgment, manhattan reads the distance and walkMoves builds the shuffle, all from the same bd, so a board from one scene can be checked with the functions of another. H is one number that shows how far the whole board sits from home, and it falls as tiles settle.

Keep the Board as a Number Array, Pick a Tile Beside the Blank, Swap Their Places and Move the Result to Cell Coordinates to Draw: the Order in Which One Sliding Puzzle Move Is Handled

The array comes first and the screen follows

A press or a drag swaps the array first, and the tile on screen follows to its target cell by SLIDE_MS or SETTLE_S interpolation. Pressing again in mid-slide is safe because the state is already settled, and 06 moves its picture pieces with drawImage in the same order.

The bound steps up through the search

The 05 search starts its bound at H and, after each failed pass, raises it to the smallest value that was cut off. Nodes per bound pile into perBound and are drawn as rows, so you can read how much the search swells with each step up.

Putting It on a Real Screen Like a Sliding Puzzle Game: Building Without a Library, Touch and Mouse Input and When the Shuffle Runs

Building without a library

A 2D canvas is enough. The scenes use no library, WebGL or CDN, and each file holds the calculation functions and the scene demo together.

Touch and mouse input

Scene 07 handles the drag with pointerdown, pointermove, pointerup and pointercancel plus setPointerCapture, and the stage box carries touch-action: none so the page does not scroll along with a drag. The other scenes call the same array functions from the arrow keys and tile presses.

When the shuffle runs

Walking the blank with walkMoves before you show the board leaves no room for an unsolvable one. For a board you already received, run solvable before drawing it.

How this differs from the neighbors

The jigsaw puzzle post covers piece shapes and merging neighbors, while this post covers the swap rule with the blank and the solvability check. To see a grid rule solved by search, the maze generator post builds on a similar calculation frame.

Where a Sliding Puzzle Breaks: a Trap of Random Shuffles That Leave an Unsolvable Board, a Search so Deep That the Screen Freezes and a Dragged Tile That Hangs Between Cells on Release

A random shuffle leaves a board that cannot be solved

Mix the array at random and roughly half the boards can be solved: 490 of 1,000 hash-random layouts were, and 2,508 of 5,000 in the Node check. To filter them, run the 02 check before drawing, or shuffle by legal moves only as 04 does, because a board with two tiles swapped does not get its parity back no matter how many moves follow.

A search without a bound freezes the screen

On a 4x4 board the node count outgrows a small cap fast: with the cap raised to 300,000, seed 5 solved in 28 moves after 16,899 nodes and the other three boards did not finish. NODE_CAP (4000) prevents the freeze by stopping and showing that the cap was reached. In a real service, set the cap much higher or run the search in a web worker.

A dragged tile hangs between cells

If the drag is not clamped to one cell width, the tile overlaps its neighbor and it is unclear which cell it should land in on release. clampK cuts the offset to 0 to 1 cells and SNAP_RATIO decides snap or return in one step, so a tile cannot stay between cells.

The full source of the nine scenes and the editable files sit in the zip card below, and the password that opens it is mvvxprjw.

Change the Board Size, the Slide Time and the Shuffle Steps and How Much Does the Feel Shift? TILE_N, SLIDE_MS and SHUFFLE_STEPS Compared

Name Changed value Feel
A bigger board 06 TILE_N 4 → 5 The tiles grow from 15 to 24 and each shrinks from 54px to 43.2px, so the picture is cut finer with more seams, while lowering it gives a few big pieces. The solve stays 16 moves and completion stays at 2.37 s.
A slower slide 01 SLIDE_MS 140 → 400 A three-tile chain takes 460 ms instead of 200 ms while the 30 ms STAGGER_MS offset stays the same, so tiles following in turn blur into one block, and shortening it makes the offset stand out.
Fewer shuffle steps 04 SHUFFLE_STEPS 60 → 12 H drops from 30 to 12 (tiles in place from 0 to 3), so the solve gets shorter, while raising it mixes the board more. Over seeds 41 to 60 the mean H is 10.6 at 12 steps, 24.7 at 60 and 38.4 at 300.

The three values do not interact: TILE_N changes only the piece count and size, SLIDE_MS only the on-screen interpolation and SHUFFLE_STEPS only how mixed the board is. Change one at a time to see which value moved the feel.

One Static Board Under Reduced Motion: Accessibility Through a Sentence for the Scene and the Current Count of Tiles in Place

Arrow keys move the tile and U takes it back

The stage box of each scene is role="application" with tabindex 0, so it takes focus. The arrow keys move the tile going that direction, Enter, Space and P pause, N takes one step of the timetable and R restarts. In 08, U, Z and Backspace take back one move, and in 07 you drag the tile and release it.

Reading out only when the mode changes

The on-screen status line is aria-live="off", so it is not read while the demo runs. A hidden role="status" paragraph gets speakText() with the scene name and the count of tiles in place, but only right after you touch the board and when the mode changes, so the auto demo does not chatter.

Reduced motion and a hidden tab

With prefers-reduced-motion on, no loop runs and one board at the timetable's rest time is drawn, so tiles sit on their target cells with no interpolation and afterInput() redraws right after an input. A hidden tab stops the loop and the stacked time is dropped on return, which follows the MDN prefers-reduced-motion page.

    // stop while the tab is hidden and restart with a fresh clock on return so the hidden seconds do not land in one frame
    document.addEventListener('visibilitychange', function () {
        if (document.hidden) {
            stopLoop();
        }
        else if (!paused && !still) {
            startLoop();
        }
    }, { signal: off.signal });
    // when the setting changes: one still scene when it turns on, moving again when it turns off
    reduceQuery.addEventListener('change', function () {
        still = reduceQuery.matches;
        if (still) {
            showRest();
        }
        else {
            lap = 0;
            play();
        }
    }, { signal: off.signal });

Sliding Puzzle FAQ: How to Solve a Sliding Puzzle, Why Some Boards Cannot Be Solved and What You Need Before Putting It on the Web

How does a sliding puzzle solver find a shortest solve

It reads the Manhattan sum H from 03 as a guide and runs the 05 iterative-deepening search, raising the bound until a solve fits. On the 3x3 boards that took 1,429 to 2,800 nodes, and the screen prints the node count for each bound.

Why can some boards not be solved

Swapping two tiles flips the parity of the inversion count, which moves the board to the unsolvable side. Legal moves leave that parity alone: over 20,000 legal moves on a 4x4 board it changed 0 times, so about half of the random layouts cannot be finished.

What do you need before putting it on the web

One set of static files is enough. The canvas multiplies devicePixelRatio by at most 2 and there are no external fonts or server calls, so a plain static host will serve it. The frame loop is built on the MDN requestAnimationFrame entry.

Enter the archive password

The password is inside this article. You will find it as you read.