text:
Draw an ASCII Checkerboard
Summary
Inspired by the recent popularity of ASCII art challenges, this challenge's purpose is to draw an ASCII checkerboard, like one on which Chess can be played.
Write a program that takes a positive integer n as an argument, in stdin, or as user input, and output an checkerboard with nxn squares, along with a border that is 1 character thick.
Each square should be 2x2 characters. The squares should follow the normal alternating white-black (white first, as in top-left corner) pattern of a checkerboard. White squares should be made out of space () characters, and black squares should be made out of pound (#) characters.
The border should be made out of dashes (-) with a plus (+) on the border or perpendicular point of a square.
Input
Positive integer in representing the number of squares (dimensions in squares) to draw in the checkerboard, with each square being 2x2 characters.
Example Results
n=2
+--+--+
|  |##|
|  |##|
+--+--+
|##|  |
|##|  |
+--+--+

n=3
+--+--+--+
|  |##|  |
|  |##|  |
+--+--+--+
|##|  |##|
|##|  |##|
+--+--+--+
|  |##|  |
|  |##|  |
+--+--+--+

n=4
+--+--+--+--+
|  |##|  |##|
|  |##|  |##|
+--+--+--+--+
|##|  |##|  |
|##|  |##|  |
+--+--+--+--+
|  |##|  |##|
|  |##|  |##|
+--+--+--+--+
|##|  |##|  |
|##|  |##|  |
+--+--+--+--+

... and so on.

Notes

Trailing spaces and new lines are acceptable.
You may write either an entire program or a function.
No leading spaces.
Your program should display correct results for n=15.
For less-known esoteric languages and similar, provide a link to the language.
n=0 should produce +. (optional, but highly recommended and encouraged.)
Shortest code in bytes wins, as this is code golf.

Welcome to Programming Puzzles and Code Golf! Nice work here, especially for your first challenge. I look forward to seeing more of your stuff.

I guess "Your program should display correct results for n=15." means "up to n=15"?

J, 24 bytes
An anonymous function:
2 2&$&.>@(' #'{~2|+/~@i.)

Usage:
   f =: 2 2&$&.>@(' #'{~2|+/~@i.)
   f 4
+--+--+--+--+
|  |##|  |##|
|  |##|  |##|
+--+--+--+--+
|##|  |##|  |
|##|  |##|  |
+--+--+--+--+
|  |##|  |##|
|  |##|  |##|
+--+--+--+--+
|##|  |##|  |
|##|  |##|  |
+--+--+--+--+

&.> is one shorter than each. Worth to note that it works only if BoxForm is set to ASCII.

Python 2, 79
N=3*input()+1
for i in range(N):print('+||- #- #+||-# -# '*N)[3**i%7/2%3:3*N:3]

For each row, selects one of the patterns
+--+--+--+--+--+
|  |##|  |##|  |
|##|  |##|  |##|

and prints 3*n+1 characters from it. The pattern is chosen by repeating its first 6 characters, selected with the string interleaving trick, which also serves to extract a snippet of the correct length.
The correct pattern is selected based the value of the row index i modulo 6 by an arithmetic expression 3**i%7/2%3 that gives the repeating pattern [0,1,1,0,2,2]. I found it using the fact that x**i%7 has period 6, then trying different values of x and different postprocessing to get the right pattern.

CJam, 43 42 bytes
ri3*)_2m*{_3f%:!2b\3f/:+2%(e|"#|-+ "=}%/N*

Try it online.
Each coordinate is mapped to a char, e.g. the top left corner is (0, 0) -> "+". Specifically, we calculate
[(y%3 == 0)*2 + (x%3 == 0)] or [(x//3 + y//3) % 2 - 1]

and index into the string "#|-+ " accordingly.

Pyth, 37
VJh*3Qsm@?+\|*2@" #"+/N3/d3%N3"+--"dJ

Rather hacked together, but short.
Demonstration.

Retina, 106 bytes
1
$_0$_x
1(?=1*0)
+--
1(?=1*x)
s
(0s.*?0)s
$1o
(s\D*?)s
$1o
s
|
o
|##
\D*?x
$0$0
0
+n
x
|n
(.*?n).*
$0$1

Takes input as unary (based on this meta discussion).
Each line should go to its own file and n should be changed to newline in the files. This is impractical but you can run the code as is, as one file, with the -s flag, keeping the n markers. You can change the n's to newlines in the output for readability if you wish. E.g.:
> echo -n 111|retina -s checkerboard|tr n '\n'
+--+--+--+
|  |##|  |
|  |##|  |
+--+--+--+
|##|  |##|
|##|  |##|
+--+--+--+
|  |##|  |
|  |##|  |
+--+--+--+

Further golfing and some explanation comes later.

JavaScript (ES6), 117
n=>Array(n*3+1).fill("+--".repeat(n)+"+").map((v,i)=>v.replace(/./g,(k,x)=>i%3?"|  |##|  "[x%6+(i%6>2)*3]:k)).join`
`

Snippet:

<input type="range" min=2 max=15 step=1 value=1 id="i" oninput="o.textContent=f(this.value)">

Anonymous function. Starts with a full array of +--+--+--... lines, and on appropriate lines, replaces the + for | and - for  or # as appropriate.
The expression that decides the replacement character, "|  |##|  "[x%6+(i%6>2)*3], could probably be golfed further, but I've found that using a longer, redundant string saves more characters than a complex calculation.

CJam, 59 bytes
This .. is .. too .. long ..
ri:I," #"f=2f*_I({__sff^_}*]'|I)*f.\2/Nf*'+I)*"--"*aI)*.\N*

Try it online here

Python 3, 114 108 100
def f(n):
 for i in range(3*n+1):print(("|##|  "*n+"|")[::i//3%2*2-1][:3*n+1]if i%3 else"+--"*n+"+")

Previous solutions
108
def f(n):
 for i in range(3*n+1):
  a=("|##|  "*n+"|")[::i//3%2*2-1][:3*n+1];print(a if i%3 else"+--"*n+"+")

114
def f(n):a="+--"*n+"+\n";b="|  |##"*n+"|";print(a+a.join(([(b[:3*n+1]+"\n")*2,(b[::-1][:3*n+1]+"\n")*2]*n)[:n])+a)

118  (not submitted)
def f(n):
 for i in range(3*n+1):print((("|##|  "*n)[:3*n+1]if i//3%2 else("|  |##"*n)[:3*n+1])if i%3 else"+--"*n+"+")

CoffeeScript with ES6, 106 bytes
f=(n,y=z='+--'[r='repeat'](n)+'+\n')->y+=('|##|  '[r](n).substr(i%2*3,n*3)+'|\n')[r](2)+z for i in[1..n];y

JavaScript (ES6), 111 bytes
Newlines are significant and counted as 1 byte each.
The explicit return made it a bit longer:
f=n=>{for(i=0,y=z='+--'[r='repeat'](n)+`+
`;i<n;)y+=('|##|  '[r](n).substr(++i%2*3,n*3)+`|
`)[r](2)+z;return y}

Demo
At time of writing, Firefox is the only major browser compatible with ES6.

f=n=>{for(i=0,y=z='+--'[r='repeat'](n)+`+
`;i<n;)y+=('|##|  '[r](n).substr(++i%2*3,n*3)+`|
`)[r](2)+z;return y}

// Demonstration related things
document.getElementById('O').innerHTML = f(document.getElementById('n').value);

document.getElementById('n').addEventListener('change', function () {
  document.getElementById('O').innerHTML = f(this.value);
});

<input id=n type=number min=0 step=1 value=6>

<output id=O></output>

CJam, 46 bytes
li3*)_2m*[{_3f/2f%:=\3f%:g+2b"+-|#+-| "=}/]/N*

Try it online
Well, I was hoping that I would at least have an original solution (I normally don't look at other answers before working on my own). Turns out that @Sp3000 had already done something very similar, only better. But since I already did the work, I thought I'd post it anyway.
Explanation:
li    Get input n.
3*)   Calculate 3*n+1, which is the total width/height.
_     Copy size. We'll need it at the end to insert the newlines.
2m*   Calculate cartesian power with 2. This enumerates all coordinate pairs.
[     Wrap characters in array for split operation at the end.
  {     Loop over all coordinate pairs.
    _     Copy coordinate pair.
    3f/   Divide coordinates by 3.
    2f%   Modulo 2. This characterizes even/odd squares.
    :=    Compare the two coordinates. This gives 0/1 for white/black squares.
    \3f%  Grab second copy of coordinates, and calculate modulo 3.
    :g    Sign. This gives 0 for grid lines, 1 for interior of squares.
    +     Concatenate the two results. We now have a 3 bit code.
    2b    Convert the 3 bits to a number in range 0..7.
    "+-|#+-| "
          Lookup table to convert 0..7 number to character.
    =     Lookup character.
  }/    End loop over coordinate pairs.
]     End wrapping characters.
/     Split character array into lines.
N*    And join them with newlines.

Ruby, 87
->n{a=[b="+--",c="|  |##",c,b,d="|##|  ",d]
0.upto(n*3){|i|puts"".ljust(n*3+1,a[i%6])}}

This is an anonymous function. Call it like this (all possibilities from 0 to 5)
f=->n{a=[b="+--",c="|  |##",c,b,d="|##|  ",d]
0.upto(n*3){|i|puts"".ljust(n*3+1,a[i%6])}}

6.times{|j|f.call(j)}

It makes use of the ljust method on an empty string. Ruby allows a padding string to be specified for justification, so we use ljust with one of the three possible padding strings b,c,d per array a, ordered as bccbdd.

HackVM, 158 bytes
Definitely not a winner, but this looked like a nice challenge to do in HVM.
Place the size into the first memory cell and use the following code:
77*1+c0<0^84*1+?1-11<-1>99*85++0^cc77*1+c066*5+-g!0<0^45*2+?1-95*0^0^2-PPP064*-6-gd95*2-P25*P$1<2>555**1-P0<0^76*6-?1-12<-2>2<3*48*+0^PP555**1-P076*2+-gd25*P$

Note: The code needs to be exactly in one line to work.
Explanation:
Call PLUSHDASHLINE
77*2+c

Read the cell and skip if done
0<0^84*1+?1-

  Flip row parity
  11<-1>

  Call NORMALLINE twice
  99*85++0^cc

  Call PLUSHDASHLINE
  77*1+c

Jump back to start of loop
066*5+-g!

DEFINE_PLUSDASHLINE
0<0^45*2+?1-95*0^0^2-PPP064*-6-gd95*2-P25*P$

DEFINE_NORMALLINE
1<2>555**1-P0<0^76*6-?1-12<-2>2<3*48*+0^PP555**1-P076*2+-gd25*P$

The code calls 2 functions PLUSHDASHLINE and NORMALLINE, maintains a global state for parities (i.e. whether to put a ' ' or a '#' in a cell).
Explanation for PLUSDASHLINE:
Repeat N times
0<0^45*2+?1-

  Print "+--"
  95*0^0^2-PPP

End Repeat
064*-6-g

Print "+"
d95*2-P

Print "\n"
25*P

Return
$

Explanation for NORMALLINE:
Copy Parity into Cell 2
1<2>

Print '|'
555**1-P

Repeat N times
0<0^76*6-?1-

  Flip Cell 2 (i.e. Flip Column Parity)
  12<-2>

  Calculate ' ' or '#' based upon parity
  2<3*48*+0^

  Print it twice
  PP

  Print '|'
  555**1-P

End Repeat
076*2+-g

Print "\n"
d25*P

Return
$

Would appreciate it if someone gave tips for improving it further :)

Python 2, 98
n=input()
f=lambda a,b,s:s+s.join(([a*2,b*2]*n)[:n])+s+'\n'
print f(f(*' #|'),f(*'# |'),f(*'--+'))

Not the shortest way, but an amusing method. The function f takes in two strings a,b and a separator s and interleaves its arguments like saasbbsaasbbsaas. The rows of the board are created in this form with their respective characters, then are themselves interleaved this way to produce the result.

@DragonGuy The problem says the input is a positive integer.

@DragonGuy When you specify the input requirements, it means input is guaranteed to meet those requirements, and can act arbitrarily when they are not the case. I notice you edited the question to add "n=0 should produce +" after this was posted, but changing the rules after answers are already in is strongly discouraged.

Ruby: 83 characters
f=->n{puts d=?++'--+'*n,(0...n).map{|i|[?|+'%2s|'*n%(['','##',''][i%2,2]*n)]*2<<d}}

Sample run:
irb(main):001:0> f=->n{puts d=?++'--+'*n,(0...n).map{|i|[?|+'%2s|'*n%(['','##',''][i%2,2]*n)]*2<<d}}
=> #<Proc:0x000000007c51a0@(irb):1 (lambda)>

irb(main):002:0> f[0]
+
=> nil

irb(main):003:0> f[1]
+--+
|  |
|  |
+--+
=> nil

irb(main):004:0> f[2]
+--+--+
|  |##|
|  |##|
+--+--+
|##|  |
|##|  |
+--+--+
=> nil

irb(main):005:0> f[3]
+--+--+--+
|  |##|  |
|  |##|  |
+--+--+--+
|##|  |##|
|##|  |##|
+--+--+--+
|  |##|  |
|  |##|  |
+--+--+--+
=> nil

Vyxal, 52 bytes
(x|`+--`*\++,2(⁰(n←x+₂[`|  `|`|##`]₴)\|,))`+--`*\++,

Try it Online!
A.  Big. Mess.

Julia, 124 bytes
n->(t="+--"^n*"+";a="|  ";b="|##";m=n÷2;c=n%2>0;p=println;p(t);for i=1:n p(((i%2<1?(b*a)^m*b^c:(a*b)^m*a^c)*"|\n")^2*t)end)

This creates an unnamed function that accepts an integer and prints to stdout.
Ungolfed + explanation:
function f(n)
    # Define the portions of the board
    t = "+--"^n * "+"
    a = "|  "
    b = "|##"

    # There will be n÷2 repeated a*b or b*a per line
    m = n ÷ 2

    # If n is odd, there will be an extra a or b
    c = n % 2 != 0

    # Print the top
    println(t)

    # Print each horizontal section of the board
    for i = 1:n
        # In even numbered sections, b precedes a
        j = (i % 2 == 0 ? (b*a)^m * b^c : (a*b)^m * a^c) * "|\n"
        println(j^2 * t)
    end
end

Javascript, ES6 149
n=>(r="+--".repeat(n)+"+",[...r].map((_,i)=>i%3?(x=i%6&&i%6<3?" ":"#",[...r].map((_,e)=>e%3?e%6&&e%6<3?x:"#"==x?" ":"#":"|").join('')):r).join('\n'))

Pretty fun to write though it's a bit long
Works on firefox
1 - Open console
2 - Type the following
console.log((n=>(r="+--".repeat(n)+"+",[...r].map((_,i)=>i%3?(x=i%6&&i%6<3?" ":"#",[...r].map((_,e)=>e%3?e%6&&e%6<3?x:"#"==x?" ":"#":"|").join('')):r).join('\n')))(15));

Output (n=15):
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

@DragonGuy Done, see if it works for you.

Right at the end, you can still save three bytes by substituting join('\n') with join\ ``, where the space I wrote denotes an actual new line character.

Haskell, 118
This is my first haskell code golf answer and here it is:
f n=mapM_(putStrLn.s)[0..3*n]where;d x=(++)$take(3*n)$cycle x;s x|x`mod`3<1=d"+--""+"|x`mod`6<3=d"|  |##""|"|1<2=d"|##|  ""|"

More readable version:
func num = do
    let -- Range
        rag = 3 * num
        -- `+--+`
        a = d "+--" "+"
        -- `|  |##`
        b = d "|  |##" "|"
        -- `|##|  `
        c = d "|##|  " "|"
        -- generate line
        d x y = take rag (cycle x) ++ y
        -- step
        step x
            | x `mod` 6 `elem` [1, 2] = b
            | x `mod` 3 == 0          = a
            | otherwise               = c

    mapM_ (putStrLn . step) [0..rag]

Output
*Main> :load test
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, modules loaded: Main.
*Main> f 1
+
*Main> f 4
+--+--+--+--+
|  |##|  |##|
|  |##|  |##|
+--+--+--+--+
|##|  |##|  |
|##|  |##|  |
+--+--+--+--+
|  |##|  |##|
|  |##|  |##|
+--+--+--+--+
|##|  |##|  |
|##|  |##|  |
+--+--+--+--+
*Main> f 15
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
|##|  |##|  |##|  |##|  |##|  |##|  |##|  |##|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
|  |##|  |##|  |##|  |##|  |##|  |##|  |##|  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

f 1 should produce 1 empty box, f 0 produces just the plus sign.

@Vioz- My bad, so this makes the code even shorter :P

Haskell, 99
This is partially inspired by the previous Haskell answer by catgocat; I wrote my own version, then looked at it, then wrote another. I'm playing by the same rules — the input is an argument, but the output is stdout. (If it could be a pure function, subtract 7 characters putStr$.)
f n=putStr$unlines$t$map t$y[a,b,b,a,c,c]where t=take(n*3+1)
a=y"+--"
b=y"|  |##"
c=drop 3b
y=cycle

We use t to take a region of 3n + 1 characters from an infinite checkerboard built using cycle, and that's it. The primary idea I took from the other answer is that of putting the patterns of both the border and checker cells together in strings.
My first version (140 characters) used the strategy of calculating the character at each point, which might be better for a more complex problem than this one.
f n=putStr$unlines$map(\y->map(g y)r)r where r=[0..n*3]
g y x=s(s '+'y '|')x$s '-'y$cycle" #"!!(x`div`3+y`div`3)
s c i d|i`mod`3==0=c|True=d

I'm glad your inspiration led to such smart answer :)

@DragonGuy I just did the same thing and still get 99. wc agrees, and I checked for nonprinting characters. Does this 84-byte version run? If so, I'll take it :)

C - 119 101
Uses now the calculation similar to @Sp3000 answer. Also couple optimizations.
i,j;f(n){for(i=j=0;j<=n*3;i++)putchar(i-n*3-1?" -|+#"[!(j%3)+2*!(i%3)?:(i/3+j/3)%2*4]:(j-=i=-1,10));}

I think that ?: is a GCC extension...
Old answer:
f(n){int i,j;char p[]=" -|+";for(i=j=0;j<=n*3;*p=" #"[(i++/3+j/3)%2])putchar(i-n*3-1?p[!(j%3)+2*!(i%3)]:(j-=i=-1,10));}

It maintains 2 coordinates and honestly calculates which character to print for each pair. List of characters to print is stored in array and this alone prints an "uncolored" grid. First element of the array is modified to draw black squares.
I might change this so that instead of two independent coordinates it's one value counting up or (maybe even better) down, but can't wrap my head around that right now.
Bonus - replacing 3 with any other number results in a program that draws valid checkerboard with different cell size.

100 bytes

awk - 91
{
    for(k=i=3*$0+1;i--;print"")
        for(j=k;j--;)printf i%3?j%3?234~(i+j)%6?FS:"#":j%3?"-":"|":"+"
}

Was quite a fight to get it below 100. Counting backwards and using the match operator were the breakthroughs ;) The rest is pretty much straightforward logic.

Pyke, 47 bytes
"+--"Q*\+j+i
QQ]Uas 2%" #"@2*)F\|JjR+"+
"+2*pi
<Newline needed>

Try it here!


text:
Pronouncing Hex
Pronouncing Hex
For those of you uninitiated with the show Silicon Valley, this challenge is inspired by an exchange that goes like this (YouTube):
Kid -
  Here it is: Bit… soup. It’s like alphabet soup, BUT… it’s ones and zeros
  instead of letters.
Erlich Bachman -
  {silence}
Kid -
  ‘Cause it’s binary? You know, binary’s just ones and zeroes.
Erlich Bachman -
  Yeah, I know what binary is. Jesus Christ, I memorized the hexadecimal
  times tables when I was fourteen writing machine code. Okay? Ask me
  what nine times F is. It’s fleventy-five. I don’t need you to tell me what binary is.

It should be noted that technically, 0x9 * 0xF = 0x87, not 'fleventy-five', but this brings up an important question - how would you actually pronounce hex in conversation? It's not like oh ex eff eff flows off the tongue easily, so what should we do? Here's a handy pronunciation chart we will follow.
A = ay       A0 = atta-
B = bee      B0 = bibbity-
C = cee      C0 = city-
D = dee      D0 = dickety-
E = ee       E0 = ebbity-
F = eff      F0 = fleventy-

We can split a 4-length hex number into two groups of two, and determine the pronunciation from the table above, as well as common English pronunciation for numbers. So, for the example 0xFFAB, we would get Fleventy-eff bitey atta-bee.
If a number is included, such as 0xF5AB, you would print Fleventy-five bitey atta-bee. Also, if a number starts one of the groups, you should use it's "tens" pronunciation. For example, 0x5FAA would become Fifty-eff bitey atta-ay. In the case where you have something like 0x1FAC, this would be Effteen bitey atta-cee. But, if this rule were to be used for 0x1AF4, a-teen could be confused for eighteen, so you must prepend a Y. So, the correct output would be Yayteen bitey fleventy-four
In the case of 0xD0F4, instead of doing Dickety-zero bitey fleventy-four, we would ignore the zero and print Dickety-bitey fleventy-four.
Hyphens should only appear within the groups of two, i.e. bitey should not be connected to either group with a hyphen unless the first group is only one word! So 0x04F4 would be four-bitey fleventy-four, but 0x44F4 would be forty-four bitey fleventy-four. As trichoplax said, bitey should only be hyphened when following a round number.
For a comprehensive look at how this will work, check out the example I/O below.
Objective
Create a program or function that will take a hexadecimal string as input or a function argument and produce it's pronunciation. The output must have proper capitalization. You may assume that the length of this number will always be 4.
Example I/O
"0xFFFF" -> "Fleventy-eff bitey fleventy-eff"
"0x0000" -> "Zero"
"0x0010" -> "Ten"
"0x0100" -> "One-bitey zero"
"0x1110" -> "Eleven-bitey ten"
"0xBEEF" -> "Bibbity-ee bitey ebbity-eff"
"0x9999" -> "Ninety-nine bitey ninety-nine"
"0xA1B2" -> "Atta-one bitey bibbity-two"
"0x3C4F" -> "Thirty-cee bitey forty-eff"
"0x17AB" -> "Seventeen-bitey atta-bee"
"0x1AFB" -> "Yayteen-bitey fleventy-bee"
"0xAAAA" -> "Atta-ay bitey atta-ay"

This is code-golf, so least number of bytes wins.

Here's a handy trick for anyone learning the hex times tables: The F times table can be calculated on your 16 fingers and toes (excluding thumbs and big toes). Simply line them up in a row and fold the nth one down to calculate F x n. The number of digits to the left of the folded down digit is the first digit, and the number of digits to the right of the folded down digit is the second digit, allowing you to calculate any 2 digit multiple. For example, fold the Cth digit down to give F x C = Bibbity four.

@trichoplax My kid was amazed when I first showed him how to do that for nines on his fingers :D

@Geobits that's what I extrapolated it from - I loved that trick for 9s as a kid.

@trichoplax I think bitey makes more sense for the purpose of pronunciation. I've tried to make it clearer where hyphens are to appear, and the first letter of the output must be capitalized, and the rest in lowercase.

@Geobits I fixed the examples.

This pronunciation method takes twice as many syllables than the lerfu (borrowed lojban word for letter pronunciations) themselves, but it is more fun to use.

Can we have a leading or trailing space?

@GeorgeReith No extra whitespace should be in the output.

Why is 0x17AB not seventeen-bitey atta-bitey when the rule is its only hyphenated if the first group is represented by one word?

@GeorgeReith seventeen is one word. and I think you mean atta-bee

you don't mention "bitey" anywhere other than examples

@Maltysen Exactly it is one word so it should be hyphenated, i did mean atta-bee but the author has since edited the example to correct it.

@GeorgeReith sorry, misread your comment.

Pyth - 312 293 286 251 bytes
Time to start reducing the data, more coming.
Holy biggest Pyth program I've ever written! There is still huge compression possible with the data, both algortihimically and base conversion, but just wanted to put this up.
Kcs@LGjC"qNjÆÉý(7läQ«I?sfçÂØ^Ðûü»   u$ÐÃoó}QÛã´Hf®?Nâ²-YÜZÔ7ÂþæX#\"åØ"26\q=+K>K11J.e?+?bnb\|@K+16k"ty"-kTbc"  twen | for | | | | | atta bibbi ci dicke ebbi fleven"d.srj"bitey "m?++@Kd?k<d18"teen"\-<d32+j\-@V,JKfT.Dd16\ ?Gh=G.DQ256tG4\-

I interpret input as hex literal through Q which it automatically detect with the 0x. Then I divmod it 256 into the bytes, and remove the first byte if its zero, then map it through two arrays, one for 0-1F and then 20-F0. The second one gets a divmod through the first array also. The first option gets a hypen at the end, and the second get a hyphen at the middle and a space at the end. Join by "bitey ", capitalize with range, and strip hyphens  with .s and we're good.
The base compression part is also interesting because I first started out with basic 128 -> 256 conversion. But now, what I am doing is using "q" as the separator instead of space. Thus I can now consider the string as a base 26 string with xLG, improving compression tremendously.
Try it here online.
Test suite.

I know it's not in the question, but I think you should try extrapolating to more numbers, like 0x112233 and 0x93FBAC09

@I think this pronunciation model loses it's, uh, viability at that point, haha. Could you imagine actually saying Ninety-three bitey fleventy-bee halfy atta-cee bitey nine?

I think something has broken, right now your code only produce a massive amount of Truebiteys and Falsebiteys.

@Vioz- Ternaries are broken. Isaacg reversed their order a couple days ago. I could go and change them and in fact save a couple bytes, but their are like 14.

Ah, I see. So what version of Pyth preserves the functionality?

@Vioz- well this was the latest commit, commit 440, so I guess anything before that.

Java - 856 bytes
Not short but at least the second answer ;)
It's a method called String p(String n) which will do the job:
String p(String n){String[]b={"","ten","twen","thir","for","fif","six","seven","eigh","nine",
"atta","bibbi","ci","dicke","ebbi","fleven"};String[]s={"zero","one","two","three","four",
"five","six","seven","eight","nine","ay","bee","cee","dee","ee","eff"};String[]t={"ten",
"eleven","twelve","thir","four","fif","six","seven","eigh","nine","yay","bee","cee","dee",
"ee","eff"};int w=Byte.valueOf(n.substring(2,3),16);int x=Byte.valueOf(n.substring(3,4),16);
int y=Byte.valueOf(n.substring(4,5),16);int z=Byte.valueOf(n.substring(5,6),16);String r=(w==
1?t[x]+(x>2?"teen":""):((w==0?"":b[w]+(w>1&&w!=10?"ty":"")+"-")+(w==0&&x==0?"":s[x])))+((w==0
&&x>0||w==1&&x<3||w>0&&x==0)?"-":w==0&&x==0?"":" ")+(w>0||x>0?"bitey ":"")+(y==1?t[z]+(z>2?
"teen":""):((y==0?"":b[y]+(y>1&&y!=10?"ty":"")+"-")+(y>1&&z!=0||y==0?s[z]:"")));return (char)
(r.charAt(0)-32)+r.substring(1);}

Javascript - 577 719 bytes
function h(e){for(e=e.match(/.{1,2}/g),r="",i=1;i<e.length;i++)j=parseInt("0x"+e[i]),0!=j?r+=c(parseInt("0x"+e[i]))+"bitey ":i>1?r+="zero-bitey":0;return r=""==r?"Zero":r[0].toUpperCase()+r.substr(1,r.length-7),null!==r[r.length-1].match(/[-\s]$/g)?r=r.substr(0,r.length-1):0,r}function c(e){return d=["zero","one","two","three","four","five","six","seven","eight","nine","ay","bee","cee","dee","ee","eff","ten","eleven","twelve","thir","four","fif","six","seven","eigh","nine","yay","bee","cee","dee","ee","eff"],p=["twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety","atta","bibbity","city","dickety","ebbity","fleventy"],1>e?"":e>31?p[Math.floor(e/16)-2]+"-"+d[e%16]+" ":17>e?d[e]+"-":d[e]+"teen-"}

I'm sure there are improvements to be made. Added bonus, it parses arbitrary length hex strings.
EDIT: Whoops, it doesn't work right when there are leading zeros. Hm.
EDIT 2: Fixed, I think. JSFiddle

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Shortest universal maze exit string
A maze on an N by N grid of square cells is defined by specifying whether each edge is a wall or not a wall. All outer edges are walls. One cell is defined as the start, and one cell is defined as the exit, and the exit is reachable from the start. The start and exit are never the same cell.
Note that neither the start nor the exit need to be on the outer border of the maze, so this is a valid maze:

A string of 'N', 'E', 'S' and 'W' indicates attempting to move North, East, South and West respectively. A move that is blocked by a wall is skipped without movement. A string exits a maze if applying that string from the start results in the exit being reached (regardless of whether the string continues after reaching the exit).
Inspired by this puzzling.SE question for which xnor provided a provable method of solving with a very long string, write code that can find a single string that exits any 3 by 3 maze.
Excluding invalid mazes (start and exit on the same cell, or exit not reachable from start) there are 138,172 valid mazes and the string must exit each of them.
Validity
The string must satisfy the following:

It is composed of only the characters 'N', 'E', 'S' and 'W'.
It exits any maze it is applied to, if started at the start.

Since the set of all possible mazes includes each possible maze with each possible valid starting point, this automatically means that the string will exit any maze from any valid starting point. That is, from any starting point from which the exit is reachable.
Winning
The winner is the answer that provides the shortest valid string and includes the code used to produce it. If more than one of the answers provide a string of this shortest length, the first to post that string length wins.
Example
Here is an example string 500 characters long, to give you something to beat:
SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE

Thanks to orlp for donating this.

Leaderboard

Equal scores are listed in order of posting of that score. This is not necessarily the order that the answers were posted since the score for a given answer may be updated over time.

Judge
Here is a Python 3 validator that takes a string of NESW as a command line argument or via STDIN.
For an invalid string, this will give you a visual example of a maze it fails for.

This is a really neat question. Is there one shortest string (or a number of strings and a proof that there can't be any shorter answers)? And if so, do you know it?

@AlexVanLiew Thanks :) For a 2 by 2 maze the shortest possible string is 11 characters. I chose 3 by 3 for the question to make it unlikely that an optimal solution will be found. Judging by the results for the 2 by 2 case (which can be brute forced), there will be a shortest possible length, with a number of different valid strings of that length.

And no, I don't have any idea how long the shortest possible string will be for 3 by 3 mazes. More than 11, and less than 86... You could increase that lower bound by brute force, but my suspicion is that the shortest string will be too long to be found that way.

Huh. If I was better at this sort of thing I would give it a shot, but I'm not good enough with optimization and low-level speed and the like to beat orlp's submission. I hope you get somebody else to post something interesting!

@AlexVanLiew optimisation is one way to approach it. I'm also interested to see if anyone finds some kind of pattern that allows for reducing the length without having to process millions of candidates...

Can the exit be the center cell?

@AlexReinking yes the start can be any of the 9 cells and the exit can be any of the 9 cells, as long as they are not the same cell, and the exit is reachable from the start.

Slightly similar to this stackoverflow question: http://stackoverflow.com/questions/26910401/solve-all-4x4-mazes-simultaneously-with-least-moves - but start and end cell are top left and bottom right in that one, which reduces the possible maze count to 2423.

@schnaader that's an interesting question you link to! In addition to start and end being fixed, the walls are filled cells in that question, rather than having walls along cell edges. Some of the techniques discussed there might still be applicable here though...

why is this specific to 3? in this case my code could just be "print NENENNNENENE" or something. why wouldn't the question be to all numbers, and be scored based on the string of length 3?

@proudhaskeller either way would be a valid question. The general case, scored for n=3, would require more generalised code. This specific case allows for optimisations that do not apply to general n, and that's the way I chose to ask it.

@proudhaskeller sorry I missed the point of your comment initially - you mean someone could hardcode a string rather than submitting code that finds one. If someone did, I would downvote and raise it on meta, as I am certain that they would need to have code elsewhere that they omitted from the answer in order to find a competitive string. A valid answer requires a string plus the code that produced it.

Has anyone considered approaching this problem as finding the shortest accepted string to a regular expression? It would require a LOT of reductions in the number of problems before converting to regexes, but could theoretically find a verifiably optimal solution.

The link to the python 3 validator is dead.

@NonlinearFruit thanks for letting me know - I've fixed the link now

@AlexVanLiew, if NP-complete problems can't be effectively solved, almost surely optimal solution won't be found.

Im excited about this puzzle.  it's probably going to be one of the first things we can solve via quantum computing.  you only need 2*n qbits where n is the number of instructions that you want to check.

@tuskiomi so as quantum computers progress we'll get increasing lower bounds on the optimal solution until eventually we find it...

@trichoplax yep,  and then (given an average computational time), we would only need to perform 2 checks per Qbit. it's very computationally lax for a quantum computer,  but for a classical machine,  it's very hard to do, even with current technology.

Can we call out to the validator you've written, in our code?

@Stackstuck this is not code-golf, so you can include my validator directly in your code - there's no need to make it short. However, the validator is intended for checking a single solution with human readable output - it isn't fast enough to check large numbers of candidates in a practical time. Go ahead and use and modify it however you wish, but the existing answers managed to find ways of optimising this check dramatically, so looking at them will probably be more useful than looking at mine... :)

Yeah, I have absolutely no idea how they're doing it.  I was just planning on exhaustively searching.

Should the question have tag atomic-code-golf?

I thought it was possible to solve this using DFA intersection and minimization, but I don't know enough to do so

C++, 97 95 93 91 86 83 82 81 79 characters

NNWSWNNSENESESWSSWNSEENWWNWSSEWWNENWEENWSWNWSSENENWNWNESENESESWNWSESEWWNENWNEES

My strategy is fairly simple - an evolution algorithm that can grow, shrink, swap elements of and mutate valid sequences. My evolution logic is now nearly the same as @Sp3000's, as his was an improvement over mine.
However, my implementation of the maze logic is rather nifty. This allows me to check if strings are valid at blistering speed. Try to figure it out by looking at the comment, do_move and the Maze constructor.
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <vector>

/*
    Positions:

        8, 10, 12
        16, 18, 20
        24, 26, 28

    By defining as enum respectively N, W, E, S as 0, 1, 2, 3 we get:

        N: -8, E: 2, S: 8, W: -2
        0: -8, 1: -2, 2: 2, 3: 8

    To get the indices for the walls, average the numbers of the positions it
    would be blocking. This gives the following indices:

        9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27

    We'll construct a wall mask with a 1 bit for every position that does not
    have a wall. Then if a 1 shifted by the average of the positions AND'd with
    the wall mask is zero, we have hit a wall.
*/

enum { N = -8, W = -2, E = 2, S = 8 };
static const int encoded_pos[] = {8, 10, 12, 16, 18, 20, 24, 26, 28};
static const int wall_idx[] = {9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27};
static const int move_offsets[] = { N, W, E, S };

int do_move(uint32_t walls, int pos, int move) {
    int idx = pos + move / 2;
    return walls & (1ull << idx) ? pos + move : pos;
}

struct Maze {
    uint32_t walls;
    int start, end;

    Maze(uint32_t maze_id, int start, int end) {
        walls = 0;
        for (int i = 0; i < 12; ++i) {
            if (maze_id & (1 << i)) walls |= 1 << wall_idx[i];
        }
        this->start = encoded_pos[start];
        this->end = encoded_pos[end];
    }

    uint32_t reachable() {
        if (start == end) return false;

        uint32_t reached = 0;
        std::vector<int> fill; fill.reserve(8); fill.push_back(start);
        while (fill.size()) {
            int pos = fill.back(); fill.pop_back();
            if (reached & (1 << pos)) continue;
            reached |= 1 << pos;
            for (int m : move_offsets) fill.push_back(do_move(walls, pos, m));
        }

        return reached;
    }

    bool interesting() {
        uint32_t reached = reachable();
        if (!(reached & (1 << end))) return false;
        if (std::bitset<32>(reached).count() <= 4) return false;

        int max_deg = 0;
        uint32_t ends = 0;
        for (int p = 0; p < 9; ++p) {
            int pos = encoded_pos[p];
            if (reached & (1 << pos)) {
                int deg = 0;
                for (int m : move_offsets) {
                    if (pos != do_move(walls, pos, m)) ++deg;
                }
                if (deg == 1) ends |= 1 << pos;
                max_deg = std::max(deg, max_deg);
            }
        }

        if (max_deg <= 2 && ends != ((1u << start) | (1u << end))) return false;

        return true;
    }
};

std::vector<Maze> gen_valid_mazes() {
    std::vector<Maze> mazes;
    for (int maze_id = 0; maze_id < (1 << 12); maze_id++) {
        for (int points = 0; points < 9*9; ++points) {
            Maze maze(maze_id, points % 9, points / 9);
            if (!maze.interesting()) continue;
            mazes.push_back(maze);
        }
    }

    return mazes;
}

bool is_solution(const std::vector<int>& moves, Maze maze) {
    int pos = maze.start;
    for (auto move : moves) {
        pos = do_move(maze.walls, pos, move);
        if (pos == maze.end) return true;
    }

    return false;
}

std::vector<int> str_to_moves(std::string str) {
    std::vector<int> moves;
    for (auto c : str) {
        switch (c) {
        case 'N': moves.push_back(N); break;
        case 'E': moves.push_back(E); break;
        case 'S': moves.push_back(S); break;
        case 'W': moves.push_back(W); break;
        }
    }

    return moves;
}

std::string moves_to_str(const std::vector<int>& moves) {
    std::string result;
    for (auto move : moves) {
             if (move == N) result += "N";
        else if (move == E) result += "E";
        else if (move == S) result += "S";
        else if (move == W) result += "W";
    }
    return result;
}

bool solves_all(const std::vector<int>& moves, std::vector<Maze>& mazes) {
    for (size_t i = 0; i < mazes.size(); ++i) {
        if (!is_solution(moves, mazes[i])) {
            // Bring failing maze closer to begin.
            std::swap(mazes[i], mazes[i / 2]);
            return false;
        }
    }
    return true;
}

template<class Gen>
int randint(int lo, int hi, Gen& gen) {
    return std::uniform_int_distribution<int>(lo, hi)(gen);
}

template<class Gen>
int randmove(Gen& gen) { return move_offsets[randint(0, 3, gen)]; }

constexpr double mutation_p = 0.35; // Chance to mutate.
constexpr double grow_p = 0.1; // Chance to grow.
constexpr double swap_p = 0.2; // Chance to swap.

int main(int argc, char** argv) {
    std::random_device rnd;
    std::mt19937 rng(rnd());
    std::uniform_real_distribution<double> real;
    std::exponential_distribution<double> exp_big(0.5);
    std::exponential_distribution<double> exp_small(2);

    std::vector<Maze> mazes = gen_valid_mazes();

    std::vector<int> moves;
    while (!solves_all(moves, mazes)) {
        moves.clear();
        for (int m = 0; m < 500; m++) moves.push_back(randmove(rng));
    }

    size_t best_seen = moves.size();
    std::set<std::vector<int>> printed;
    while (true) {
        std::vector<int> new_moves(moves);
        double p = real(rng);

        if (p < grow_p && moves.size() < best_seen + 10) {
            int idx = randint(0, new_moves.size() - 1, rng);
            new_moves.insert(new_moves.begin() + idx, randmove(rng));
        } else if (p < swap_p) {
            int num_swap = std::min<int>(1 + exp_big(rng), new_moves.size()/2);
            for (int i = 0; i < num_swap; ++i) {
                int a = randint(0, new_moves.size() - 1, rng);
                int b = randint(0, new_moves.size() - 1, rng);
                std::swap(new_moves[a], new_moves[b]);
            }
        } else if (p < mutation_p) {
            int num_mut = std::min<int>(1 + exp_big(rng), new_moves.size());
            for (int i = 0; i < num_mut; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves[idx] = randmove(rng);
            }
        } else {
            int num_shrink = std::min<int>(1 + exp_small(rng), new_moves.size());
            for (int i = 0; i < num_shrink; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves.erase(new_moves.begin() + idx);
            }
        }

        if (solves_all(new_moves, mazes)) {
            moves = new_moves;

            if (moves.size() <= best_seen && !printed.count(moves)) {
                std::cout << moves.size() << " " << moves_to_str(moves) << "\n";
                if (moves.size() < best_seen) {
                    printed.clear(); best_seen = moves.size();
                }
                printed.insert(moves);
            }
        }
    }

    return 0;
}

Confirmed valid. I'm impressed - I didn't expect to see strings this short.

I finally got round to installing gcc and running this for myself. It is hypnotic watching the strings mutating and slowly shrinking...

@trichoplax I told you it was fun :)

