Really?

OP isn't right that this is greedy either. What your users are doing is an iterative search with a backoff strategy. They pursue one path through the search space, and when they don't find the solution, they remove some links (backing off) and try a new path through the search space.

The clever bit is whether you can automate their decision mechanism for how they're proceeding through the space step by step, and what points you can fall back to when something does wrong (and how to recognize when you've gone wrong).

The fact that people can do this by the seat of their pants somewhat shouldn't come as a surprise to people who study cognitive psychology, but certainly might be a surprise to engineers. After all, that's why everyone who's not a social scientist loves Malcolm Gladwell's books.

Iterative search with a backoff strategy is called backtracking, no? Seems an obvious way of solving the problem, especially since if I was to write a solver I'd definitively do it in Prolog.

I've heard it called a bunch of stuff, but yep, that's one of 'em! Sorry i was writing while exhausted :)

To pick a nit, I don't think the human, "cognitive" strategy really has any "back-off."

In my experience (playing Monorail!) the "fast" approach is basically guess, repair, repair, repair, ... If you're trying to keep a mental stack of tentative moves to "undo," as many people do, e.g. when doing a Sudoku, that's a different, more "logical" approach, to me. The fast approach has no state except the current state of the board.

What I'm saying is that you shouldn't draw such general conclusions from seeing a simple algorithm work in a particular case. Your problem-game turned out to be algorithmically simple. This probably makes it more appealing as a game. But most things in life will not be as simple, and this includes large coding projects.

What you call the repair step I see as running the greedy algorithm again, from a different node in the search graph.

The conclusion I drew from this experience was that I should get over my fear of making mistakes. I could have been more clear on that in the post.

There's probably some optimal level of fear-of-mistakes for any given project. Monorail made me realize my brain was tuned too far in the fear direction. I stand by that generalization.

"It turns out to be easier and faster to iterate from an existing but wrong solution, than to deduce a correct solution from scratch. Even if you have to occassionally press the “clear” button to start over."

This is what I was referring to. Yes, if you tackle coding projects that are challenging mostly by size and not by algorithmic difficulty, simply plowing ahead is the right attitude. But sometimes you will encounter real challenges, and for those you will need all the top-down design and logical tricks that you can muster. To the extent that my personal experience is relevant, for my PhD thesis I've designed and implemented a novel algorithm. I went through three non-functional versions before I realized that I actually needed to spell everything out on paper first, before writing a single line of code. After that, I was done in two weeks.

Something tells me trying and failing three times contributed much more to your solution than writing everything out on paper.

Can you define "algorithmically simple"? This looks like hamiltonian cycle with an extra constraint that there is one bounded region. I wouldn't be surprised if this problem was NP-hard.

You're right, there are probably instances of this problem for which greedy algorithms are quite slow.

"iterate and repair" is a pretty standard form of local optimum search, like in http://en.wikipedia.org/wiki/Hill_climbing or simulated annealing. Why are you surprised that works for exploring the decision tree of a puzzle game?

Regular expression search is often greedy and also repairs by next examining a less greedy partial solution