18
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Sandboxed: codegolf.meta.stackexchange.com/a/17888/11261 \$\endgroup\$ – Jordan Aug 2 at 15:10
  • 1
    \$\begingroup\$ @Arnauld You're correct; it's not valid. A meander is a single closed path. \$\endgroup\$ – Jordan Aug 2 at 19:32
  • 1
    \$\begingroup\$ @Arnauld Thanks, I’ve made that change. I didn’t realize MathJax was enabled on this site! \$\endgroup\$ – Jordan Aug 3 at 18:57
11
\$\begingroup\$

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)

Results

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)
\$\endgroup\$
  • \$\begingroup\$ Nice work. I'd love to read an explanation of the code. \$\endgroup\$ – Jordan Aug 2 at 19:44
  • \$\begingroup\$ @Arnauld are you brute-forcing it or using another algorithm? \$\endgroup\$ – Jonah Aug 2 at 22:10
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Arnauld Aug 2 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.