You could make this even faster by just preprocessing a table of walls, positions, and directions. It'd be less than a megabyte in size, and do_move would just become table[walls][pos][move]

Actually, if you created that table within each Maze struct, you would only use two memory loads to compute a move, rather than one memory load and a bunch of arithmetic (and a branch!).

@AlexReinking That would be significantly slower. Since the table is around ~1 megabyte you'll expect to hit L3 cache. L3 cache is ~40 cycles per access. The best way to speed this up is to precompute the masks into the walls variable, and to not do memory lookups at all.

Aren't you already hitting L3 cache when you iterate over the vector of Mazes? No memory lookups would be best, yeah.

@AlexReinking No, iterating over a contiguous chunk of memory in a linear fashion is perfect for the prefetcher and cache. Either way, that iteration can not be avoided.

@orlp I had an idea for moving that doesn't require branching and uses a small lookup table (less than the size of a cache line). How fast do you think it is?

@AlexReinking Not needed, you can change the position numbers such that they'll never go negative, and then encode the wall such that the ith bit of it contains either a 0 or a 1 for a wall at that position, and every other bit is a 0. Then you can just mask directly without the need of any lookup table or branch.

Would love to see what that looks like.

@AlexReinking I updated my answer with said implementation. If you look at the disassembly you'll see it's only a dozen of instructions without any branch or load: http://coliru.stacked-crooked.com/a/3b09d36db85ce793 .

