[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]
# 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](https://1drv.ms/x/s!AkqhtBc2XEHJnBsMSryudqTL8Nd4?e=Mw1dW8)
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~192~~ ~~190~~ 188 bytes
* Saved two bytes thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/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](https://codegolf.stackexchange.com/users/52904/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!](https://tio.run/##jY/BUsIwEIbvPkXsDEzSBFJiRWwbvHlw@gjOMGkIpWNIsAlVx/LsNQgjV4@7/37f7spJLeVAY/BijfBbYcBzq@SWAJaw2SRJJ3cJiOlNGLg2MiBVoxtTS@EB3Hq/dxml0q5VbfVm6ryQb@pTBlmtptLu6MGp1tF79pik9Ioi4ESn1sB/WFB9eeUui/4hfKeMpQ/zRSAGRyzRpCOCVKTMFVyh741tYcmTvMS4mBUFi1e56/v9wTsYReica95xy12YssUp5nrcoY5DwcvlcoXteIZ6WJ0Ki3EonnTPBen6KgtogvKzI8k1ZcWtyzXmf/5TZC9iFLrh8BamcwyDTMfBjTEaMZQfj8NONAaa34sANIHB2BSL8IVBaN82xm9gZAAHo3X2aiJiAjT8AA "C (gcc) – 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]
# [05AB1E](https://github.com/Adriandmen/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!](https://tio.run/##AS0A0v9vc2FiaWX//1Qyw6NJw6PKkuKIisO8JlDEgP99dnnigqxTw7hKwrssIiIs/zI "05AB1E – 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]
# [Vyxal](https://github.com/Lyxal/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!](http://lyxal.pythonanywhere.com?flags=&code=%5C0%E2%85%9B%5C1%E2%85%9B%5C2%E2%85%9B%3F%28%C2%BE3n%E2%80%BAe%28%C2%BC_%29%C6%9B0%2B%E2%85%9B_nt0%3D%5Bn%E2%80%BA%E2%85%9Bn2%2B%E2%85%9B%7Cnt1%3D%5Bn%E2%80%BA%E2%85%9B%7Cn2%2B%E2%85%9B%5D%5D%29%C6%9B%5C0%6000%0A%60%C3%B8%E1%B9%99%5C1%6001%0A%60%C3%B8%E1%B9%99%5C2%6010%0A%60%C3%B8%E1%B9%99%3B%E2%81%8B&inputs=3&header=&footer=)
[Answer]
# [Python 3](https://docs.python.org/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!](https://tio.run/##PcpBCoMwEIXhvaeY3Zg0BsRdIFfwAmkKKTFUqKNEwbTSs6eGQneP/3vLa3vM1OUc9NNNd@@ABPfKGGsNKTtHs19MsmGOkGCkA2VCgUni53ZwL1Ceq@B@IoSamlYko1TTWmZzDxq6qvDk3sPv0TNVASxxpK3mJQtYh0XjlZD9geUv "Python 3 – Try It Online") The output is vertical.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 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!](https://tio.run/##FcxBCoMwEEDRfe9RnCFVyHSnTDxBTyBBB5uElphIFa@f6ubzVv8rh2zz77PudcpvV4rnxCb1HlKtsfFR9pesIGwgsDskgiiebhPinagfRBE9RAXbntQXSV8hi@1QVbZ0Hp7YLOdiZDPntOXompgDjIhd@QM "JavaScript (Node.js) – Try It Online")
2 as path, 1 as wall
# [JavaScript (Node.js)](https://nodejs.org), 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!](https://tio.run/##PctBCsMgEADAe/9RdIkRt701aF7QFwQxi1VJMRqa0O/bnHoe5k1f2v1n2Y6@1FdoLeqiTRkjLz2CjJmOJ22ctOFJk9zz4gNX4gYiXRHHCVEk@5iYQiZQCUQLcj2D08Z182XuCOBkZtsQ@f1vvpa95iBzTdwBDO0H "JavaScript (Node.js) – Try It Online")
1 as path, 0 as wall
[Answer]
# [Haskell](https://www.haskell.org/), 66 bytes
```
(d%)
r%0=[[]]
r%n=[h:t|h<-max[d,"x.",".x"][r,d],t<-h%(n-1)]
d=".."
```
[Try it online!](https://tio.run/##Fco9DsIgGADQvaf4QmwC4Sc2bqZ4Ap0cHCgDKVYaaSUUE2o8u6jbG54zy/3qfRlkV7CtSRXrrVRK6x9mqdw@vV3LJ5OVZSgLxJDISKvIrGap5a7GM2@IrqxEQqAymXGWkwknCM90TvE4wwaGh7exAfwaw2VMDnCXYeWHTCkCQJSuhPwX7MqnH7y5LYX3IXwB "Haskell – Try It Online")
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 39 bytes
```
ＮθＥΦＥＸ³θＥ◧⍘ι³θΣλ⬤ι⁻³∧μ⁺λ§ι⊖μＥ²⭆ι§.x⁼⊕λν
```
[Try it online!](https://tio.run/##RY3BDoIwEETvfkXDqU2qBzlywqgJiRgSvqBC1SbbBUqr/H3dyoE9zUzm7XRv5bpBQYwVjsHfg31oxydR7Bpn0PNajfxqwFOYZDN8SeWSTUKyf6D6m356flKzbj0hL24ky8XaaIPlIEiUACmvDYY54SX23ErWAFkg6yvs9ZIqZ905bTV6TQ2x3jp1pH//hWTMBmWHJZPsMgUFM69ww4FAXD8UMeZx/4Ef "Charcoal – 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]
# [J](http://jsoftware.com/), 43 bytes
```
[:(#~(0=&#.*&(2#.\0,]))/"2)-]\"#.2#:@i.@^+:
```
[Try it online!](https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/o600lOs0DGzVlPW01DSMlPViDHRiNTX1lYw0dWNjlJT1jJStHDL1HOK0rf5rcqUmZ@QrpCkYQhjqurq66jAx4/8A "J – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 11 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
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!](https://tio.run/##ASUA2v9qZWxsef//NOG5l@KAmeG4iibGnVAkxodkMv/Dh8WS4bmY//8y "Jelly – 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]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~47~~ ~~40~~ 43 [bytes](https://github.com/abrudz/SBCS)
Assumes `⎕IO←0`, `0`'s are walls.
-7 bytes inspired by [this answer](https://codegolf.stackexchange.com/a/165670/64121).  
-4 bytes thanks to [Razetime](https://codegolf.stackexchange.com/users/80214/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!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/6s1HvV06T/q6dCPNow1ArErdB717K3QfNSzvwKoQsNIy@jw9Ee9WzWNgMSj3i2P2iY@6t1sBGL1roBI1f5PA6p81Nv3qKv5Ue8aoNSh9cYgdX1Tg4OcgWSIh2fw/zQFIwA "APL (Dyalog Unicode) – Try It Online")
`⌊/⌈/[1]2⌊/x,⌽x` is checking if a maze is solvable, everything else is just generating and filtering all mazes.
[Answer]
# [Haskell](https://www.haskell.org/), 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!](https://tio.run/##NY2xCsIwFEX3fMUjdEigDYhr2i/QycGhFHnQ1gbznqFGCMF/j63gcofD5ZwFX4/J@1Jm4LanD9mGMJxVL42RtUz7mCQHW826PxjDQ43eKytTktpklYEwaaoiOg80iNxmF64uLoXQcTs@BbBt1gnHEwsIq@No/MT3uFRbUcAeuynVdeEdL3E9sdy0Pwh/ovdnOX4B "Haskell – 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](https://www.haskell.org/), 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!](https://tio.run/##Nc2xCoMwFAXQPV/xeDgomIB0k8QvsFNHkRIwJlJ9DTFChv57qoUOdzn3wnV6f5l1zXmGRvkjGFl0FgybgdSQWtfGzxnJ54J4UyfJLbiRWRQC1WBqTAJrFAlPg/2SfWRGXXXe9EJqejMgyYPRU08MfFgoitWQja44Pxhs2t@fZdl1/oiPGHpCrMQP4S/Vtcy3Lw "Haskell – Try It Online")
Recursive version.
[Answer]
# [JavaScript (V8)](https://v8.dev/), 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!](https://tio.run/##LYtBCoNADEX3PYgmlVC0m9Ix04NIQSmMJItUR3HT6dmnCl399x58HbZheUWZVtpuOXA29p/wjiA8c9225oTI4VGUZ6eHSAGa9NwkvTSY0hTFVoCR96sRPTrx3or6WXX6h/7UVyMY3ssS98FvDnDF/AM "JavaScript (V8) – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), 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!](https://tio.run/##DcQ9DsIgGADQvacoXxwgKfgzNnADnRyRNKQFbaSEQCsMPbvoG95Lp7dxrlrxqBgBkOaEBiGlUo1Hk5Clz3vhFBiDXuY9cyqBFeigMFBdPorpP6fY0zNB0XxMTKYtqi569mLR4TbgsK33NV4927ybvUnkYNtL/Y7W6WeqdAzhBw "Haskell – Try It Online")
[Answer]
# [Pip](https://github.com/dloscutoff/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!](https://tio.run/##K8gs@P8/0lhLKzHawLDEwCDWIS7et8TPM14vKCzezdPBTiM@xMlY07dSW6fy////ugH/jQE "Pip – Try It Online")
Here's a version with nicer output: [Try it online!](https://tio.run/##K8gs@P8/0lhLKzEy2sCwxMAg1iEu3rfEzzNeLygs3s3TwU4jPsTJWNO3Ulun8r9bbqVCNZdCgEJULpCs4Kr9/183578xAA "Pip – 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]
# [Zsh](https://www.zsh.org/) `-F`, 57 bytes
```
eval for\ {1..$1}\ (01 10 00) 'grep -Ev "1 1|10 01"<<<$@'
```
[Try it online!](https://tio.run/##qyrO@F@cWqKg66Zg/D@1LDFHIS2/KEah2lBPT8WwNkZBw8BQwdBAwcBAU0E9vSi1QEHXtUxBCShWAxI1VLKxsVFxUP//HwA "Zsh – 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)`
* `eval`uate 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)
]