Sliding Between Kolams

A 15-puzzle with kolam tiles

We have seen that arranging sixteen oriented square kolam tiles on a $4\times4$ grid, subject to the matching, boundary, and connectivity rules, gives rise to 408 kolams. Each has two components in its tile-connection graph: one contains fifteen tiles; the other is the isolated tile $\mathtt{0000}$, whose drawing is a closed loop. The model and the count are developed in From Sixteen Tiles to Fifty-One Kolams.

Remove that isolated loop tile. The completed kolam now has fifteen tiles and one empty cell, just like the familiar 15-puzzle. It is natural to ask: can we play the 15-puzzle game on these kolam grids?

The familiar 15-puzzle
Position 16 left empty

A kolam with one empty cell
0000 removed

The sliding rules carry over immediately. A tile sharing a side with the empty cell may slide into it, leaving a new empty cell behind. Tiles keep their orientations throughout: we do not rotate them, lift them out, or exchange two occupied cells.

The destination changes. In the numbered puzzle, we try to put the numbers in order. Here, we begin with a valid kolam and ask whether the tiles can be slid into another valid kolam. Once we choose a particular target, we can ask a more demanding question: can this kolam be transformed into that one?

Try now

Start with the completed kolam below. Select a highlighted tile beside the empty cell, or focus the board and use the arrow keys, to slide it. Try to reach a different valid kolam; simply undoing your moves to recover the starting pattern does not count.

The lines may stop matching while you play. That is allowed: the challenge is to restore a complete, connected pattern at a different endpoint. Scramble loads a new valid starting kolam, Reset restores the current starting board, and Undo retraces one move.

Choose Show a route from the start to watch an example. A small grid traces the path taken by the empty cell, with arrows recording each move. Follow the gap as the tiles slide around it.

Before reading on, try three small experiments:

• Make one slide and inspect the connections around the cell you have emptied.
• Slide that tile straight back. Why is the restored pattern not a new answer?
• Find a way to move several tiles while eventually returning the blank to its starting cell.

Why can some kolams never reach one another?

Playing the puzzle raises a question that trial and error alone cannot settle. If we choose any two of the 408 valid kolams, must there be a sliding route between them? Or can two perfectly valid patterns be separated by an obstruction that no sequence of moves can overcome?

There are such pairs. One example is a valid board and the board obtained by turning its entire design through a quarter-turn, including the directions on every tile. Both are valid kolams, yet they cannot be joined by the permitted slides. We will verify a concrete pair below.

To explain why, we need a way to record a board, a quantity preserved by every slide, and a theorem that tells us whether that quantity detects every obstruction.

A precise description of the tiles

We use the square-tile model introduced in From Sixteen Tiles to Fifty-One Kolams. It is a deliberately simplified mathematical model inspired by kolam, with its own precise rules.

Each tile carries a four-bit word in the fixed order east, north, west, south. A $1$ records a connection on that side; a $0$ records no connection. Thus $\mathtt{1011}$ connects east, west, and south, while $\mathtt{0100}$ connects only north. There are $2^4=16$ words, and the inventory contains each one exactly once.

The orientation is part of a tile's identity. A tile may slide, but it may not turn. For calculations, we also give the word $(e,n,w,s)$ its ordinary binary value $8e+4n+2w+s$. The labels then run from $0$ to $15$: for example, $\mathtt{0100}=4$ and $\mathtt{1011}=11$.

A valid kolam board satisfies three requirements, in addition to using the full inventory:

1. Matching: the facing bits across every shared side agree.
2. A closed boundary: every bit pointing out of the board is $0$.
3. Connectivity: the fifteen nonzero tiles form one connected network through their matched $1$-connections.

The tile $\mathtt{0000}$ is part of the complete inventory and contains a closed loop. It has no connection to its neighbours, so it is necessarily isolated. Setting it aside gives the sliding puzzle its blank. Whenever we check whether a sliding position is a valid kolam, we imagine putting $\mathtt{0000}$ back in the empty cell.

