49

18

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

**, and the exit is reachable from the start. The start and exit are never the same cell.**

*exit*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.

3This 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? – Alex Van Liew – 2015-07-31T18:43:52.473

@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. – trichoplax – 2015-07-31T19:33:41.710

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. – trichoplax – 2015-07-31T19:38:24.747

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! – Alex Van Liew – 2015-07-31T21:12:14.887

@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... – trichoplax – 2015-07-31T21:27:42.123

Can the exit be the center cell? – Alex Reinking – 2015-08-03T19:34:01.157

1@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. – trichoplax – 2015-08-03T23:30:32.273

1

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 – 2015-08-04T12:40:55.507@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... – trichoplax – 2015-08-04T18:53:13.473

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? – proud haskeller – 2015-08-04T19:39:43.653

1@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. – trichoplax – 2015-08-04T21:24:33.920

@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. – trichoplax – 2015-08-05T10:35:44.5032Has 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. – Kyle McCormick – 2015-08-09T03:47:38.123

The link to the python 3 validator is dead. – NonlinearFruit – 2017-05-19T23:04:02.810

@NonlinearFruit thanks for letting me know - I've fixed the link now – trichoplax – 2017-05-19T23:16:47.863

@AlexVanLiew, if NP-complete problems can't be effectively solved, almost surely optimal solution won't be found. – rus9384 – 2017-09-13T10:40:43.167

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 – 2018-10-15T14:56:08.177

@tuskiomi so as quantum computers progress we'll get increasing lower bounds on the optimal solution until eventually we find it... – trichoplax – 2018-10-15T19:31:35.723

@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. – tuskiomi – 2018-10-15T19:36:19.757

Can we call out to the validator you've written, in our code? – Stackstuck – 2019-03-25T16:42:02.553

@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... :) – trichoplax – 2019-03-25T21:36:49.393

Yeah, I have absolutely

noidea how they're doing it. I was just planning on exhaustively searching. – Stackstuck – 2019-03-26T02:10:38.590