Generate all solvable 2xN mazes

Question

Your job is to write a program that takes a number N as input and outputs all 2-by-N mazes that are solvable.

Output format can be in the form of any two distinct values representing wall and empty - I use x and . here but you can use anything. You can have a matrix, array, string, ascii art, whatever is convenient, and it can be horizontal, as shown in my examples, or vertical.

A maze is solvable if it has a path of empty cells (represented here as .) from the left end to the right end. For example,

xxxx.....
.....x..x

is solvable, because you can trace a path (marked with O):

xxxxOOOOO
OOOOOx..x

But this is not.

xxx.x..
..xxx..

You cannot pass through diagonal gaps, so this is also not:

xxx...
...xxx

Testcases

1:

.
. 
 
.
x

x
.

2: 

..
..

..
.x

.x
..

..
x.

..
xx

x.
..

xx
..

Answer 1

Excel, 163 143 bytes

=LET(a,BASE(SEQUENCE(3^A1)-1,3,A1),b,FILTER(a,ISERROR(FIND(12,a))*ISERROR(FIND(21,a))),SUBSTITUTE(b,2,0)&"
"&SUBSTITUTE(SUBSTITUTE(b,1,0),2,1))

Use 1 for walls and 0 for empty cells.

Original

=LET(a,BASE(SEQUENCE(3^A1)-1,3,A1),b,FILTER(a,ISERROR(FIND(12,a))*ISERROR(FIND(21,a))),SUBSTITUTE(SUBSTITUTE(b,1,"X"),2,0)&"
"&SUBSTITUTE(SUBSTITUTE(b,2,"X"),1,0))

Uses 0 for empty cells and X for walls.

Link to Spreadsheet

Answer 2

C (gcc), 192 190 188 bytes

• Saved two bytes thanks to ceilingcat using ++u<=\$\iff\$u++< and puts("")'s return value of 1 (i.e. the number of printed bytes).
• Saved two bytes thanks to ceilingcat; transforming (a=L>>_+o&1)|(b=L>>o++&1)||(l=v=0),l|=a,v|=b; into v=(a=L>>_+o&1)|(b=L>>o++&1)?l|=a,v|b:(l=0); which when naming the major equivalent segment @ becomes @||(l=v=0),l|=a,v|=b; and v=@?l|=a,v|b:(l=0);.

s,o,l,v,a,b,L;e(_){for(L=0;L++<1<<2*_;s||puts("")){for(l=v=o=s=0;o<_;s|=l&v)v=(a=L>>_+o&1)|(b=L>>o++&1)?l|=a,v|b:(l=0);for(l=0;l/2<!s;l+=puts(""))for(o=0;o<_;)putchar(46+(L>>l*_+o++)%2);}}

Try it online!

---

Uses . as a path character and / as a wall character. Requires n < 16 assuming an int is 32 bits wide and can thus hold 2*n +1 bits. Due to this problem's combinatorial nature, this restriction should be of little hindrance. Else one may need to consider 128 bit systems.

If one was to allow barely printable characters like tab (ASCII 9) and newline (ASCII 10 = 9+1), one could save a byte by substituting s!46+!9+!. Even more extremely, outputting literal zeroes and ones, s!46+!! would save three bytes.

Answer 3

05AB1E, 12 11 bytes

Returns a list of mazes where each maze is a list of 2×1 slices. 0's are walls.

T2ãIãʒ∊ü&PĀ

Try it online! Footer prints mazes horizontally.

Same idea as my APL answer, for each 2×2 submaze check if it is solvable (contains 11 in the top or bottom row).

Commented:

T            # push integer / string 10
 2ã          # all pairs of 1/0
   Iã        # all n-tuples of pairs of 1/0
             # each n-tuple represents a 2×n maze
     ʒ       # filter the mazes on:
      ∊      #   extend the maze by mirroring (for n=1)
       ü&    #   bitwise and of adjacent maze slices 
         PĀ  #   is the product not equal to 0?

Answer 4

Vyxal, 109 84 bytes

\0⅛\1⅛\2⅛?(¾3n›e(¼_)ƛ0+⅛_nt0=[n›⅛n2+⅛|nt1=[n›⅛|n2+⅛]])ƛ\0`00
`øṙ\1`01
`øṙ\2`10
`øṙ;⁋

My first Vyxal answer, which is probably why it's so bad.

-25 bytes thanks to lyxal.

Try it Online!

Answer 5

Python 3, 91 83 bytes

Returns a list of lists of strings with characters . and x.

f=lambda n,*d:[[]][n:]or[w+[x]for x in{'.x','x.'}^{*d,'..'}for w in f(n-1,x[::-1])]

Try it online! The output is vertical.

Answer 6

JavaScript (Node.js), 78 bytes

f=n=>n?f(n-1).flatMap(a=>(g=eval(a+=`
`))%22?[a+22,a+g]:[a+12,a+21,a+22]):['']

Try it online!

2 as path, 1 as wall

JavaScript (Node.js), 88 bytes

f=n=>n?f(n-1).flatMap(a=>(g=a.slice(0,2),g%11?[11,g]:['01',10,11]).map(_=>_+`
`+a)):['']

Try it online!

1 as path, 0 as wall

Answer 7

Haskell, 66 bytes

(d%)
r%0=[[]]
r%n=[h:t|h<-max[d,"x.",".x"][r,d],t<-h%(n-1)]
d=".."

Try it online!

Answer 8

Charcoal, 39 bytes

ＮθＥΦＥＸ³θＥ◧⍘ι³θΣλ⬤ι⁻³∧μ⁺λ§ι⊖μＥ²⭆ι§.x⁼⊕λν

Try it online! Link is to verbose version of code. Explanation: Represents mazes internally as a list of digits, 0 = no walls, 1 = upper wall, 2 = lower wall. (3 would be an impossible maze, of course.)

Ｎθ                                      Input `N` as a number.
    ＥＸ³θ                                Map over potential mazes
        Ｅ◧⍘ι³θΣλ                         Split into lists of walls
   Φ                                     Filter over mazes where
                ⬤ι                      All columns satisfy
                  ⁻³∧μ⁺λ§ι⊖μ            Consecutive sums do not total 3
  Ｅ                                     Map over filtered mazes
                            Ｅ²          Map over each row
                              ⭆ι        Map over the maze and join
                                §.x⁼⊕λν Select wall or space
                                        Implicitly print

Answer 9

J, 43 bytes

[:(#~(0=&#.*&(2#.\0,]))/"2)-]\"#.2#:@i.@^+:

Try it online!

Answer 10

Jelly, 11 bytes

4ṗ’Ḋ&ƝP$Ƈd2

A monadic Link accepting a positive integer that yields a list of lists of pairs where 0 represents a wall and 1 represents space.

Try it online!

How?

4ṗ’Ḋ&ƝP$Ƈd2 - Link: integer, n
4           - four
 ṗ          - ([1,2,3,4]) Cartesian power (n) -> all n-tuples made from alphabet [1,2,3,4]
  ’         - decrement -> all n-tuples made from alphabet [0,1,2,3] (first is all zeros)
   Ḋ        - dequeue (remove the first, to make the rest work when n=1)
        Ƈ   - filter keep those for which this is truthy (non zero):
       $    -   last two links as a monad - f(potential):
     Ɲ      -     for neighbours:
    &       -       bitwise AND
      P     -     product
         d2 - div-mod two (vectorises)

Answer 11

APL (Dyalog Unicode), 47 40 43 bytes

Assumes ⎕IO←0, 0's are walls.

-7 bytes inspired by this answer.
-4 bytes thanks to Razetime! (Commute ⍴ to save on parenthesis, replicate first ⌿ instead of replicate along the first axis /[0])

{(⌊/⌈/[1]2⌊/x,⌽x)⌿x←(2*2×⍵)2⍵⍴↑⍳2⍴⍨2×⍵}

Try it online!

⌊/⌈/[1]2⌊/x,⌽x is checking if a maze is solvable, everything else is just generating and filtering all mazes.

Answer 12

Haskell, 80 bytes

f n=[m|m<-mapM(["..","x.",".x"]<$f)[1..n],all(<"xx").z(z max)m$tail m]
z=zipWith

Try it online!

Takes n as input, returns the list of all the \$2\times n\$ solvable mazes; each maze is represented as a list of list of characters, where . is an empty cell and x is a wall.

Haskell, 81 bytes

f 1=pure<$>g e
f n=[x:h:t|h:t<-f$n-1,x<-g h]
g".."=[e,"x.",".x"]
g s=[e,s]
e=".."

Try it online!

Recursive version.

Answer 13

JavaScript (V8), 101 bytes

Prints all solutions, with 0 = empty and 1 = wall.

n=>{for(i=q=1<<n;i--;)for(j=q;j--;)i&(j|j*2|j/2)||print((g=n=>n--?[i>>n&1]+[j>>n&1]+`
`+g(n):'')(n))}

Try it online!

Answer 14

Haskell, 75 bytes

A port of my Python answer.

(!"")
0!_=[[]]
n!d=[x:w|x<-"..":[w|w<-[".x","x."],w/=d],w<-(n-1)!reverse x]

Try it online!

Answer 15

Pip -P, 39 bytes

Y3**a[01t00]@^_MtNI_.RV_FI@>(_TB3)My+,y

Outputs each maze as a list of 2x1 slices, where 0 is a space and 1 is a wall. Try it online!

Here's a version with nicer output: Try it online!

Explanation

Observing that a slice with both walls (11) is no good, we try all combinations of slices 00, 01, and 10, with the further rule that 01 and 10 cannot be adjacent.

I tried using Cartesian product at first, but found that abusing base conversion was shorter.

Y3**a[01t00]@^_MtNI_.RV_FI@>(_TB3)My+,y
                                         a is command-line arg; t is 10 (implicit)
Y3**a                                    Yank 3 to the power of a into y variable
                                   y+,y  Range from y to 2*y
                                  M      For each number in that range:
                             _TB3         Convert to base 3
                          @>(    )        Remove the leading 1
                                         We now have a list of all strings of 0,1,2
                                         whose length equals the input number
                                         0 represents a slice with a wall in the
                                         lower half, 1 with a wall in the upper half,
                                         and 2 a slice with no walls.
                        FI               Filter that list on this function:
                t                         10
                 NI                       is not a substring of
                   _.RV_                  the string concatenated to its reverse
               M                         For each string in the remaining list:
             ^_                           Split it into digits
     [01t00]@                             and use each digit to index into the list
                                          [01;10;00]

Answer 16

Zsh -F, 57 bytes

eval for\ {1..$1}\ (01 10 00) 'grep -Ev "1 1|10 01"<<<$@'

Try it online!

Outputs as a space-separated list of pairs of characters, with 1 representing walls and 0 representing gaps.

• for\ {1..$1}\ (01 10 00): construct the string for 1 (01 10 00) for 2 (01 10 00) for 3 (01 10 00) ... for n (01 10 00)
• evaluate that string, which is n nested for-loops using the loop variables 1 to n, creating all the combinations of 01 10 00 (so all possible mazes)
• <<<$@ - print all the variables numbered 1 to n separated by spaces
• grep -Ev "1 1|10 01" - filter out combinations which match either 1 1 or 10 01 (i.e., diagonal walls)