Let the $3n^2$ asparagus squares be $a_1,...,a_{3n^2}$, and similarly byzantium for $b_1,...,b_{3n^2}$ and citrine $c_1,...,c_{3n^2}$. Suppose during the permutation, each $a_i$ replaces $b_i$ and each $c_i$ replaces $a_i$. Consider groups $u_i$ for $i=1,2,...,3n^2$ with each group $u_i$ containing $a_i,b_i,c_i$. Now tile the $3n\times 3n$ grid with 1x3 vertical rectangles. Each group $v_i,i=1,...,3n^2$ will contain the 3 cells in each of the $3n^2$ rectangles. Now consider a bipartite graph with bipartition $U_i,V_i$ for $i=1,...,3n^2$. An edge is drawn from $U_j$ and $V_k$ iff there is a cell belonging to both $u_j$ and $v_k$. Note that for any subset $U$ of $\{U_i\}$ of size $m$, the size of its neighbors is at least $m$ since you need at least $m$ groups of threes to cover $3m$ cells. Thus by Hall's Marriage lemma there is a perfect matching between $U_i,V_i$. Suppose $U_j,V_k$ are matched, then we can move $a_j$ to the common cell of $u_j,v_k$ in distance $d$ then to a 0 in $v_k$ in at most distance 2. Hence we can move each $a_i$ to a unique 0 in at most distance $d+2$. Similarly for each byzantium and citrine and we are done.

Crazy problem, I like it

We are therefore done. Also, I think my solution is different from Oneplusone's solution above, but I'm not sure...

Agree. This is a really nice problem. Partition the squareboard into $3n^2$ horizontal rectangles of size $1 \times 3$. Notice that these rectangles exactly contain one asparagus, byzantium and cytrine color square. It suffices to prove the statement for a color, let's say, asparagus. Let the tokens for asparagus, byzantium and cytrine be denoted as $a_i, b_i, c_i$ respectively. Notice that for every permutation $\pi$ of the board, there are 3 natural rectangle a token $a_i$ on rectangle $t$ could go: $\{ t, \pi(t), \pi^{-1} (t) \}$. Now, consider a bipartite graph of the set $A_i$: asparagus tokens and $T_i$: the $3n^2$ trimino. Now, $a_i$ and $t_k$ are connected by an edge if and only if $t_k$ is the "natural" rectangle that token $a_i$ can go to. Hence, each token $a_i$ is connected to 3 triminoes. We'll now prove the Hall's Condition. Take any $n$ tokens. Notice that the number of triminoes must be at least $n$, which are all the original triminoes the tokens are on, or otherwise, it won't cover $n$ asparagus tokens. Hence, the Hall's condition is satisfied. By Hall Marriage Theorem, there exists a perfect matching connecting each asparagus tokens to a unique trimino. By the definition of the natural triangle, this covers a distance of at most $d$. Now, since each trimino has complete color for all three colors, we can match the color of the token in that trimino to the suitable color, in at most $2$ moves (from the leftmost to the rightmost of the domino). Hence, it is possible to permute the tokens with a distance of at most $d + 2$.

I think it is possible to permute the tokens with a distance of at most $d+1$ with a better partition.

There are the partition for asparagus, byzantium and cytrine. A is asparagus, B is byzantium, C is cytrine. As for asparagus, use <picture 1> partition. As for byzantium, use <picture 2> partition. As for cytrine, use <picture 3>partition. But in this case, We have to think separately about white squares. Then, We can match the color of the token in that trimino to the suitable color, in at most $1$ move.