Connectivity here refers to the graph of tiles joined across their sides. It should not be confused with a claim that the entire drawing consists of one continuous strand.

Two changing quantities, one unchanging sign

An invariant is a quantity that remains unchanged under every allowed move. To find one here, we combine the order of the labels with the position of the blank.

Read the board as a list

Read the cells from left to right across the top row, then the second row, and so on. Include the blank as the label $0$.

An inversion is a pair of entries that occur in the wrong numerical order: the earlier entry is larger than the later one. The list $(3,1,2,0)$ has five inversions: $(3,1)$, $(3,2)$, $(3,0)$, $(1,0)$, and $(2,0)$.

Write $N(X)$ for the inversion count of a board $X$. We need only its parity—whether it is even or odd.

The zero counts. Omitting the blank produces another common convention for the 15-puzzle, but its formula is different. We keep the blank in the list throughout this article, as the sandboxes do.

Locate the blank

Number the columns $1,2,3,4$ from left to right and the rows $1,2,3,4$ from bottom to top. If the blank is at $(a_0,b_0)$, the parity of $a_0+b_0$ records its checkerboard colour.

Notice the two conventions: we read the board from the top down, but the vertical coordinate increases upwards. Stating both removes an easy source of sign errors.

Define

This is the value displayed in the comparison below. It is $+1$ when the exponent is even and $-1$ when it is odd.

Why a slide preserves it

Every legal slide exchanges the blank with one tile. As a permutation of the sixteen labels, this is a single transposition, so it reverses the parity of the inversion count.

The same slide moves the blank to an adjacent square, reversing its checkerboard colour. Thus the parity of $a_0+b_0$ reverses too.

Both contributions change by an odd amount. Their sum changes by an even amount, and therefore

whenever one legal slide takes $X$ to $X'$.

The inversion count itself need not stay fixed. Nor does the blank's colour. The invariant is obtained by combining them.

Two valid boards that cannot meet

For the Unreachable pair in the comparison below, the starting board $X$ has $N(X)=67$ and its blank is at $(1,1)$. The target $Y$ is its clockwise quarter-turned image: it has $N(Y)=53$ and its blank is at $(1,4)$. Hence

Both endpoints satisfy all the kolam rules. But every slide preserves $\varepsilon$, so no sequence can take this $X$ to this $Y$. Failure to reach the target is not a failure of strategy: a route does not exist.

Switch between Reachable pair and Unreachable pair below. Slide tiles on $X$ and watch its sign stay fixed. The target $Y$ stays still. The reachable example is the twelve-slide pair analysed in the next section; Show a route from the start demonstrates it and traces the path of the empty cell.

Wilson's theorem: when does a path exist?

The invariant gives an impossibility test. If $\varepsilon(X)\ne\varepsilon(Y)$, it rules out every possible sliding path, however long or inventive. But equal values need a further argument: an invariant might fail to detect some other obstruction.

Think of the sixteen board cells as vertices of a graph, joining cells that share a side. This fixed board graph records where the blank may move; it is different from the changing graph of matched kolam connections. Its checkerboard colouring makes it bipartite: every edge joins opposite colours.

Wilson's theorem, applied to this grid, says that all sliding-puzzle positions form exactly two connected components. Its general statement concerns finite simple graphs that remain connected when any one vertex is deleted, excluding cycles and one exceptional seven-vertex graph. For such graphs, the puzzle graph has two components when the board graph is bipartite, and one otherwise. The $4\times4$ grid meets these conditions. Wilson, “Graph Puzzles, Homotopy, and the Alternating Group” (1974).

We have already found an invariant taking two values and proved that no slide crosses between them. Since Wilson's theorem says there are exactly two components, these two invariant classes must be the components. There is no further obstruction. With our convention,

Here $X\longleftrightarrow Y$ means that some finite sequence of legal slides joins the two boards, allowing invalid kolams along the way. The result for the classical 15-puzzle predates Wilson's generalisation: Johnson and Story established its necessity and sufficiency in 1879. The introduction to Karpman and Roldán's study of sliding puzzles reviews this earlier criterion.

