+1. It felt very mechanical running through "bard, card, hard, lard, nard, pard, sard, ward, ware, care, dare, fare, hare, mare, nare, pare, tare, bare, bark, dark, hark, lark, mark, nark, park, sark,..." Definitely feels like something a computer could do better than a human. (And the leaderboard confirms it.)

But switching the traversal order to "bard, bare, care, card, hard, hare, dare, dark, hark, hart, cart,..." doesn't seem to make it any more fun.

My suggestion would be to add an "enemy AI" following its own trajectory toward you; your job then is not just to walk around as long as possible, but to stay at least one step ahead of the enemy for a long as possible.

The enemy might not move just one step per turn; it might do something like "stand still for 3 turns, then change 2 letters in a single turn."

Showing the enemy's words to the player would also increase the "discoverability" of paths in the game. The player could say "Oh, apparently NARD is a valid word! I'll remember that for next time."