We will construct a perfect matching between tokens of color $A$ and squares of color $A$ such that each pairing pairs objects distance at most $2$ from each other. Indeed, let $\sigma$ be the original permutation of tokens. Draw a bipartite graph with tokens of color $A$ on the left, squares of color $A$ on the right, and an edge between token $t$ and square $s$ if and only if $s$ is at most $2$ away from one of $t,\sigma(t),\sigma^{-1}(t)$. Our goal is to show that this graph satisfies Hall's condition. Suppose we have a set $T$ of $A$-tokens. Let $T_1=\sigma(T)$, and $T_2=\sigma^{-1}(T)$. Note that $T,T_1,T_2$ are all disjoint since each set consists entirely of the same color of tokens. Note that all $A$-squares distance at most $2$ away from any token in $S:=T\cup T_1\cup T_2$ is connected to some token in $T$, so if we show that the number of such $A$-squares is at least $T$, then we've shown Hall's condition. It suffices to show that there are at least $|S|/3$ $A$-squares distance at most $2$ from any token in $S$. In fact, this is easy to see, simply tile the square with triominoes, as each one contains an $A$-square, so any token in the triomino as at most $2$ away from an $A$-square. This proves the existence of the matching. We consider similar matchings for $B$ and $C$, and moving each token to its matched square finishes the solution.

The key idea is to invoke Hall's marriage lemma. Let \(X\) be the set of cells with an asparagus token, and let \(Y\) be the set of asparagus squares, so by symmetry, the goal is to find a perfect matching between \(X\) and \(Y\) such that the distance between each pair is at most \(d+2\). For each subset \(W\subseteq X\), let \(W\) consist of the cells \(a_1\), \(a_2\), $\ldots$, \(a_{|W|}\). Moreover, let \(N_i(W)\) consist of all cells a distance of at most \(i\) from some cell in \(W\). Let the permutation send \(a_i\) to \(b_i\) (so \(b_i\) originally contains a byzantium token) and \(c_i\) to \(a_i\) (so \(c_i\) originally contains a citrine token). Observe that: there are at least \(|W|\) distinct cells in \(N_d(W)\) with asparagus tokens, namely \(a_1\), $\ldots$, \(a_{|W|}\); there are at least \(|W|\) distinct cells in \(N_d(W)\) with byzantium tokens, namely \(b_1\), $\ldots$, \(b_{|W|}\); there are at least \(|W|\) distinct cells in \(N_d(W)\) with citrine tokens, namely \(c_1\), $\ldots$, \(c_{|W|}\). Thus \(|N_d(W)|\ge3|W|\). Tile the \(3n\times3n\) grid with \(1\times3\) triominos, so each triomino consists of exactly one asparagus square, one byzantium square, and one citrine square. Let the asparagus square be the \(A\)-representative of these three squares, so every asparagus square is the representative of exactly three squares, and every square's representative is a distance of at most 2 away. Then \(N_{d+2}(W)\) contains the representatives of all cells in \(N_d(W)\), so \[|N_{d+2}(W)\cap Y|\ge\frac{|N_d(W)|}3\ge|W|.\]By Hall's marriage lemma, a desirable perfect matching between \(X\) and \(Y\) exists, and we are done.

Rename the color as $a,b,c$ for simplicity. For a square $S$, let $\overline{S}$, the closure of $S$ be those squares who share a corner or an edge with $S$, along with $S$ itself. If $T$ is a set of squares then $\overline{T}$ is defined to be the union of the closures of squares in $T$. Lemma. If $T$ is a set of monochromatic squares, then $$|\overline{T}|\geq 3|T|$$Proof. Let $T=\{s_1,...,s_k\}$. The case $n=1$ is just some trivial checking. For the general case, partion the board into $n^2$ $3\times 3$ board, call them $B_1,B_2,...,B_{n^2}$. Let $T_i=B_i\cap T$, and let $T_i'$ be the closure of $T_i$ in $B_i$ then $$|\overline{T}|\geq\sum_{i=1}^n|T_i'|\geq \sum_{i=1}^n3|T_i|=3|T|$$as desired. $\blacksquare$ Now let $A_1$ be the set of all squares with color $a$, and let $A_2$ be the set of all tokens with color $a$. Define $B_1,B_2,C_1,C_2$ similarly. Construct a bipartite graph with one vertex set being $A_1$ and another being $A_2$, such that $a_1\in A_1$ and $a_2\in A_2$ are adjacent if and only if $d(a_1,a_2)\leq d+2$. We want to show that this graph has a perfect matching. By Hall's theorem, it suffices to show that given $A_3\subset A_1$, the number of vertices $V$ in $A_2$ adjacent to some vertices in $A_3$ is at least $|A_3|$. We now show it. Indeed, letting $k=|A_3|$ from the lemma, $|\overline{A_3}|\geq 3k$. therefore there exists a color $D$, such that at least $k$ tokens with color $D$ lie in $\overline{A_3}$, we divide into two cases. Case I: $D=A$. Notice that all tokens in $\overline{A_3}$ has distance at most $\sqrt{2}<d+2$ with some squares in $A_3$, hence they must be adjacent to that square in the graph. Therefore, $V\geq |A_3|$ as desired. Case II: $D=B$ or $C$ WLOG assume $D=B$. Let these tokens be $b_1,...,b_k$, and let $a_1,...,a_k$ be the tokens which replace them. By triangle inequality, each $a_i$ is at a distance of at most $d+\sqrt{2}<d+2$ with some squares in $A_3$, hence they must be adjacentn to some vertices in $A_3$, which implies $V\geq |A_3|$. $\blacksquare$ By symmetry, there exists a perfect matching for $B_1,B_2$ and $C_1,C_2$ as well, this completes the proof.