One local move helps explain why permutations enter the story. Move the blank once around a $2\times2$ square. After four slides the blank returns, while the other three tiles have undergone a cyclic permutation. Such a three-cycle is even. With the blank returned to a fixed cell, every even permutation of the other fifteen tiles can be achieved. The little circuit illustrates the mechanism; it is not by itself a proof of that full statement.

The two components are the sliding orbits, distinguished by $\varepsilon=+1$ and $\varepsilon=-1$. Each contains $16!/2$ arrangements. Choosing a new pair in the interactive loads a new problem; it does not make a move that crosses from one orbit to the other.

Move X to Y: a complete example

In the second experiment, the target is fixed. Reaching a different valid kolam is no longer enough: every tile, including the blank, must match $Y$.

Here is a pair drawn from the sandbox's challenge set. The numbers are decimal labels for the binary tiles; $0$ marks the blank.

For an exact record of the arrangements,

The inversion counts are $N(X)=67$ and $N(Y)=61$. Both blanks are at $(1,1)$, giving

The invariant permits a route. To exhibit one, slide the following tiles into the blank, in the order shown:

Each number names the tile that moves, not a cell to click or a direction for the blank. After the last slide, the board is exactly $Y$.

The first few steps show how the invariant works numerically:

The integer in the fourth column changes, but its parity does not. Direct checking also confirms that all eleven intermediate boards in this route are invalid kolams. The valid patterns occur at the two ends.

Why twelve is the shortest possible

For each nonzero tile, count how many horizontal and vertical steps separate its current cell from its target cell. Add these quantities over the fifteen tiles. This is the total Manhattan distance, denoted $H(X,Y)$.

A single slide moves exactly one numbered tile by one grid step, so it can reduce this total by at most one. Every solution must therefore use at least $H(X,Y)$ slides. The blank is omitted from the sum to avoid counting the same slide twice.

For the displayed pair, $H(X,Y)=12$. We have both a lower bound of twelve moves and an explicit twelve-move route. Consequently,

No search over every possible solution is needed to certify this particular route. The lower bound and the construction meet exactly.

Knowing that a route exists is not finding the route

The invariant answers a yes-or-no question. It does not tell us which tile to move next, and it does not measure how far away the target is.

For a fixed reachable target $Y$, let $d(X,Y)$ be the minimum number of slides from $X$ to $Y$. Manhattan distance gives a useful lower bound, but it need not equal the true distance. Tiles can obstruct one another, and some routes must temporarily move a tile away from its destination to make room.

The fixed-target experiment makes this distinction visible. Try the reachable pair yourself, then use Show a route to replay the verified twelve-slide solution from the starting board. This control returns to the start before demonstrating the route; it does not claim to find a shortest path from an arbitrary position you have reached. Follow the empty cell on the route diagram: each arrow records where the gap moved, in the direction opposite to the tile that filled it. The original Move X to Y sandbox also offers a shortest-solution search from the current position.

There is also a precise fact about the distance indicator: after one legal slide, the exact distance to a fixed target changes by either $+1$ or $-1$. It cannot stay unchanged.

The triangle inequality first tells us that it changes by at most one. To rule out zero, observe that every move switches the blank's checkerboard colour. Every path between two fixed boards therefore has the same parity of length: even when the blanks occupy cells of the same colour, and odd when they occupy cells of opposite colours. Moving to a neighbouring board reverses this parity. The new distance must differ by one.

This statement concerns distance to one fixed target. The open-ended challenge in Sandbox 2 accepts any different valid kolam; the nearest acceptable board and a particular designated target are separate notions. Sandbox 3 is the natural setting for studying exact distance and shortest routes.

Where the 408 kolams sit

The full sliding-puzzle graph has $16!$ vertices. Only a very small subset of these vertices satisfies the kolam conditions.

