# Complete the grid-filling meander

A grid-filling meander is a closed path that visits every cell of a square $$\N \times N\$$ grid at least once, never crossing any edge between adjacent cells more than once and never crossing itself. For example:

Once filled, each cell of the grid can be represented by one of the following 8 tiles:

Numbered this way, the tiles of the above meander can be represented by this matrix:

5 6 5 6
4 8 3 2
5 7 6 2
4 3 4 3


Your task is to complete a grid-filling meander given an incomplete set of tiles. For example, the incomplete meander:

...which can be represented using 0s for missing tiles:

5 0 0 0 6
0 0 7 0 0
0 0 0 0 3
2 4 0 0 0
0 0 3 0 0


...could be completed like this:

...i.e.:

5 6 5 1 6
4 8 7 6 2
5 7 7 7 3
2 4 8 8 6
4 1 3 4 3


### Specifications

• The input will always have at least $$\1\$$ and at most $$\N^2\$$ (non-empty) tiles, where $$\2 \le N \le 7\$$.
• You may use any set of values to represent the tiles, as long as it's specified in your answer.
• Your input and output may be in any format and order, as long as it's specified in your answer.
• At least one valid solution will exist for all inputs (i.e. you don't need to handle invalid input).
• Standard I/O rules apply.
• Standard loopholes are forbidden.
• Explanations, even for "practical" languages, are encouraged.

### Test cases

Input (Θ):

0 6
0 0


Output (Θ):

5 6
4 3


Input (Θ):

5 6 5 6
4 0 3 2
5 7 6 2
4 3 4 3


Output (Θ):

5 6 5 6
4 8 3 2
5 7 6 2
4 3 4 3


Input (Θ):

5 0 0 0 6
0 0 7 0 0
0 0 0 0 3
2 4 0 0 0
0 0 3 0 0


Output (Θ):

5 6 5 1 6
4 8 7 6 2
5 7 7 7 3
2 4 8 8 6
4 1 3 4 3

• – Jordan Aug 2 at 15:10
• @Arnauld You're correct; it's not valid. A meander is a single closed path. – Jordan Aug 2 at 19:32
• @Arnauld Thanks, I’ve made that change. I didn’t realize MathJax was enabled on this site! – Jordan Aug 3 at 18:57

# JavaScript (ES7),  236 ... 193  185 bytes

Outputs by modifying the input matrix.

m=>(g=(d,x,y,v,r=m[y],h=_=>++r[x]<9?g(d,x,y,v)||h():r[x]=0)=>r&&1/(n=r[x])?x|y|!v?n?g(d='21100--13203-32-21030321'[n*28+d*3+7&31],x+--d%2,y+--d%2,v+=n<7||.5):h():!m[v**.5|0]:0)(0,0,0,0)


Try it online!

(includes some post-processing code to print the result both as a matrix and as a flat list compatible with the visualization tool provided by the OP)

## How?

### Variables

$$\g\$$ is a recursive function taking the current direction $$\d\$$, the current coordinates $$\(x,y)\$$ and the number of visited cells $$\v\$$.

The following variables are also defined in the scope of $$\g\$$:

• $$\r\$$ is the current row of the matrix.

r = m[y]

• $$\h\$$ is a helper function that tries all values from $$\1\$$ to $$\8\$$ for the current cell and invokes $$\g\$$ with each of them. It either stops as soon as $$\g\$$ succeeds or sets the current cell back to $$\0\$$ if we need to backtrack.

h = _ => ++r[x] < 9 ? g(d, x, y, v) || h() : r[x] = 0


### Initial checks

We first make sure that our current location is valid and we load the value of the current cell into $$\n\$$:

r && 1 / (n = r[x]) ? ... ok ... : ... failed ...


We test whether we're back to our starting position, i.e. we're located at $$\(0,0)\$$ and we've visited at least a few cells ($$\v>0\$$):

x | y | !v ? ... no ... : ... yes ...


For now, let's assume that we're not back to the starting point.

### Looking for a path

If $$\n\$$ is equal to $$\0\$$, we invoke $$\h\$$ to try all possible values for this tile.

If $$\n\$$ is not equal to $$\0\$$, we try to move to the next tile.

The tile connections are encoded in a lookup table, whose index is computed with $$\n\$$ and $$\d\$$, and whose valid entries represent the new values of $$\d\$$.

d = '21100--13203-32-21030321'[n * 28 + d * 3 + 7 & 31]


The last 8 entries are invalid and omitted. The other 4 invalid entries are explicitly marked with hyphens.

For reference, below are the decoded table, the compass and the tile-set provided in the challenge:

   | 1 2 3 4 5 6 7 8
---+-----------------
0 | 0 - - 1 3 - 3 1          1
1 | - 1 - - 2 0 2 0        0 + 2
2 | 2 - 1 - - 3 1 3          3
3 | - 3 0 2 - - 0 2


We do a recursive call to $$\g\$$ with the new direction and the new coordinates. We add $$\1/2\$$ to $$\v\$$ if we were on a tile of type $$\7\$$ or $$\8\$$, or $$\1\$$ otherwise (see the next paragraph).

g(d, x + --d % 2, y + --d % 2, v += n < 7 || .5)


If $$\d\$$ is invalid, $$\x\$$ and $$\y\$$ will be set to NaN, forcing the next iteration to fail immediately.

### Validating the path

Finally, when we're back to $$\(0,0)\$$ with $$\v>0\$$, it doesn't necessarily mean that we've found a valid path, as we may have taken a shortcut. We need to check if we've visited the correct number of cells.

Each tile must be visited once, except tiles $$\7\$$ and $$\8\$$ that must be visited twice. This is why we add only $$\1/2\$$ to $$\v\$$ when such a tile is visited.

In the end, we must have $$\v = N^2\$$. But it's also worth noting that we can't possibly have $$\v > N^2\$$. So, it's enough to test that we don't have $$\v < N^2\$$, or that the $$\k\$$th row of the matrix (0-indexed) does not exist, where $$\k=\lfloor\sqrt{v}\rfloor\$$.

Hence the JS code:

!m[v ** .5 | 0]


### Formatted source

m => (
g = (
d,
x, y,
v,
r = m[y],
h = _ => ++r[x] < 9 ? g(d, x, y, v) || h() : r[x] = 0
) =>
r && 1 / (n = r[x]) ?
x | y | !v ?
n ?
g(
d = '21100--13203-32-21030321'[n * 28 + d * 3 + 7 & 31],
x + --d % 2,
y + --d % 2,
v += n < 7 || .5
)
:
h()
:
!m[v ** .5 | 0]
:
0
)(0, 0, 0, 0)

• Nice work. I'd love to read an explanation of the code. – Jordan Aug 2 at 19:44
• @Arnauld are you brute-forcing it or using another algorithm? – Jonah Aug 2 at 22:10
• @Jonah I'm currently writing an explanation. Basically, yes, it's a brute-force approach but the algorithm backtracks as soon as some inconsistency is detected rather than trying each and every possible board. – Arnauld Aug 2 at 22:15