I just downloaded his article, and he states that "With the advent of computers, algorithms for maze solving have become automated, but the solution times still

I just downloaded his article, and he states that "With the advent of computers, algorithms for maze solving have become automated, but the solution times still scale unfavorably with maze size/complexity" and then references a paper by Dijkstra (Dijkstra, E. W. Numer. Math. 1959, 1, 269.). That might be true for dense graphs, if you think that O(|V|^2 log|V|) is unfavourable. A normal maze graph is planar and therefore |V| <= 3|E| - 6. Thus, maze problems can always be solved in O(|V| log|V|) time for a constant number of exits and starting points. So, while the author made a little mathematical blunder ( single layer maze problems are efficient to solve), he's not the one that implied NP-completeness. EDIT: Clarified my comment so that no-one can think I'm implying that an O(|V|^2 log|V|) algorithm is an NP problem.