The earlier square-kolam investigation found 652 boards satisfying the inventory, matching, and boundary rules. Of these, 408 have all fifteen nonzero tiles connected. These are the valid kolams used here. The enumeration and its constraints are explained in From Sixteen Tiles to Fifty-One Kolams.

Classifying these valid boards by their sliding invariant gives

These counts have been checked by exhaustive enumeration of the tile placements. The equality of the two counts also has a symmetry explanation, which we will prove next.

From any valid starting board, exactly 203 other valid boards are reachable, with tile orientations held fixed and invalid intermediate positions allowed. The starting board itself is the remaining member of its set of 204.

It is useful to keep three scales separate:

The number 204 is not the size of the sliding orbit. It counts the valid kolams encountered within that much larger component.

Rotating a kolam is a different operation

The earlier article identifies 51 kolams up to the eight symmetries of the square. How does that count fit with the two sliding orbits?

A whole-board symmetry moves the cells and transforms the directions on every tile. A clockwise quarter-turn, for example, sends an east connection to a south connection. A legal slide changes a tile's position while keeping its directions fixed. These are different operations, with different equivalence classes.

Here is a striking consequence: a valid board and its quarter-turned image always have opposite sliding invariants. They represent the same design up to symmetry, but one cannot be reached from the other by legal slides alone.

The quarter-turn calculation

Consider what a clockwise quarter-turn does to the three ingredients of $\varepsilon$.

First, it permutes the sixteen cell positions in four cycles of length four. Each four-cycle is odd, so the combined permutation is even.

Second, it permutes the four compass bits in every label. Any exchange of two bit positions swaps four pairs among the sixteen binary words, leaving the other words fixed. It therefore induces an even permutation of the sixteen labels. Since any permutation of bit positions is built from such exchanges, the quarter-turn's relabelling is even too.

Thus neither operation changes the parity of the full inversion count.

Finally, a clockwise quarter-turn sends the blank at $(a_0,b_0)$ to $(b_0,5-a_0)$. The coordinate sum changes by $5-2a_0$, which is odd. The checkerboard colour reverses, and hence

Rotation is a bijection on the valid boards, so it pairs the two invariant classes in equal numbers. Combined with the total of 408, this proves the split into 204 and 204.

For completeness, the eight square symmetries behave as follows. Each includes the corresponding transformation of the tile directions.

Every valid board has eight distinct images under these symmetries, as established in the earlier enumeration. Four images lie in each sliding orbit. Thus each of the 51 designs has four representatives in each orbit, and $51\times4=204$.

This also clarifies what a target means. If the target is the exact displayed board, its invariant decides reachability. If any rotation or reflection of a design is acceptable, the question has changed: every one of the 51 designs has representatives in each sliding orbit.

Questions to take back to the sandboxes

1. Explain an impossible target. Starting from a valid board, form its quarter-turned image on paper. Predict the new $\varepsilon$ value before counting any inversions. Explain why the same design up to rotation does not guarantee a sliding route to that orientation.

2. Make a three-cycle. Move the blank around a $2\times2$ square and back to its starting cell. Record which three tiles move. Perform the same circuit three times in total. Why does the board return to its original state?

3. Measure a route. For a pair in Move X to Y, count the Manhattan distance before playing. Compare that lower bound with the length of a shortest solution. Equality supplies an immediate certificate of optimality; a gap records the extra work needed to organise the tiles.

4. Count without the zero. Let $I(X)$ count inversions after deleting the blank from the row-by-row list, and let $r(X)$ be the blank's row counted from the bottom, starting at $1$. Show that our convention gives $\varepsilon(X)=(-1)^{I(X)+r(X)+1}$. Hint: if the blank is in the $k$th cell of the full list, it contributes $k-1$ inversions. Different conventions may reverse the names of the two invariant classes without changing the reachability test.

5. Change the permitted endpoints. Compare two challenges: reach an exact labelled board, and reach any symmetric image of that board. Determine how many target orientations are reachable before attempting a solution.

The blank gives the tiles room to move. The invariant tells us which destinations that freedom can reach. A local action—one tile entering one space—leads to a global division of all possible arrangements.