We match color $A$ tokens with color $A$ cells, so each color $A$ token maps to a color $A$ cell within $2$ away from either 1) its original cell, 2) the cell of the color $B$ token it went to, or 3) the cell of the color $C$ token that went to it under the permutation. By Triangle Inequality this is sufficient. We use Hall's theorem. Consider any set $S$ of color $A$ tokens. Its neighborhood consists of the color $A$ cells within $2$ away of either 1) one of the cells that the tokens of $S$ were originally on, 2) the cells that the tokens of $S$ went to, or 3) the cells that had tokens that went to the cells that the tokens of $S$ were originally on. Each of these three groups are disjoint since they contained different colored tokens. They have $|S|$ cells each, so they consist of $3|S|$ different cells. Subdivide the board into $1\times 3$ rectangles. At least $|S|$ rectangles must have at least one of the cells of our three groups defined above. Each rectangle has a color $A$ cell, and this cell is within $2$ away from any cell in the rectangle. So the color $A$ cells in these rectangles are in the neighborhood, and there are at least $|S|$ of them, done. $\blacksquare$

Actual knowledge check We proceed by Hall's marriage lemma. Notice for any set of red tokens, it is at most $\frac{1}{3}$ of its $d$ neighborhood since there is an equally large set of green and blue tokens in the $d$ neighborhood. Furthermore, by looking row-wise and summing, the set of red squares in the $d+2$ neighborhood of the red tokens is at least $\frac{1}{3}$ the size of the $d$ neighborhood in all cases. Thus, we are done.

By the condition, it follows that each token is within $d$ of some uniquely chosen token of both the other colors. Note that we can consider how tokens of each color move separately. Then, for each color individually, consider the bipartite graph between tokens and cells of this same color, with a connection if they are at most within $d + 2$ of each other. Partition the square into $1 \times 3$ tiles. For each token of this color, it is within $d + 2$ of the two earlier uniquely chosen tokens and itself. Hall's condition holds for any subset $|V|$ as then we have $3 \cdot |V|$ unique tokens which fill at least $|V|$ tiles, and then if a tile has a token then the token is within $2$ of the same color.

Love this, it's a wild problem that pushes Hall to its extremes (and it's somehow not trivial by Hall either.) We will construct a perfect matching between $1 \times 3$ rectangles in the grid and asparagus tokens such that we may move any matched asparagus token into its corresponding $1 \times 3$ rectangle in at most $d$ moves. Because every such $1 \times 3$ rectangle contains exactly one asparagus square, we will be able to move the asparagus token there in $d+2$ moves, which solves the problem. In particular, it suffices to verify Hall's condition: in other words, for any $k$ $1 \times 3$ rectangles, there must exist at least $k$ asparagus tokens that are within a distance $d$ of one of the rectangles. However, observe that within the $3k$ squares present within these rectangles, there must exist $k$ that are the same color $c$. If this color is asparagus, we're done immediately; if it is byzantium or citrine, by assumption, there exists a sequence of moves transferring $k$ distinct asparagus token onto these $k$ byzantium or citrine tokens such that each token is moved a distance of at most $d$. This completes the proof.