could you save a little bit by defining the enum constants to be the offsets you compute and then make the rarely-called string translation a bit more complicated?

@AlexReinking Initially I thought of using 2-bit integers to represent the strings, but then I found out memory usage is no problem, so the enum still stems from that version. In my next version I can do that, yes.

@AlexReinking Done. do_move is now insanely fast.

I got a little bit of a speed up by sorting the vector of mazes - each time a string fails for a maze, that maze is moved one step closer to the start of the vector, so that after a while invalid strings are failing earlier on average. Not sure if that will conflict with some of the other improvements you've made since then though...

@trichoplax That's a cool idea!

@trichoplax And from my measurements, effective too! All I do is if I detect that the maze at index i caused the failure, I swap it with the maze at position i / 2. This (really) often reduces 10000+ mazes being checked  to <50.

@trichoplax From my measurements it seems to be 2x faster!

@orlp Great! I was only swapping with i - 1 and saw a marginal speed up - I didn't think to use i / 2.

@orlp did the improvements lead to shorter strings? 24 hours left to get lower than 82 for the bounty...

@trichoplax Well, I woke up today to check the terminal, but it seems that my computer BSOD'd overnight. So, the only answer is 'perhaps'.

Ah... Well I'll be waiting until the end of the 24 hour grace period before awarding the bounty, so there are over 25 hours still available. Good luck :)

