Bloodnok,
Actually, I started with the premise that it was a weighted undirected graph and tried to find a heuristic algorithm for the longest path problem. Unfortunately, this doesn't work because the graph itself changes every time you make a decision. In other words, what is connected to what (starting at level 2) changes each step you take. Perhaps this works to my advantage (no longer NP complete) but I haven't figured it out - which is why I asked for suggestions.

Cheers - L~R

Each 4 letter word (approximately 4,000)

% grep -c '^....$' enable.lst
3919
[download]

JavaFan,
Actually, I took the Scrabble Tournament Word List and pulled out all 4 letter words. It was a little over (not under) 4000. Some of the games on FaceBook indicate what list they use (this one doesn't) but I have found it is the safest list to use.

Cheers - L~R

On level 2, the rule is "which ever letter you used to form the first word in level 2 can't be used in any word for the remainder of the level

Clarification please. Do you really mean that only the letter used in the first word can't be used thereafter? Or do you mean "which ever letter you used in any previous step can't be used from then on for the remainder of the level" ?

In the first case the graph wouldn't change after the first step, which would really trivially divide the problem into less than 26 unchanging subproblems. Only in the second case there is constant change in the graph

One refinement for level 2 in the second case would be to pick random pairs of expensive words (without any letter common to the first word of level 2) and look for an expensive path of 4 words between them. For every row of 6 words found this way check if there is a path from the first word of level 2 to either end of this row (since you can turn around the row without invalidating it).

Example:

First word in level 2 is "bean". Now randomly find two words that have neither 'b','e','a' and 'n' in them and no common letter between them. For example "womb" and "pixy". Now look for a string of 4 words between "womb" and "pixy" using no letter from "bean" inbetween. Since 4 of the 5 letters needed to change from womb to pixy are already known ('p','i','x' and 'y'), an exhaustive search of routes between the two words should be very fast.

If you find such a route (which should be very expensive since you could freely select 8 out of the 9 letters), you now would look for a route from 'bean' to either 'womb' or 'pixy' with 3 words inbetween, also rather trivial as the letters to use are all fixed.

jethro,
Rather than fail with words, I will try not to fail with an example:

Level 1
9:  moon
10: noon
Level 2
11: loon
(Can not use 'l' for the rest of level 2)
[download]

Actually, I think it is the letter to make the last word from level 1 that becomes unavailable for level 2 but it really doesn't change the problem. Perhaps I haven't worked with graphs and graph theory enough to understand how continuing to think about this as a graph helps. According to Wikipedia, this is an NP complete problem. Since I indicated I am fine with a suboptimal solution I want to stick to something simple and fast. Do you think this approach would produce solutions consistently better than my drop dead simple approach outline in the root node with a run-time under an hour?

Cheers - L~R

Well, this doesn't really answer my questions, since the two cases start to differ from 12 on. In the first case:

12: loop
(Can not use 'l' for the rest of level 2)

In the second case:

12: loop
(Can not use 'l' and 'p' for the rest of level 2)

Anyway: I assume you meant the first case. Then level 2 is just as easy (or difficult) as level 1, the only difference is that after step 11 (or 10) one character is blacklisted

Whether the algorithm I proposed would give better solutions probably depends on the density of words to non-words. In our case that would be 4000/ 26^4 = 1/114. I.e. only one in 114 four-letter combinations is a real word.

To find a path from the start word to one of the two words of the 6-word-chain one of the 48 combinations of intermediate words would have to be made out of real words, this happens once every approximately 114^3 /48 = 31000 times. The ratio is even worse because you are looking for expensive words that are probably not as well connected as the average word.

To be somewhat sure that you get at least one solution the program should at least be able to test 20 times as many word chains in the alloted run-time, lets say 31000 times 20 = 600.000 test per hour or 170 tests a second. So you have to find 170 valid chains of 6 words a second, rather a tall order. I think in this scenario the density is maybe too low for my algorithm to have much success.

Level 2 sounds like it could be represented by 26 copies of the original graph, with a subset of the nodes (those containing the letter you chose to use first) removed from each copy. You essentially must choose which of the 26 variant subgraphs you want to play in, and then throw the others away.

Level 3 could be four copies of the graph, but for each link, you alter it to point to the corresponding node in Copy #N if that link changes letter #N. Then clean up by deleting any links that go from Copy N to Copy M where N==M.
The graph will have to become directed, since you can go from moon(1) to mood(4) or mood(1) to moon(4) but not mood(4) to moon(1)

SuicideJunkie,
Yes, I am sure one could continue to think in terms of graphs but do you think it will be of any use. In other words, I think it becomes more complex not less. At least, more complex than I am willing to invest to wow and amaze friends.

Cheers - L~R

#!/usr/bin/perl

use 5.010;

use strict;
use warnings;
use autodie;

my $dict = "word_list";
my $size = 4;

open my $fh, "<", $dict;
my @words = <$fh>;
close $fh;
chomp @words;

my $start = @ARGV ? shift : $words[rand @words];
my $runs  = @ARGV ? shift :  1000;

my %words = map {$_ => 1} @words;
my %graph;
my %freq;
my %score;

foreach my $word (@words) {
    foreach my $index (0 .. $size - 1) {
        $graph{$word}[$index] = {};
        foreach my $c ('a' .. 'z') {
            my $w1 = $word;
            substr $w1, $index, 1, $c;
            next if $w1 eq $word;
            next unless $words{$w1};
            $graph{$word}[$index]{$c} = $w1;
        }
    }
    $freq{$_}++ for split //, $word;
}
my $tot_letters = $size * @words;
foreach (keys %freq) {
    $freq{$_} = 1 - $freq{$_} / $tot_letters;
}

foreach my $word (@words) {
    $score{$word} += $freq{$_} for split //, $word;
}

my $best_score = 0;
my @best;

for (1 .. $runs) {
    my @list;
    my %seen;
    my $forbidden = " ";
    my $changed = $size;

    push @list, $start;
    $seen{$start} = 1;
    
    while (1) {
        my $turn = @list + 1;
        my $current = $list[-1];
        #
        # Get all possibilities. 
        #
        my @nbs;
        
        for (my $i = 0; $i < @{$graph{$current}}; $i++) {
            next if $i == $changed && $turn >= 21;
            my $l = $graph{$current}[$i];
            next unless $l;
            my @letters = grep {$_ ne $forbidden} keys %$l;
            push @nbs, $$l{$_} for @letters; 
        }
        #
        # Filter out things we've seen.
        #
        @nbs = grep {!$seen{$_}} @nbs;
        last unless @nbs;  # End of the line.

        my $pick = $nbs[rand @nbs];
        push @list, $pick;
        $seen{$pick}++;
    
        foreach my $i (0 .. $size - 1) {
            next if substr($list[-2], $i, 1) eq substr($list[-1], $i, 
+1);
            $changed = $i;
            last;
        }
    
        if ($turn == 11) {
            $forbidden = substr $list[-1], $changed, 1;
        }
        elsif ($turn == 21) {   
            $forbidden = " ";
        }
    }
        
    my $score = 0;
       $score += $score{$_} for @list;
            
    if ($score > $best_score) {
        @best = @list;
        $best_score = $score;
    }
}
         
for (my $i = 0; $i < @best; $i++) {
    printf "%3d %s\n", $i + 1, $best[$i];
}
say "$start: list of ", scalar @best, " words. Score: $best_score";

__END__
[download]

JavaFan,
I will clean my code up and post what I have later. It doesn't do a DFS as I have found I almost never need to backtrack. I have only made it to level 13 but that was enough to become the all-time high score for all of FaceBook.

Cheers - L~R