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

2 Answers 2

Reset to default
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)
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Nice work. I'd love to read an explanation of the code. \$\endgroup\$ Commented Aug 2, 2019 at 19:44
  • \$\begingroup\$ @Arnauld are you brute-forcing it or using another algorithm? \$\endgroup\$ Commented Aug 2, 2019 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\$ Commented Aug 2, 2019 at 22:15
2
\$\begingroup\$

Python3, 1171 bytes

Long, but fast.

P=[[(1,3)],[(2,4)],[(1,2)],[(2,3)],[(3,4)],[(4,1)],[(1,2),(3,4)],[(2,3),(4,1)]] M={1:(3,0,-1),3:(1,0,1),2:(4,-1,0),4:(2,1,0)} E=enumerate def G(d): q=[i for i in d if d[i]] while q: v=q.pop(0) Q,S=[(*v,0,[])],[v] for x,y,H,p in Q: for j in P[d[(x,y)]-1]: if not H or H in j: for J in j: e,X,Y=M[J];U=(x+X,y+Y) if d.get(U,-1)>0 and([]==p or U!=p[-1]): if p and U==p[0]:return p+[(x,y)] Q+=[(*U,e,p+[(x,y)])];S+=[U] q=[*{*q}-{*S}] def V(d): for x,y in d: if d[(x,y)]: for j in P[d[(x,y)]-1]: for J in j: e,X,Y=M[J];U=(x+X,y+Y) if U not in d:return if d[U]==0:continue if not any(e in u for u in P[d[U]-1]):return return 1 def f(b): q=[{(x,y):v for x,r in E(b)for y,v in E(r)}] for d in q: if(L:=G(d)): if len({*L})!=len(d):continue return d D={} for x,y in d: if d[(x,y)]==0: for I,A in E(P,1): T=eval(str(d));T[(x,y)]=I if V(T):D[(x,y)]=D.get((x,y),[])+[I] if D: t=min(map(len,D.values())) k=[i for i in D if len(D[i])==t] if t==1: T=eval(str(d)) for i in k:T[i]=D[i][0] q+=[T] else: for I in D[k[0]]:T=eval(str(d));T[k[0]]=I;q+=[T]

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 1109 bytes \$\endgroup\$ Commented Jul 26 at 20:03

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.