It's a false conclusion. His non-determinisitic algorithm is decidedly less efficient than A*: it's essentially following a similar algorithm except it's randomly choosing what node to expand next, sometimes repeating expanding the same node.
The author of the blog post used a deterministic algorithm; he observed some of his users using a non-deterministic one that appeared to work better.
The fact that the algorithm is executed by a human matters, because the human processing system is optimised for highly parallel tasks, such as estimating which of many possible next moves is most likely to improve the solution.
The problem can most certainly be solved with A* or one of its variants.
Just because a problem is NP-complete doesn't preclude the use of deterministic algorithms. For example, you can solve small instances of TSPs with standard search techniques.
I'm not sure what distinction you're trying to make with your last statement.
Can you explain how you'd solve this using A* efficiently? You will see what I mean. A* finds the shortest path, this problem requires a Hamiltonian cycle, two entirely different problems.
Finding a Hamiltonian cycle has much more in common with solving a sudoku puzzle than with finding the shortest path in a graph; both are problems for which no polynomial time algorithm is known. Now, this problem is about finding a Hamiltonian cycle in a restricted class of graphs, so there is a chance that you could solve it efficiently, but it is non obvious. If you know how, perhaps you should publish a paper on it: that might be a major breakthrough.
A-star is not limited to performing just pathfinding; consider it more a graph traversal algorithm (which fits well with this state space). I would use one variant in particular, IDA-star, for solving this game. If we consider one or more nodes connected together as a "cluster", starting with an "empty cluster", the start state is a set of clusters, and the end state is one single cluster that represents a cycle. A "move" would connect two clusters together.
There is nothing particularly publish-worthy although it would make an interesting state space for a graduate-level AI class assignment.
(Another state space -- game -- that we can use A-star to solve are sliding tile games, which have nothing outwardly to do with pathfinding per se.)
What you are describing is exhaustive search on the state space and is orders of magnitude slower than the randomized algorithm, especially when executed by humans (which is why I added the qualifier "efficiently"). Also, A* is for finding the shortest path, and the length of the path in this case is irrelevant. In fact the length of all paths is the same.
