Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ending states) that uses a 4-letter alphabet.
Each maze hence directly corresponds to a regular language. The intersection of all the regular languages is also a regular language with each string in it representing a valid "universal exit string". And we now have to find the shortest such string.
So is there any algorithm, construction, etc that can help us find the shortest such string?
I found this paper by Thomas Ang on googling but couldn't find anything in it I could use in the problem (I could be mistaken).
I'm just making this post to find out if any already existing results/approaches in theoretical CS can be used to solve the problem.
P.S. There's an unofficial bounty on the question if it tempts anyone.