@trichoplax 81 :)

That was quick...

I hope you don't mind my edit - I wanted to include the most up to date score found using your code ready for posting an open ended bounty for an improvement.

Has anyone thought about porting the do_Move function to OpenCL or CUDA?

This code can be further sped up by halving move values and not doing the division by 2. Though I haven't measured precisly, the speedup was noticable at least on my pc. https://godbolt.org/z/iLml-3 The version with bt was slower, at least on my nehalem
`enum { N = -4, W = -1, E = 1, S = 4 };
int do_move(uint32_t walls, int pos, int halfmove) {
int idx = pos + halfmove;
return walls & (1ull << idx) ? pos + halfmove + halfmove : pos;
}Also it's trivial to parallelize. https://pastebin.com/tv1vnPcA There'snum_threads` variable.

Python 3 + PyPy, 82 80 characters
SWWNNSENESESWSSWSEENWNWSWSEWNWNENENWWSESSEWSWNWSENWEENWWNNESENESSWNWSESESWWNNESE

I've been hesitant to post this answer because I've basically taken orlp's approach and put my own spin on it. This string was found by starting with a pseudorandom length 500 solution - quite a number of seeds were tried before I could break the current record.
The only new major optimisation is that I only look at one third of the mazes. Two categories of mazes are excluded from the search:

Mazes where <= 7 squares are reachable
Mazes where all reachable squares are on a single path, and the start/finish are not at both ends

The idea is that any string which solves the rest of the mazes should also solve the above automatically. I'm convinced this is true for the second type, but it is definitely not true for the first, so the output will contain some false positives that need to be checked separately. These false positive usually only miss about 20 mazes though, so I thought it'd be a good tradeoff between speed and accuracy, and it would also give the strings a little more breathing space to mutate.
Initially I went through a long list of search heuristics, but horrifically none of them came up with anything better than 140 or so.
import random

N, M = 3, 3

W = 2*N-1
H = 2*M-1

random.seed(142857)

