Plumbing Random Paths

CJam, 274

q~:K;:B;:A;{0aA*aB*:M5*5f*:I;K{[Bmr:QAmr:P]5f*:R;3Ym*{R.+:)2{1$0=I=2$W=@tI@0=@t:I;}:F~}/R2f+1FK({MQ=P=:EY4mr:D#&1{{MQMQ=PE2D#+tt:M;}:G~7,1>[W0_1_0_W]2/D=:Off*{[QP]5f*2f+.+_:H1F_OW%.+2FOW%.m2F}/H2FO~P+:P;Q+:Q;MQ=P=:E_5YD2%-*=!JK2-=+*1{D2+4%:D;G}?}?}fJ]}0?}g'P2NA5*SI,N2NI:+N*

Try it online

Uses PBC, outputs in PGM format. You can remove the :+ near the end to get a nicer visual output in the browser.

It's very slow for larger input, especially if the step count is close to the area.

Example result for input 4 3 10 (scaled 500%):

Brief explanation:

The general approach is:

• repeat all the following steps until successful:
• initialize 2 matrices: one recording which sides are being used in each cell, and one for the image
• if s=0, we're done, else:
• pick a random cell and draw a square, then do the following s-1 times:
• pick a random direction; if that side is already used, fail and start over
• mark the side as used and draw the actual pipe in the image (drawing 3 adjacent lines of length 6, starting right "after" the center pixel of the current cell, then adding a dot to cap the end of the pipe)
• update the current position (moving to the next cell)
• check if the cell is empty or it's a valid crossing; if not, fail and start over
• mark the side in the opposite direction as used in this cell, then continue the loop

QBasic, 517 516 bytes

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
1CLS
IF s=0GOTO 9
x=5*INT(RND*w)
y=5*INT(RND*h)
GOSUB 7
FOR k=1TO s-1
r=INT(RND*4)+1
a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)=0GOTO 1
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
9IF c GOTO 1
END
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN

• Takes w, h, and s from user input, comma-separated.
• Output is drawn on the screen. While the program is searching for a solution, you may see partial solutions flickering past.
• Does not use periodic boundary conditions. I found it easier to draw and test for connecting pipes without having to worry about half of the pipe being on one side of the grid and half on the other.

The approach here is to try a random direction at each step and start over from the beginning if it results in an invalid move. We draw the pipes as the directions are decided, and use POINT to test points on the screen for our validity conditions. A move is valid if it doesn't go outside the boundaries of the grid and:

1. The moved-to cell is empty; or
2. Both
   1. The moved-to cell contains a pipe going straight through, either horizontally or vertically, and
   2. The new pipe section does not double up an existing pipe section

Like aditsu's CJam answer, this code is very slow, and can be mind-numbingly slow if s is a significant fraction of w*h. On my QB64 setup, it comes up with an answer for 5,5,19 fairly promptly, but takes longer than I was willing to wait on 5,5,20.

If you want to run larger/more densely packed examples, here's my original approach using a depth-first search. It's much more efficient, at the cost of a whopping 300 extra bytes.

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
DIM t(s),m(s)
0
FOR z=1TO s
t(z)=-1
NEXT
i=5*INT(RND*w)
j=5*INT(RND*h)
k=1
1CLS
IF s=0GOTO 9
x=i
y=j
GOSUB 7
FOR z=1TO k-1
r=m(z)
GOSUB 6
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
IF c*(k=s)THEN k=k-1:GOTO 1 ELSE IF k=s GOTO 9
IF k<1GOTO 0
IF t(k)>=0GOTO 4
t(k)=0
f=30
WHILE f
r=INT(RND*4)+1
IF f AND 2^r THEN t(k)=t(k)*5+r:f=f-2^r
WEND
4r=t(k)MOD 5
m(k)=r
t(k)=t(k)\5
GOSUB 6
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)THEN k=k+1 ELSE IF t(k)>0GOTO 4 ELSE t(k)=-1:k=k-1
GOTO 1
6a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
RETURN
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN
9

Example output for inputs 10, 10, 100, actual size:

A still fancier version can be found in this gist. Besides being ungolfed and thoroughly commented, it scales up the output by a constant factor and allows for a set delay between steps, enabling you to watch the DFS algorithm at work. Here's an example run: