Schedule a 4-way stop

Question

A bunch of cars are lined up at a 4-way stop sign waiting to proceed. Everyone is confused about who gets to go next, who is going which way, etc. Clearly suboptimal.

Your job is to schedule the traffic at the stop sign in an optimal fashion.

You receive as input 4 strings of turn requests, one for each of the four cardinal directions. Each request is either L for left, S for straight, or R for right.

LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL

The first row is the lineup at the North entrance to the intersection. The first car in line wishes to turn left (that is, exit East). The subsequent rows are for the incoming East, South, and West entrances. So the first car coming from the West wishes to exit South.

Traffic moves in a series of steps. At each step, you must choose a subset of the cars at the head of their lines to proceed. The cars chosen must not interfere with each other. Two cars interfere if they exit the same direction or if they must cross each other's path (given standard right-hand driving rules). So two opposite cars both wishing to go straight may go at the same step. So may 4 cars all wishing to turn right. Two opposite cars can both turn left simultaneously.

Your job is to schedule the intersection in a minimum series of steps. For each step, output a line with the incoming cars' compass direction(s) listed. For the example above, the minimal schedule is 14 steps. One minimal schedule is:

N    [L from North]
E    [S from East]
E    [S from East]
E    [S from East]
NESW [L from North, R from East, L from South, R from West]
NE   [S from North]
EW   [R from East]
NESW [L from North, R from East, L from South, R from West]
W    [L from West]
EW   [L from East, L from West]
NESW [R from North, L from East, R from South, L from West]
NES  [L from North, R from East, L from West]
NS   [S from North, S from South]
SW   [R from South, L from West]

Your program should be able to handle 50 cars in each line in under 1 minute. Input of the 4 strings and output of the schedule may be in any convenient manner for your language.

Shortest program wins.

A larger example:

RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL
LLLRRRSSRSLRSSSSLLRRRR

which requires a minimum of 38 rounds. One possible solution:

E
EW
E
ESW
S
NS
ES
NESW
NSW
ESW
ES
NSW
NS
NS
NW
EW
NSW
NS
EW
NES
EW
NSW
NE
E
NE
EW
E
E
EW
EW
EW
W
ESW
NSW
NSW
NS
NSW
NEW

Answer 1

Python, 1219 Bytes

I didn't spend very much time/effort trying to golf this, but I might improve it if other answers start popping up. I use A* search with an admissible heuristic, guaranteeing optimality. I am pretty sure (although I haven't bothered to confirm) that the heuristic is also consistent, meaning that it is O(dynamic programming).

The program reads in four lines from STDIN in the format you have specified, and prints the result to STDOUT, also in the format you specified.

from heapq import heappush,heappop
from itertools import combinations
N,E,S,W=range(4)
L="L"
R="R"
T="S"
d=[{L:E,R:W,T:S},{L:S,R:N,T:W},{L:W,R:E,T:N},{L:N,R:S,T:E}]
b=set([(N,S,W,E),(N,S,E,W),(S,N,W,E),(S,N,E,W),(E,W,N,E),(N,S,W,N),(S,N,E,S),(W,E,S,W)])
for x in list(b):b.add(x[2:]+x[:2])
def v(*a):return a[1]!=a[3] and a not in b
i=lambda:raw_input()+'\n'
i=map(lambda l:map(lambda e:("NESW"[l[0]],d[l[0]][e]), l[1]),enumerate((i()+i()+i()+i()).split()))
q=[]
heappush(q,(0,[],i))
while q:
    h,a,n=heappop(q)
    m=sum(map(bool,n))
    if m==0:
        print "\n".join(a)
        break
    for r in range(4,0,-1):
        f=False
        for c in combinations(range(4),r):
            l=True
            for i in c:
                if not n[i]:
                    l=False
                    break
            if not l:continue
            l=True
            for x,y in combinations(c,2):
                if not v(x,n[x][0][1],y,n[y][0][1]):
                    l = False
                    break
            if l==False:continue
            f=True
            e=list(n)
            for i in c:e[i]=e[i][1:]
            heappush(q,(m-r+min(map(len,e)),a+["".join([n[x][0][0] for x in c])],e))
        if f:break

Example usage:

$ time echo "RRLLSSRLSLLSSLRSLR\nRLSLRLSLSSRLRLRRLLSSRLR\nRLSLRLRRLSSLSLLRLSSL\nLLLRRRSSRSLRSSSSLLRRRR" | python 4way.py
NES
NEW
NSW
NS
NS
ESW
NS
NES
NEW
NS
NES
NSW
NS
NS
NSW
NW
NS
NS
NS
EW
ES
SW
EW
EW
SW
ES
EW
EW
EW
EW
E
EW
EW
EW
EW
EW
E
EW
echo   0.00s user 0.00s system 38% cpu 0.002 total
python 4way.py  0.02s user 0.01s system 90% cpu 0.030 total