def move(c, cell, walls):
    global W, H

    if c == "N":
        if cell > W and not (1<<(cell-W)//2 & walls):
            cell = cell - W*2

    elif c == "S":
        if cell < W*(H-1) and not (1<<(cell+W)//2 & walls):
            cell = cell + W*2

    elif c == "E":
        if cell % W < W-1 and not (1<<(cell+1)//2 & walls):
            cell = cell + 2

    elif c == "W":
        if cell % W > 0 and not (1<<(cell-1)//2 & walls):
            cell = cell - 2

    return cell

def valid_maze(start, finish, walls):
    global adjacent

    if start == finish:
        return False

    visited = set()
    cells = [start]

    while cells:
        curr_cell = cells.pop()

        if curr_cell == finish:
            return True

        if curr_cell in visited:
            continue

        visited.add(curr_cell)

        for c in "NSEW":
            cells.append(move(c, curr_cell, walls))

    return False

def print_maze(maze):
    start, finish, walls = maze
    print_str = "".join(" #"[walls & (1 << i//2) != 0] if i%2 == 1
                        else " SF"[2*(i==finish) + (i==start)]
                        for i in range(W*H))

    print("#"*(H+2))

    for i in range(H):
        print("#" + print_str[i*W:(i+1)*W] + "#")

    print("#"*(H+2), end="\n\n")

all_cells = [W*y+x for y in range(0, H, 2) for x in range(0, W, 2)]
mazes = []

for start in all_cells:
    for finish in all_cells:
        for walls in range(1<<(N*(M-1) + M*(N-1))):
            if valid_maze(start, finish, walls):
                mazes.append((start, finish, walls))

num_mazes = len(mazes)
print(num_mazes, "mazes generated")

to_remove = set()

for i, maze in enumerate(mazes):
    start, finish, walls = maze

    reachable = set()
    cells = [start]

    while cells:
        cell = cells.pop()

        if cell in reachable:
            continue

        reachable.add(cell)

        if cell == finish:
            continue

        for c in "NSEW":
            new_cell = move(c, cell, walls)
            cells.append(new_cell)

    max_deg = 0
    sf = set()

    for cell in reachable:
        deg = 0

        for c in "NSEW":
            if move(c, cell, walls) != cell:
                deg += 1

        max_deg = max(deg, max_deg)

        if deg == 1:
            sf.add(cell)

    if max_deg <= 2 and len(sf) == 2 and sf != {start, finish}:
        # Single path subset
        to_remove.add(i)

    elif len(reachable) <= (N*M*4)//5:
        # Low reachability maze, above ratio is adjustable
        to_remove.add(i)

mazes = [maze for i,maze in enumerate(mazes) if i not in to_remove]
print(num_mazes - len(mazes), "mazes removed,", len(mazes), "remaining")
num_mazes = len(mazes)

def check(string, cache = set()):
    global mazes

    if string in cache:
        return True

    for i, maze in enumerate(mazes):
        start, finish, walls = maze
        cell = start

        for c in string:
            cell = move(c, cell, walls)

            if cell == finish:
                break

        else:
            # Swap maze to front
            mazes[i//2], mazes[i] = mazes[i], mazes[i//2]
            return False

    cache.add(string)
    return True

while True:
    string = "".join(random.choice("NSEW") for _ in range(500))

    if check(string):
        break

# string = "NWWSSESNESESNNWNNSWNWSSENESWSWNENENWNWESESENNESWSESWNWSWNNEWSESWSEEWNENWWSSNNEESS"

best = len(string)
seen = set()

while True:
    action = random.random()

    if action < 0.1:
        # Grow
        num_grow = int(random.expovariate(lambd=3)) + 1
        new_string = string

        for _ in range(num_grow):
            i = random.randrange(len(new_string))
            new_string = new_string[:i] + random.choice("NSEW") + new_string[i:]

    elif action < 0.2:
        # Swap
        num_swap = int(random.expovariate(lambd=1)) + 1
        new_string = string

        for _ in range(num_swap):
            i,j = sorted(random.sample(range(len(new_string)), 2))
            new_string = new_string[:i] + new_string[j] + new_string[i+1:j] + new_string[i] + new_string[j+1:]

    elif action < 0.35:
        # Mutate
        num_mutate = int(random.expovariate(lambd=1)) + 1
        new_string = string

        for _ in range(num_mutate):
            i = random.randrange(len(new_string))
            new_string = new_string[:i] + random.choice("NSEW") + new_string[i+1:]

    else:
        # Shrink
        num_shrink = int(random.expovariate(lambd=3)) + 1
        new_string = string

        for _ in range(num_shrink):
            i = random.randrange(len(new_string))
            new_string = new_string[:i] + new_string[i+1:]

    if check(new_string):
        string = new_string

    if len(string) <= best and string not in seen:
        while True:
            if len(string) < best:
                seen = set()

            seen.add(string)
            best = len(string)
            print(string, len(string))

            # Force removals on new record strings
            for i in range(len(string)):
                new_string = string[:i] + string[i+1:]

                if check(new_string):
                    string = new_string
                    break

            else:
                break

Confirmed valid. Nice improvements :)

I like your idea of realising some mazes do not need to be checked. Could you somehow automate the process of determining which mazes are redundant checks? I'm curious to know if that would show up more mazes than the ones that can be deduced intuitively...

What's your reasoning for not needing to check path graphs where the start is not at one end? The case where the finish is not at one end is easy to justify, and can be strengthened to not needing to check cases where the finish is a cut vertex, but I can't see how to justify eliminating start vertices.

@PeterTaylor After some more thinking, theoretically you are right, there are some mazes that you can't eliminate like that. However, it seems that on 3x3 it doesn't matter for strings this long.

@orlp, Sp3000 sketched a proof in chat. Path graphs are a special case. Renumber the cells 0 to n along the path and suppose that string S gets you from 0 to n. Then S also gets you from any intermediate cell c to n. Suppose otherwise. Let a(i) be the position after i steps starting at 0 and b(i) starting at c. Then a(0) = 0 < b(0), each step changes a and b by at most 1, and a(|S|) = n > b(|S|). Take the smallest t such that a(t) >= b(t). Clearly a(t) != b(t) or they would be in sync, so they must swap places at step t by moving in the same direction.

Hi, can I modify this code to try to find a shorter string?

I just need the first part the checks if it is a valid string.

@Oliver I... guess, if it's just the validation. Would be interested to see whether alternative search methods have more success.

I'm not getting your point. If a string solves all reachable mazes, why doesn't it solve others? In fact string must visit every cell in every reachable maze, which also solves unreachable cases.

@rus9384 "reachable" is referring to a cell (a square) in a maze. There are unreachable cells, not unreachable mazes. For example, if a square has 4 walls around it then it cannot be reached from any other cell.

@trichoplax Reachable maze is a maze where all cells are reachable from any other.

@rus9384 That's not how the word "reachable" is being used in either the answer or the comments.

@trichoplax, in fact it's enough that string passes through all cells from any starting cell in 189 different mazes (assuming maze count as the same wherever start and finish are). That's what I mean.

@rus9384 I don't yet follow how this works, but if you've found a set of 189 mazes that means you don't have to check any others, that would give a huge improvement in the time taken to check each string. The comments are getting full here but I'd be interested to hear how this works in [chat].

C++ and the library from lingeling

Summary: A new approach, no new solutions, a nice program to play
with, and some interesting results of local non-improvability of the
known solutions. Oh, and some generally useful observations.

Using a SAT
based approach, I could completely
solve
the similar problem for 4x4 mazes with blocked cells instead of thin walls
and fixed start and exit positions at opposite corners.
So I hoped to be able to use the same ideas for this problem.
However, even though for the other problem I only used 2423 mazes
(in the meantime it has been observed that 2083 are enough) and it has
a solution of length 29, the SAT encoding used millions of variables
and solving it took days.
So I decided to change the approach in two important ways:

Don't insist on searching a solution from scratch, but allow to fix
a part of the solution string. (That's easy to do anyway by adding unit
clauses, but my program makes it comfortable to do.)
Don't use all mazes from the beginning. Instead, incrementally add one
unsolved maze at a time. Some mazes may be solved by chance, or they are
always solved when the ones already considered are solved. In the latter
case, it will never be added, without us needing to know the implication.

I also did some optimizations to use less variables and unit clauses.
The program is based on @orlp's.
An important change was the selection of mazes:

First of all, mazes are given by their wall structure and the
start position only. (They also store the reachable positions.)
The function is_solution checks if all reachable positions are reached.
(Unchanged: still not using mazes with only 4 or less reachable positions.
But most of them would be thrown away anyway by the following observations.)
If a maze does not use any of the three top cells, it is equivalent to a
maze that is shifted up. So we can drop it. Likewise for a maze that does
not use any of the three left cells.
It doesn't matter if unreachable parts are connected, so we insist that
each unreachable cell is completely surrounded by walls.
A single path maze that is a submaze of a bigger single path maze is always
solved when the bigger one is solved, so we don't need it. Each single path
maze of size at most 7 is part of a bigger one (still fitting in 3x3), but
there are size 8 single path mazes that aren't. For simpliciy, let's just
drop single path mazes of size less than 8. (And I'm still using that only
the extreme points need to be considered as start positions.
All positions are used as exit positions, which only matters for the SAT
part of the program.)

In this way, I get a total of 10772 mazes with start positions.
Here is the program:
#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
#include <limits>
#include <cassert>

extern "C"{
#include "lglib.h"
}

// reusing a lot of @orlp's ideas and code

enum { N = -8, W = -2, E = 2, S = 8 };
static const int encoded_pos[] = {8, 10, 12, 16, 18, 20, 24, 26, 28};
static const int wall_idx[] = {9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27};
static const int move_offsets[] = { N, E, S, W };
static const uint32_t toppos = 1ull << 8 | 1ull << 10 | 1ull << 12;
static const uint32_t leftpos = 1ull << 8 | 1ull << 16 | 1ull << 24;
static const int unencoded_pos[] = {0,0,0,0,0,0,0,0,0,0,1,0,2,0,0,0,3,
                                    0,4,0,5,0,0,0,6,0,7,0,8};

int do_move(uint32_t walls, int pos, int move) {
  int idx = pos + move / 2;
  return walls & (1ull << idx) ? pos + move : pos;
}

struct Maze {
  uint32_t walls, reach;
  int start;

  Maze(uint32_t walls=0, uint32_t reach=0, int start=0):
    walls(walls),reach(reach),start(start) {}

  bool is_dummy() const {
    return (walls==0);
  }

  std::size_t size() const{
    return std::bitset<32>(reach).count();
  }

  std::size_t simplicity() const{  // how many potential walls aren't there?
    return std::bitset<32>(walls).count();
  }

};

bool cmp(const Maze& a, const Maze& b){
  auto asz = a.size();
  auto bsz = b.size();
  if (asz>bsz) return true;
  if (asz<bsz) return false;
  return a.simplicity()<b.simplicity();
}

uint32_t reachable(uint32_t walls) {
  static int fill[9];
  uint32_t reached = 0;
  uint32_t reached_relevant = 0;
  for (int start : encoded_pos){
    if ((1ull << start) & reached) continue;
    uint32_t reached_component = (1ull << start);
    fill[0]=start;
    int count=1;
    for(int i=0; i<count; ++i)
      for(int m : move_offsets) {
        int newpos = do_move(walls, fill[i], m);
        if (reached_component & (1ull << newpos)) continue;
        reached_component |= 1ull << newpos;
        fill[count++] = newpos;
      }
    if (count>1){
      if (reached_relevant)
        return 0;  // more than one nonsingular component
      if (!(reached_component & toppos) || !(reached_component & leftpos))
        return 0;  // equivalent to shifted version
      if (std::bitset<32>(reached_component).count() <= 4)
        return 0;
      reached_relevant = reached_component;
    }
    reached |= reached_component;
  }
  return reached_relevant;
}

void enterMazes(uint32_t walls, uint32_t reached, std::vector<Maze>& mazes){
  int max_deg = 0;
  uint32_t ends = 0;
  for (int pos : encoded_pos)
    if (reached & (1ull << pos)) {
      int deg = 0;
      for (int m : move_offsets) {
        if (pos != do_move(walls, pos, m))
          ++deg;
      }
      if (deg == 1)
        ends |= 1ull << pos;
      max_deg = std::max(deg, max_deg);
    }
  uint32_t starts = reached;
  if (max_deg == 2){
    if (std::bitset<32>(reached).count() <= 7)
      return; // small paths are redundant
    starts = ends; // need only start at extremal points
  }
  for (int pos : encoded_pos)
    if ( starts & (1ull << pos))
      mazes.emplace_back(walls, reached, pos);
}

std::vector<Maze> gen_valid_mazes() {
  std::vector<Maze> mazes;
  for (int maze_id = 0; maze_id < (1 << 12); maze_id++) {
    uint32_t walls = 0;
    for (int i = 0; i < 12; ++i)
      if (maze_id & (1 << i))
    walls |= 1ull << wall_idx[i];
    uint32_t reached=reachable(walls);
    if (!reached) continue;
    enterMazes(walls, reached, mazes);
  }
  std::sort(mazes.begin(),mazes.end(),cmp);
  return mazes;
};

bool is_solution(const std::vector<int>& moves, Maze& maze) {
  int pos = maze.start;
  uint32_t reached = 1ull << pos;
  for (auto move : moves) {
    pos = do_move(maze.walls, pos, move);
    reached |= 1ull << pos;
    if (reached == maze.reach) return true;
  }
  return false;
}

std::vector<int> str_to_moves(std::string str) {
  std::vector<int> moves;
  for (auto c : str) {
    switch (c) {
    case 'N': moves.push_back(N); break;
    case 'E': moves.push_back(E); break;
    case 'S': moves.push_back(S); break;
    case 'W': moves.push_back(W); break;
    }
  }
  return moves;
}

Maze unsolved(const std::vector<int>& moves, std::vector<Maze>& mazes) {
  int unsolved_count = 0;
  Maze problem{};
  for (Maze m : mazes)
    if (!is_solution(moves, m))
      if(!(unsolved_count++))
    problem=m;
  if (unsolved_count)
    std::cout << "unsolved: " << unsolved_count << "\n";
  return problem;
}

LGL * lgl;

constexpr int TRUELIT = std::numeric_limits<int>::max();
constexpr int FALSELIT = -TRUELIT;

int new_var(){
  static int next_var = 1;
  assert(next_var<TRUELIT);
  return next_var++;
}

bool lit_is_true(int lit){
  int abslit = lit>0 ? lit : -lit;
  bool res = (abslit==TRUELIT) || (lglderef(lgl,abslit)>0);
  return lit>0 ? res : !res;
}

void unsat(){
  std::cout << "Unsatisfiable!\n";
  std::exit(1);
}

void clause(const std::set<int>& lits){
  if (lits.find(TRUELIT) != lits.end())
    return;
  for (int lit : lits)
    if (lits.find(-lit) != lits.end())
      return;
  int found=0;
  for (int lit : lits)
    if (lit != FALSELIT){
      lgladd(lgl, lit);
      found=1;
    }
  lgladd(lgl, 0);
  if (!found)
    unsat();
}

void at_most_one(const std::set<int>& lits){
  if (lits.size()<2)
    return;
  for(auto it1=lits.cbegin(); it1!=lits.cend(); ++it1){
    auto it2=it1;
    ++it2;
    for(  ; it2!=lits.cend(); ++it2)
      clause( {- *it1, - *it2} );
  }
}

/* Usually, lit_op(lits,sgn) creates a new variable which it returns,
   and adds clauses that ensure that the variable is equivalent to the
   disjunction (if sgn==1) or the conjunction (if sgn==-1) of the literals
   in lits. However, if this disjunction or conjunction is constant True
   or False or simplifies to a single literal, that is returned without
   creating a new variable and without adding clauses.                    */

int lit_op(std::set<int> lits, int sgn){
  if (lits.find(sgn*TRUELIT) != lits.end())
    return sgn*TRUELIT;
  lits.erase(sgn*FALSELIT);
  if (!lits.size())
    return sgn*FALSELIT;
  if (lits.size()==1)
    return *lits.begin();
  int res=new_var();
  for(int lit : lits)
    clause({sgn*res,-sgn*lit});
  for(int lit : lits)
    lgladd(lgl,sgn*lit);
  lgladd(lgl,-sgn*res);
  lgladd(lgl,0);
  return res;
}

int lit_or(std::set<int> lits){
  return lit_op(lits,1);
}

int lit_and(std::set<int> lits){
  return lit_op(lits,-1);
}

using A4 = std::array<int,4>;

void add_maze_conditions(Maze m, std::vector<A4> dirs, int len){
  int mp[9][2];
  int rp[9];
  for(int p=0; p<9; ++p)
    if((1ull << encoded_pos[p]) & m.reach)
      rp[p] = mp[p][0] = encoded_pos[p]==m.start ? TRUELIT : FALSELIT;
  int t=0;
  for(int i=0; i<len; ++i){
    std::set<int> posn {};
    for(int p=0; p<9; ++p){
      int ep = encoded_pos[p];
      if((1ull << ep) & m.reach){
        std::set<int> reach_pos {};
        for(int d=0; d<4; ++d){
          int np = do_move(m.walls, ep, move_offsets[d]);
          reach_pos.insert( lit_and({mp[unencoded_pos[np]][t],
                                  dirs[i][d ^ ((np==ep)?0:2)]    }));
        }
        int pl = lit_or(reach_pos);
        mp[p][!t] = pl;
        rp[p] = lit_or({rp[p], pl});
        posn.insert(pl);
      }
    }
    at_most_one(posn);
    t=!t;
  }
  for(int p=0; p<9; ++p)
    if((1ull << encoded_pos[p]) & m.reach)
      clause({rp[p]});
}

void usage(char* argv0){
  std::cout << "usage: " << argv0 <<
    " <string>\n   where <string> consists of 'N', 'E', 'S', 'W' and '*'.\n" ;
  std::exit(2);
}

const std::string nesw{"NESW"};

int main(int argc, char** argv) {
  if (argc!=2)
    usage(argv[0]);
  std::vector<Maze> mazes = gen_valid_mazes();
  std::cout << "Mazes with start positions: " << mazes.size() << "\n" ;
  lgl = lglinit();
  int len = std::strlen(argv[1]);
  std::cout << argv[1] << "\n   with length " << len << "\n";

  std::vector<A4> dirs;
  for(int i=0; i<len; ++i){
    switch(argv[1][i]){
    case 'N':
      dirs.emplace_back(A4{TRUELIT,FALSELIT,FALSELIT,FALSELIT});
      break;
    case 'E':
      dirs.emplace_back(A4{FALSELIT,TRUELIT,FALSELIT,FALSELIT});
      break;
    case 'S':
      dirs.emplace_back(A4{FALSELIT,FALSELIT,TRUELIT,FALSELIT});
      break;
    case 'W':
      dirs.emplace_back(A4{FALSELIT,FALSELIT,FALSELIT,TRUELIT});
      break;
    case '*': {
      dirs.emplace_back();
      std::generate_n(dirs[i].begin(),4,new_var);
      std::set<int> dirs_here { dirs[i].begin(), dirs[i].end() };
      at_most_one(dirs_here);
      clause(dirs_here);
      for(int l : dirs_here)
        lglfreeze(lgl,l);
      break;
      }
    default:
      usage(argv[0]);
    }
  }

  int maze_nr=0;
  for(;;) {
    std::cout << "Solving...\n";
    int res=lglsat(lgl);
    if(res==LGL_UNSATISFIABLE)
      unsat();
    assert(res==LGL_SATISFIABLE);
    std::string sol(len,' ');
    for(int i=0; i<len; ++i)
      for(int d=0; d<4; ++d)
        if (lit_is_true(dirs[i][d])){
          sol[i]=nesw[d];
          break;
    }
    std::cout << sol << "\n";

    Maze m=unsolved(str_to_moves(sol),mazes);
    if (m.is_dummy()){
      std::cout << "That solves all!\n";
      return 0;
    }
    std::cout << "Adding maze " << ++maze_nr << ": " <<
      m.walls << "/" << m.start <<
      " (" << m.size() << "/" << 12-m.simplicity() << ")\n";
    add_maze_conditions(m,dirs,len);
  }
}

First configure.sh and make the lingeling solver, then compile the
program with something like
g++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl, where ... is the
path where lglib.h resp. liblgl.a are, so both could for example be
../lingeling-<version>.
Or just put them in the same directory and do
without the -I and -L options.
The program takes one mandatory command line argument, a string consisting
of N, E, S, W (for fixed directions) or *. So you could search
for a general solution of size 78 by giving a string of 78 *s (in quotes),
or search for a solution starting with NEWS by using NEWS followed by
as many *s as you want for additional steps. As a first test, take your
favourite solution and replace some of the letters with *.
This finds a solution fast for a surprisingly high value of "some".
The program will tell which maze it adds, described by wall structure and
start position, and also give the number of reachable positions and walls.
The mazes are sorted by these criteria, and the first unsolved one is added.
Therefore most added mazes have (9/4), but sometimes others appear as well.
I took the known solution of length 79, and for each group of adjacent 26
letters, tried to replace them with any 25 letters. I also tried to remove
13 letters from the beginning and from the end, and replace them by any 13 at the
beginning and any 12 at the end, and vice versa. Unfortunately, it all came
out unsatisfiable. So, can we take this as indicator that length 79 is
optimal? No, I similarly tried to improve the length 80 solution to length 79,
and that was also not successful.
Finally, I tried combining the beginning of one solution with the end of the
other, and also with one solution transformed by one of the symmetries.
Now I'm running out of interesting ideas, so I decided to show you what I
have, even though it didn't lead to new solutions.

That was a really interesting read. Both the new approach and the different ways of reducing the number of mazes to check. To be a valid answer this will need to include a valid string. It doesn't need to be a new shortest string, just any valid string of any length to give a current score for this approach. I mention this because without a score, the answer will be at risk of deletion, and I'd really like to see it stay.

Also nice work on finding the optimal length solution for the older related challenge!

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Fastest Longest Common Subsequence Finder
Your task is to solve the Longest Common Subsequence problem for n strings of length 1000.
A valid solution to the LCS problem for two or more strings S1, … Sn is any string T of maximal length such that the characters of T appear in all Si, in the same order as in T.
Note that T does not have to be a substring of Si.
We've already solved this problem in the shortest amount of code. This time, size doesn't matter.
Example
The strings axbycz and  xaybzc have 8 common subsequences of length 3:
abc abz ayc ayz xbc xbz xyc xyz

Any of these would be a valid solution for the LCS problem.
Details
Write a full program that solves the LCS problem, as explained above, abiding the following rules:

The input will consist of two or more strings of length 1000, consisting of ASCII characters with code points between 0x30 and 0x3F.

You have to read the input from STDIN.
You have two choices for the input format:

Each string (including the last) is followed by a linefeed.

The strings are chained together with no separator and no trailing linefeed.

The number of strings will be passed as a command-line parameter to your program.

You have to write the output, i.e., any one of the valid solutions to the LCS, to STDOUT, followed by one linefeed.

Your language of choice has to have a free (as in beer) compiler/interpreter for my operating system (Fedora 21).

If you require any compiler flags or a  specific interpreter, please mention it in your post.

Scoring
I will run your code with 2, 3, etc. strings until it takes longer than 120 seconds to print a valid solution. This means that you have 120 seconds for each value of n.
The highest amount of strings for which your code finished in time is your score.
In the event of a tied score of n, the submission that solved the problem for n strings in the shortest time will be declared the winner.
All submissions will be timed on my machine (Intel Core i7-3770, 16 GiB RAM, no swap).
The n strings of the (n-1)th test will be generated by calling rand n (and stripping the linefeeds, if requested), where rand is defined as follows:
rand()
{
    head -c$[500*$1] /dev/zero |
    openssl enc -aes-128-ctr -K 0 -iv $1 |
    xxd -c500 -ps |
    tr 'a-f' ':-?'
}

The key is 0 in the above code, but I reserve the right to change it to an undisclosed value if I suspect anybody of (partially) hardcoding the output.

Can we throw exceptions?

@JamesSmith As long as the output is correct, sure.

Since i'm reading with bufferedreader, can i throw ioexception from public static void main(...)?

@JamesSmith I don't really know Java, so I don't know what that is, but don't worry about exceptions.

@JamesSmith Since code length does not matter for this challenge, can't you simply catch the exceptions?

I could, though I prefer to leave it thrown.

C, n = 3 in ~7 seconds
Algorithm
The algorithm is a direct generalization of the standard dynamic programming solution to n sequences. For 2 strings A and B, the standard recurrence looks like this:
L(p, q) = 1 + L(p - 1, q - 1)           if A[p] == B[q]
        = max(L(p - 1, q), L(p, q - 1)) otherwise

For 3 strings A, B, C I use:
L(p, q, r) = 1 + L(p - 1, q - 1, r - 1)                          if A[p] == B[q] == C[r]
           = max(L(p - 1, q, r), L(p, q - 1, r), L(p, q, r - 1)) otherwise

The code implements this logic for arbitrary values of n.
Efficiency
The complexity of my code is O(s ^ n), with s the length of the strings. Based on what I found, it looks like the problem is NP-complete. So while the posted algorithm is very inefficient for larger values of n, it might actually not be possible to do massively better. The only thing I saw are some approaches that improve efficiency for small alphabets. Since the alphabet is moderately small here (16), that could lead to an improvement. I still predict that nobody will find a legitimate solution that goes higher than n = 4 in 2 minutes, and n = 4 looks ambitious already.
I reduced the memory usage in the initial implementation, so that it could handle n = 4 given enough time. But it only produced the length of the sequence, not the sequence itself. Check the revision history of this post for seeing that code.
Code
Since loops over n-dimensional matrices require more logic than fixed loops, I'm using a fixed loop for the lowest dimension, and only use the generic looping logic for the remaining dimensions.
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define N_MAX 4

int main(int argc, char* argv[]) {
    int nSeq = argc - 1;
    if (nSeq > N_MAX) {
        nSeq = N_MAX;
    }

    char** seqA = argv + 1;

    uint64_t totLen = 1;
    uint64_t lenA[N_MAX] = {0};
    uint64_t offsA[N_MAX] = {1};
    uint64_t offsSum = 0;
    uint64_t posA[N_MAX] = {0};

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        lenA[iSeq] = strlen(seqA[iSeq]);
        totLen *= lenA[iSeq] + 1;

        if (iSeq + 1 < nSeq) {
            offsA[iSeq + 1] = totLen;
        }

        offsSum += offsA[iSeq];
    }

    uint16_t* mat = calloc(totLen, 2);
    uint64_t idx = offsSum;

    for (;;) {
        for (uint64_t pos0 = 0; pos0 < lenA[0]; ++pos0) {
            char firstCh = seqA[0][pos0];
            int isSame = 1;
            uint16_t maxVal = mat[idx - 1];

            for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
                char ch = seqA[iSeq][posA[iSeq]];
                isSame &= (ch == firstCh);

                uint16_t val = mat[idx - offsA[iSeq]];
                if (val > maxVal) {
                    maxVal = val;
                }
            }

            if (isSame) {
                mat[idx] = mat[idx - offsSum] + 1;
            } else {
                mat[idx] = maxVal;
            }

            ++idx;
        }

        idx -= lenA[0];

        int iSeq = 1;
        while (iSeq < nSeq && posA[iSeq] == lenA[iSeq] - 1) {
            posA[iSeq] = 0;
            idx -= (lenA[iSeq] - 1) * offsA[iSeq];
            ++iSeq;
        }
        if (iSeq == nSeq) {
            break;
        }

        ++posA[iSeq];
        idx += offsA[iSeq];
    }

    int score = mat[totLen - 1];

    char* resStr = malloc(score + 1);
    resStr[score] = '\0';

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        posA[iSeq] = lenA[iSeq] - 1;
    }

    idx = totLen - 1;
    int resIdx = score - 1;

    while (resIdx >= 0) {
        char firstCh = seqA[0][posA[0]];
        int isSame = 1;
        uint16_t maxVal = mat[idx - 1];
        int maxIdx = 0;

        for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
            char ch = seqA[iSeq][posA[iSeq]];
            isSame &= (ch == firstCh);

            uint16_t val = mat[idx - offsA[iSeq]];
            if (val > maxVal) {
                maxVal = val;
                maxIdx = iSeq;
            }
        }

        if (isSame) {
            resStr[resIdx--] = firstCh;
            for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
                --posA[iSeq];
            }
            idx -= offsSum;
        } else {
            --posA[maxIdx];
            idx -= offsA[maxIdx];
        }
    }

    free(mat);

    printf("score: %d\n", score);
    printf("%s\n", resStr);

    return 0;
}

Instructions for Running
To run:

Save the code in a file, e.g. lcs.c.
Compile with high optimization options. I used:
clang -O3 lcs.c

On Linux, I would try:
gcc -Ofast lcs.c

Run with 2 to 4 sequences given as command line arguments:
./a.out axbycz xaybzc

Single quote the command line arguments if necessary, since the alphabet used for the examples contains shell special characters.

Results
test2.sh and test3.sh are the test sequences from Dennis. I don't know the correct results, but the output looks at least plausible.
$ ./a.out axbycz xaybzc
score: 3
abc

$ time ./test2.sh
score: 391
16638018802020>3??3232270178;47240;24331395?<=;99=?;178675;866002==23?87?>978891>=9<6<9381992>>7030829?255>6804:=3>:;60<9384=081;0:?66=51?0;5090724<85?>>:2>7>3175?::<9199;5=0:494<5<:7100?=95<91>1887>33>67710==;48<<327::>?78>77<6:2:02:<7=5?:;>97<993;57=<<=:2=9:8=118563808=962473<::8<816<464<1==925<:5:22?>3;65=>=;27?7:5>==3=4>>5>:107:20575347>=48;<7971<<245<??219=3991=<96<??735698;62?<98928

real  0m0.012s
user  0m0.008s
sys   0m0.003s

$ time ./test3.sh
score: 269
662:2=2::=6;738395=7:=179=96662649<<;?82?=668;2?603<74:6;2=04=>6;=6>=121>1>;3=22=3=3;=3344>0;5=7>>7:75238;559133;;392<69=<778>3?593?=>9799<1>79827??6145?7<>?389?8<;;133=505>2703>02?323>;693995:=0;;;064>62<0=<97536342603>;?92034<?7:=;2?054310176?=98;5437=;13898748==<<?4

real  0m7.218s
user  0m6.701s
sys   0m0.513s

Apologies if that wasn't clear, but you have to print the LCS, not just its length.

@Dennis I see. Some of my optimizations were in vain then. I'll have to go back to a version that stores the full matrix so that I can reconstruct the string. That won't be able to run for n=4, but should still finish below 10 seconds for n=3. I think I was around 6-7 seconds when I still had the full matrix.

Again, sorry. The question wasn't very clear about this... When you post your output, I'll be able to compare it to BrainSteel's. The length your program reports exceeds the length of his output by 5 for n=2. By the way, I had to define N_MAX as a macro and add the compiler flag -std=c99 to compile your code with GCC.

@Dennis No problem. It said that the solution "is a string", so that should have been clear enough. I almost exclusively use C++, so I'm never sure what's allowed in C. This code started out as C++, but once I realized that I wasn't really using any C++ features, I switched it over to C. clang on my Mac was happy with it, but it probably uses a different C version by default, or is just more lenient.

@Dennis Ok, I added the traceback logic so that I can produce the string. Takes about 7 seconds now for n=3.

This answer is currently broken due to a bug. Fixing soon...
C, 2 strings in ~35 seconds
This is very much a work in progress (as shown by the horrible messiness), but hopefully it sparks some good answers!
The code:
#include "stdlib.h"
#include "string.h"
#include "stdio.h"
#include "time.h"

/* For the versatility */
#define MIN_CODEPOINT 0x30
#define MAX_CODEPOINT 0x3F
#define NUM_CODEPOINT (MAX_CODEPOINT - MIN_CODEPOINT + 1)
#define CTOI(c) (c - MIN_CODEPOINT)

#define SIZE_ARRAY(x) (sizeof(x) / sizeof(*x))

int LCS(char** str, int num);
int getshared(char** str, int num);
int strcount(char* str, char c);

int main(int argc, char** argv) {
    char** str = NULL;
    int num = 0;
    int need_free = 0;
    if (argc > 1) {
        str = &argv[1];
        num = argc - 1;
    }
    else {
        scanf(" %d", &num);
        str = malloc(sizeof(char*) * num);
        if (!str) {
            printf("Allocation error!\n");
            return 1;
        }

        int i;
        for (i = 0; i < num; i++) {
            /* No string will exceed 1000 characters */
            str[i] = malloc(1001);
            if (!str[i]) {
                printf("Allocation error!\n");
                return 1;
            }

            scanf(" %1000s", str[i]);

            str[i][1000] = '\0';
        }

        need_free = 1;
    }

    clock_t start = clock();

    /* The call to LCS */
    int size = LCS(str, num);

    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("Size: %d\n", size);
    printf("Elapsed time on LCS call: %lf s\n", dt);

    if (need_free) {
        int i;
        for (i = 0; i < num; i++) {
            free(str[i]);
        }
        free(str);
    }

    return 0;
}

/* Some terribly ugly global variables... */
int depth, maximum, mapsize, lenmap[999999][2];
char* (strmap[999999][20]);
char outputstr[1000];

/* Solves the LCS problem on num strings str of lengths len */
int LCS(char** str, int num) {
    /* Counting variables */
    int i, j;

    if (depth + getshared(str, num) <= maximum) {
        return 0;
    }

    char* replace[num];
    char match;
    char best_match = 0;
    int earliest_set = 0;
    int earliest[num];
    int all_late;
    int all_early;
    int future;
    int best_future = 0;
    int need_future = 1;

    for (j = 0; j < mapsize; j++) {
        for (i = 0; i < num; i++)
            if (str[i] != strmap[j][i])
                break;
        if (i == num) {
            best_match = lenmap[j][0];
            best_future = lenmap[j][1];
            need_future = 0;
            if (best_future + depth < maximum || !best_match)
                goto J;
            else {
                match = best_match;
                goto K;
            }
        }
    }

    for (match = MIN_CODEPOINT; need_future && match <= MAX_CODEPOINT; match++) {

    K:
        future = 1;
        all_late = earliest_set;
        all_early = 1;
        for (i = 0; i < num; replace[i++]++) {
            replace[i] = strchr(str[i], match);
            if (!replace[i]) {
                future = 0;
                break;
            }

            if (all_early && earliest_set && replace[i] - str[i] > earliest[i])
                all_early = 0;
            if (all_late && replace[i] - str[i] < earliest[i])
                all_late = 0;
        }
        if (all_late) {
            future = 0;
        }

    I:
        if (future) {
            if (all_early || !earliest_set) {
                for (i = 0; i < num; i++) {
                    earliest[i] = (int)(replace[i] - str[i]);
                }
            }

            /* The recursive bit */
            depth++;
            future += LCS(replace, num);
            depth--;

            best_future = future > best_future ? (best_match = match), future : best_future;
        }
    }

    if (need_future) {
        for (i = 0; i < num; i++)
            strmap[mapsize][i] = str[i];
        lenmap[mapsize][0] = best_match;
        lenmap[mapsize++][1] = best_future;
    }

J:
    if (depth + best_future >= maximum) {
        maximum = depth + best_future;
        outputstr[depth] = best_match;
    }

    if (!depth) {
        mapsize = 0;
        maximum = 0;
        puts(outputstr);
    }

    return best_future;
}

/* Return the number of characters total (not necessarily in order) that the strings all share */
int getshared(char** str, int num) {
    int c, i, tot = 0, min;
    for (c = MIN_CODEPOINT; c <= MAX_CODEPOINT; c++) {
        min = strcount(str[0], c);
        for (i = 1; i < num; i++) {
            int count = strcount(str[i], c);
            if (count < min) {
                min = count;
            }
        }
        tot += min;
    }

    return tot;
}

/* Count the number of occurrences of c in str */
int strcount(char* str, char c) {
    int tot = 0;
    while ((str = strchr(str, c))) {
        str++, tot++;
    }
    return tot;
}

The relevant function that performs all of the LCS computation is the function LCS. The code above will time its own call to this function.
Save as main.c and compile with: gcc -Ofast main.c -o FLCS
The code can be ran either with command line arguments or through stdin. When using stdin, it expects a number of strings followed by the strings themselves.
~ Me$ ./FLCS "12345" "23456"
2345
Size: 4
Elapsed time on LCS call: 0.000056 s

Or:
~ Me$ ./FLCS
6
2341582491248123139182371298371239813
2348273123412983476192387461293472793
1234123948719873491234120348723412349
1234129388234888234812834881423412373
1111111112341234128469128377293477377
1234691237419274737912387476371777273
1241231212323
Size: 13
Elapsed time on LCS call: 0.001594 s

On a Mac OS X box with a 1.7Ghz Intel Core i7 and the test case Dennis provided, we get the following output for 2 strings:
16638018800200>3??32322701784=4240;24331395?<;=99=?;178675;866002==23?87?>978891>=9<66=381992>>7030829?25265804:=3>:;60<9384=081;08?66=51?0;509072488>2>924>>>3175?::<9199;330:494<51:>748571?153994<45<??20>=3991=<962508?7<2382?489
Size: 386
Elapsed time on LCS call: 33.245087 s

The approach is very similar to my approach to the earlier challenge, here. In addition to previous optimization, we now check for a total number of shared characters between strings at every recursion and exit early if there's no way to get a longer substring than what already exists.
For now, it handles 2 strings okay but tends to get crash-y on more. More improvements and a better explanation to come!

I think I have missed something. With 2 strings isn't this a classic dynamic programming problem that should take about 1000^2 steps to solve?  In other words, a fraction of a second.

@Lembik Yeah, it should. This method was built for handling many more than 2 strings, but it ended up scaling too poorly with string length for it to have good results. I've got many more tricks up my sleeve, and if any of them actually work... Things should improve immensely.

There seems to be a problem somewhere. @RetoKoradi's code finds a valid common substring of length 391 for n=2, while your code reports a length of 386 and prints a string of length 229.

@Dennis Umm... Yeah, yeah it does... Oh dear. Well, this is embarrassing. I'm working on it :) I'll edit the answer to reflect the bug.


text:
Is it simple or is it hard?
For your hard thing to do, you must make a thing for a computer to do that finds out if some words are explained in a simple way. Something is explained in a simple way if it only uses the ten hundred most used words. If not, it is explained in a hard way. This can be a full computer thing or part of a computer thing. (full program or function)
There is a thing for a computer to read that has all of the ten hundred words in it with a space between each word. The name of the thing for the computer to read is called 'most used.txt'. You can take this thing from this computer place.
The person who uses the computer thing will enter some words. (This can be from STDIN, function arguments or command line arguments) The computer must say something like a true if the words are simple and something like a not true if it is hard. (truthy-falsy) The person who makes the shortest thing for the computer to do is the best. The things that every person knows are bad are bad. (standard loopholes apply)

More stuff to know about how the computer thing works:

It doesn't matter if the words are BIG or little.
The pictures that make what the word meaning easier to know (punctuation) don't matter. So if the person who uses the computer thing says "dont" it isn't a different word than the word "don't". Numbers and other pictures also don't matter. So if the person says "HE$$ll9o" the computer should read it like "hello"
The little lines between words (dashes) work the same way as spaces. So the word "up-goer-five" is the same as the words "up goer five".

More stuff to know about making words like this:
https://xkcd.com/1133/
http://splasho.com/upgoer5/#

So check the computer thing user's words to the big word thing to see if all the words in the little word thing are in the big word thing?

@Geobits couldn't have said it better myself.

Can the words we check have many lines or can only space come between them?

Maybe it's just me, but I found this exceptionally difficult to read.

@PeterTaylor The words that the person says, or the big words the computer reads?

The words that the person says.

(I'm done talking in up-goer-five) I don't have any objection to having the input on multiple lines, but I don't see how since it would be taken from STDIN followed by an enter,

You don't mention STDIN in the spec, and it's not the only acceptable default. "types some words and hits the enter thing" could mean command line arguments, etc. The simple-talk is funny, but it helps to be clear, and it's not very conducive to that.

It might be better to give a synopsis in simple-talk, followed by an actual spec in "real" English.

Does the dictionary have to be read from a file? That might downright exclude a couple of languages.

You should have had a penalty for every word used which is hard in the program

CJam, 41 bytes
q"file:///most used.txt"g]{el_euS--S%}/-!

This makes the rather unclean assumption that most used.txt is in the root directory, since CJam cannot handle relative paths.
Alternatively, we have the following web-based solutions (78 and 29 bytes):
q"https://docs.google.com/uc?id=0B2sM8IORrbL3RVpJWTZNUy1rOFU"g]{el_euS--S%}/-!

