Generate net puzzles

Question

An acyclical grid is a mapping of an acyclical graph (that is, a tree) where each node has no more than four edges onto a toroidal rectangular grid such that each cell of the grid is occupied by a node. Here is an example of an acyclical grid:

┴─┐╵╵│└┘└╴╶┴┬
╴╷╵┌┐│╷┌┬┐╶┐├
╷│╷╵│├┘│╵└╴│╵
┘└┴┐│└┬┤┌─┬┴─
╷╶─┤│╷╵├┤╶┘╶┐
│╶┐└┤└┬┤╵╷╶─┤
┤╷└─┴┬┤└┐└┬┬┴
│├──┐│├╴├─┤├╴
┘└┐┌┴┤└┐├╴╵╵┌
┌┬┘╵┌┴┐╵└─┐╶┘
┤└─┐│╷│┌┬╴╵╷╶

^{Some browser fonts have trouble rendering this in a properly monospaced way. If the grid looks off, please copy-paste it into a text editor of your choice.}

Notice that this grid is toroidal: the left and right, as well as the top and bottom are connected preserving the axis you are moving along. For example, if you move left in the third row you eventually end up on the right of the third row and vice versa.

This grid is composed of box-drawing characters which fall into four classes:

1. The characters ╵ , ╶, ╷, and ╴ denote leaves (nodes with one edge)
2. The characters │ and ─ denote nodes with two edges in a collinear arrangement
3. The characters ┴, ├, ┬, and ┤ denote nodes with three edges
4. The characters └, ┌, ┐, and ┘ denote nodes with two edges in a perpendicular arrangement

The characteristic matrix of an acyclical grid is a matrix comprising for each cell in the acyclical grid the class of the node positioned there. For instance, the characteristic matrix of the aforementioned grid is this:

3241124441133
1114424232123
1211234214121
4434243342332
1123211331414
2144343311123
3142333444333
2322423131331
4444334431114
4341434142414
3424212431111

A net puzzle is an n × m matrix of integers in the range from 1 to 4 such that it is the characteristic matrix of exactly one acyclical grid.

If you want to gain an intuitive understanding about net puzzles, you can play net from Simon Tatham's puzzle collection. Make sure that “wrapping” and “ensure unique solution” are both checked and that “barrier probability” is set to 0.

The challenge

Write a function or program that given two integers n and m in the range from 3 to 1023 generates a net puzzle of dimension n × m. You may optionally receive a third integer p in the range from 1 to 1023.

If you implement the variant with two arguments (the non-deterministic variant), then your submission shall with great probability return a different puzzle each time it is called. If you implement the variant with three arguments (the deterministic variant), then the set of puzzles generated for all p for a given pair (n, m) shall contain at least four different puzzles for each pair (n, m).

There are no further restrictions with respect to input and output.

Scoring

This challenge is code golf. The solution with the least number of octets wins.

Answer 1

K (ngn/k), 38 bytes

{((x,y)#&(0;y;y*x-2;y-2;2))z|:/x!z+!x}

Try it online!

I can't believe that it went unanswered for, like, six and a half years?

Implements the three-argument version. It is a function that takes n m p as three separate parameters and builds a valid net puzzle deterministically.

Basically what it does is to build one asymmetric and easily constructible net puzzle of size n m, and then permute its rows based on p.

What it builds & Why it is valid for this challenge

The result for f[5;6;0] is this:

1 1 1 1 1 1
2 2 2 2 2 2
2 2 2 2 2 2
2 2 2 2 2 2
3 3 3 3 4 4

In box drawing chars:

1 1 1 1 1 1 : ╷╷╷╷╷╷
2 2 2 2 2 2 : ││││││
2 2 2 2 2 2 : ││││││
2 2 2 2 2 2 : ││││││
3 3 3 3 4 4 : ┴┴┴┴┘└

And it has a unique solution, as well as its reflections and rotations (as in APL sense; cyclically moving rows and columns).

Why unique solution? First, the solution is an unrooted tree (in graph-theoretical sense); if a configuration has a cycle, then it is not a solution because it necessarily has two or more disjoint parts. Then, the 2's must be all aligned either horizontally or vertically, but if they're horizontal then they form one or more cycles of their own. So they must be vertical. Then the orientation of 1's are fixed (downwards), and then the 3's (disconnected to the lower side). Finally the orientations for 4's are fixed in order to connect everything.

The code is easy:

&(0;y;y*x-2;y-2;2)    Create an array of:
                      m copies of 1's, m*(n-2) copies of 2's,
                      (m-2) copies of 3's, and 2 copies of 4's
(x,y)#                Reshape into n-row, m-col matrix

For "at least four distinct puzzles" part, I had to use two different permuting methods because of the 3x3 grid (single reflection gives at most 2; stepwise rotation gives at most either n or m). I went for pure row permutation because applying two separate transforms was too long.

For code, !x creates the identity permutation vector 0 1 2 ... (n-1), x!z+ rotates it by p steps, and z|:/ reverses it p times. This creates lcm(2, n) unique grids, which is always at least 4.

I know, it's likely against the original intent of the challenge, but this is not the first time I exploited "generate at least x distinct grids" :P