Alien Tiles

Alien Tiles is the Lights Out of a stranger world. The board is a seven-by-seven grid of tiles, each showing one of four colours that cycle in a fixed order, red to green to blue to purple and back to red. Clicking a tile advances it one colour, and advances every other tile in its row and its whole column with it. Starting from an all-red board, the task is to reach a chosen target, all green say, or all blue, in as few clicks as possible. It is the same kind of puzzle as Lights Out, a linear system hidden under a coloured surface, but the arithmetic is richer and the reach of each click is longer.

Arithmetic in fours

Two facts strip the game down, as before. Clicking a tile four times returns every colour it touches to the start, so no tile is worth clicking more than three times, and the order of clicks does not matter. A solution is a count, zero to three, attached to each tile. What a tile finally shows depends only on how many clicks landed in its row and its column, taken modulo four.

Count carefully and a tile at $(i, j)$ is advanced once by every click in its row $i$ and once by every click in its column $j$, its own clicks sitting in both but counted a single time. So if $x_{ij}$ is the number of clicks on tile $(i, j)$, the net advance of tile $(i, j)$ is $\sum_{l} x_{il} + \sum_{k \neq i} x_{kj}$, and to turn red into a target colour every tile must advance by the same residue $r$ modulo four, $r = 1$ for green, $2$ for blue, $3$ for purple. A spare non-negative integer $d_{ij}$ carries the multiple of four, exactly as the dummy did over the two-element field of the previous chapter, and the clicks are minimised.

from ortools.sat.python import cp_model

def fewest_clicks(n, residue, seconds=120):
    m = cp_model.CpModel()
    x = {(i, j): m.NewIntVar(0, 3, "") for i in range(n) for j in range(n)}
    for i in range(n):
        for j in range(n):
            row = sum(x[i, l] for l in range(n))
            col = sum(x[k, j] for k in range(n) if k != i)
            d = m.NewIntVar(0, n, "")
            m.Add(row + col == 4 * d + residue)  # net advance == r (mod 4)
    m.Minimize(sum(x.values()))
    s = cp_model.CpSolver()
    s.parameters.max_time_in_seconds = seconds
    s.Solve(m)
    return int(s.ObjectiveValue())

Green is dear, blue is cheap

There is a solution anyone can see: click every one of the forty-nine tiles once. Each tile then catches seven clicks from its row and seven from its column, less the one shared with itself, thirteen in all, and thirteen is one more than a multiple of four. Every tile advances by one, red turns green, and the whole board is green in forty-nine clicks. The model confirms that for green this obvious answer is also the best: there is no way to turn the board green in fewer than forty-nine clicks.

Blue is where intuition misleads. The same reflex says click every tile twice, ninety-eight clicks for an advance of two everywhere, but that is wildly wasteful. The model turns the board blue in fourteen, by the route of Figure 44.1: click each tile of the bottom row twice and nothing else. A tile off that row is advanced only by the two clicks beneath it in its own column, an advance of two; a tile on the bottom row catches all fourteen clicks of the row, and fourteen is also two more than a multiple of four. Every tile lands on blue, in fourteen clicks, and no fewer will do. Purple, by the same model, takes sixty-three. The three targets that look like simple multiples of one another, one step, two steps, three steps, have fewest-click costs of forty-nine, fourteen and sixty-three, an asymmetry that the modulo-four arithmetic produces and that no amount of staring at the board would suggest.

Sources. Alien Tiles was invented by Clifford A. Pickover and is played at alientiles.com: a square board of tiles in four colours, a click advancing every tile in the clicked tile’s row and column. The integer-programming formulation, over the integers modulo four with a dummy variable absorbing the multiple of four, is from Martin J. Chlond, An Alien IP, INFORMS Transactions on Education volume $7$, number $1$ ($2006$), pages $149$–$152$, which notes that the single-colour seven-by-seven targets resisted the general-purpose solver of the day even as they yield to the eye. The fewest-click counts of forty-nine for green, fourteen for blue and sixty-three for purple are produced and proved optimal by the model above; the forty-nine matches the click-everything-once solution, and the fourteen-click blue board is drawn here and re-checked by replaying its clicks. The companion puzzle over the two-element field, where a click flips a tile and its orthogonal neighbours, is the Lights Out of an earlier chapter.