q"j.mp/-o_O"g]{el_euS--S%}/-!

The "proper" way of doing this in CJam would be reading both inputs from STDIN (input on the first line, dictionary on the second), which is possible in 18 bytes:
qN%{el_euS--S%}/-!

You can try the last version in the CJam interpreter. (permalink tested in Chrome)
Examples
$ cjam <(echo 'q"file:///most used.txt"g]{el_euS--S%}/-!') <<< 'ten hundred'; echo
1
$ cjam <(echo 'q"file:///most used.txt"g]{el_euS--S%}/-!') <<< 'thousand'; echo
0

You could use tinyurl on the Drive url to make it shorter

@M.I.Wright Figured it out. That and uploading the file to Pastebin saved 12 bytes. Thanks!

R, 106 bytes
Is not sure if is understand challenge because is has hard time reading.
function(s){u=toupper;all(strsplit(gsub("[^A-Z -']","",u(s)),"[ -]")[[1]]%in%u(scan("most used.txt","")))}

This creates an unnamed part of a computer thing that accepts a string and returns something like a true or like a not true.
Ungolfed + explanation:
partOfAComputerThing <- function(s) {
    # Remove everything but letters, spaces, dashes, and single quotes
    s <- gsub("[^A-Z -']", "", toupper(s))

    # Split s into a vector on spaces/dashes
    v <- strsplit(s, "[ -]")[[1]]

    # Read the file of words (assumed to reside in the current directory)
    m <- scan("most used.txt", "")

    # Determine if all words in the input are in the file
    all(v %in% toupper(m))
}

Thanks to Dennis for inspiration thing.

Something like part-of-a-computer-thing(s){...} should be worth bonus points.

@Dennis: How's this? :)

Much better!

Python 3, 148 bytes
import re
print(all(i in open("most used.txt").read().lower().split(' ')for i in re.sub("[^a-z ']+","",input().replace("-"," ").lower()).split(" ")))

Outputs True and False
Examples
Input:  Don't
Output: True

Input:  The poison air he's breathing has a dirty smell of dying
Output: False

Input:  Who let the dogs out?
Output: False

Will this handle an input of don't correctly?

@AlexA. It returns True. Is that correct?

Any reason you split most used.txt by new lines? I'm not 100% sure on how this works, but I imagine you're trying to split it into each individual word in the file?

@DeadChex What is the supplied text file separated by? I can't access it because it keeps throwing an SSL error.

and for me on Python 3.4.1 running it an typing in don't prints False same with Who let the dogs out? actually.

The question states "There is a thing for a computer to read that has all of the ten hundred words in it with a space between each word"

As for the SSL error, Drive will happily serve it over http http://docs.google.com/uc?id=0B2sM8IORrbL3RVpJWTZNUy1rOFU

Pyth, 35 bytes
!-Fm@LGcrXd\-bZ),zs'"most used.txt

Tests, where the above is the file common.pyth
$ pyth common.pyth <<< 'I can write this way too-hell99#0O.'
True
$ pyth common.pyth <<< 'But I get confused easily.'
False

Explanation:
!-Fm@LGcrXd\-bZ),zs'"most used.txt
   m            ,zs'"most used.txt    Map over input and input file:
         Xd\-b                        Replace hyphens with newlines.
        r     Z                       Cast to lower case.
       c       )                      Split on whitespace.
    @LG                               Remove non-alphabetic characters.
 -F                                   Setwise difference - remove anything in
                                      the text file from the input.
!                                     Logical negation.

APL (Dyalog), 69 bytes
Assumes that the file is in the current directory.
s←819⌶' '(1↓¨,⊂⍨⊣=,)'[- ]' '\W'⎕R' ' ''
∧/(s⍞)∊s⊃⎕NGET'most used.txt'

Try it online!
The first line defines a normalising and splitting-into-list-of-strings helper function, s:
s← s is
819⌶ the lowercased
' '( result of the following function, with a space as left argument…
 1↓¨ drop one from each of
 , the concatenation of the arguments
 ⊂⍨ cut before each element where
 ⊣ the left argument
 = is equal to
 , the concatenation of the arguments
) applied to
'[- ]' '\W'⎕R' ' '' the PCRE replacements dash/space→space, non-word-char→nothing
∧/(…) is it all-true that
 s the normalised and split
 ⍞ text input
∊ are members of
s the normalised and split
⊃ first element of
⎕NGET'most used.txt' the (content, encoding, newline-style) of the file

JavaScript (ES7), 161 bytes
s=>fetch("most used.txt").then(t=>t.text()).then(d=>alert(s.split(/[ -]/g).every(l=>d.split` `.map(w=>w.replace(/[\.']/,"")).includes(l.replace(/[^a-z]/g,"")))))

Anyone got a copy of the file online that I can use to create a working Snippet?

I guess that you can save 22 bytes by removing then and 7 bytes by removing alert.

Can you elaborate, @Titus? Each step of this returns a promise so the thens are required to execute subsequent code when they resolve.

I´m not that familiar with ES7; was thinking in the wrong direction. But maybe you can come up with something shorter if You reduce the input to all words not in the list? I doubt that PHP can really beat JS by almost 40%.

Oh, yeah, there's definitely room for improvement there; this was my last challenge of the day and I had brainache so I posted what I had so far to revisit tomorrow. Unfortunately, the chain of promises required just to get at the contents of a file puts JS at a disadvantage in these challenges against the likes of PHP but it's still better than the alternative of using XHR.

PHP, 101 bytes
foreach(preg_split("#[^\w']+#",$argn)as$w)preg_match("#\b$w\b#i",end(file("most used.txt")))?:die(1);

takes input from STDIN, assumes single line dictionary
exits with 1 (error) for falsy, 0 (ok) for truthy. Run with -R.
Split input by non-word characters, loop through resulting array (words):
If word is in the dictionary, continue; else exit(1).
implicit exit(0).
or, simply put:
one word after another: If word is in the most used words, continue; else return 1.
return 0.
and: I could save two points if the most used words had a space each in front and at the end.

Java, 248 bytes
With the Phrase passed as an argument.
void g(String s) throws Exception{String c=new java.util.Scanner(new java.io.File("most used.txt")).useDelimiter("\\Z").next(),x="false";for(String l:s.split(" "))if(c.contains(l.toLowerCase().replaceAll("![a-z]","")))x="true";System.out.print(x);}

input/output:
g("was he")         --> "true"
g("was h!e")         --> "true"
g("delicious cake") --> "false"

Spaced and tabbed out:
void g(String s) throws Exception{
    String c=new java.util.Scanner(new java.io.File("most used.txt")).useDelimiter("\\Z").next()
      ,x="false";
    for(String l:s.split(" "))
      if(c.contains(l.toLowerCase().replaceAll("![a-z]","")))
          x="true";
    System.out.print(x);
}

What do you mean it's up to you to import what's needed?

@Beta I use some of Java's utility classes that, if you were to put this function in a program you'd have to import (namely java.io.* and java.util.*), much like pythons import statement

Well you have to include these imports in your byte count. You aren't allowed to exclude import statements in Python, so you can't exclude them in Java

@BetaDecay Tweaked the program, no more imports needed