PHP anagram puzzle solver

Question

I'm trying to find a solution to a PHP puzzle solver I'm working on.

It's an anagram solver that needs to fill a 4x4 grid with the 4-letter anagrams of the 16 letters in "Message to swimmer".

The horizontal rows and vertical columns need to make completed 4-letter anagrams of the phrase. Below is the desired outcome, but my program must solve it by itself.

S M O G
W E R E
I T E M
M A S S

My attempts at creating this are timing out. I'm trying something like this:

foreach($word_array as $word){

    $board = array();   
    $available = $default_array;
    $row1 = $trie->run_word_check($word[0],$available);

    if($row1){
        echo "current row1 check: ". $row1."<br/>";
        remove_from_available($row1,$available);
        $board[] = $row1;
        $col1 = $trie->run_word_check($row1[0],$available);

        if($col1){
            echo "current col1 check: ". $col1."<br/>";
            remove_from_available($col1,$available);
            $board[] = $col1;
            $row2 = $trie->run_word_check($col1[0],$available);

            if($row2){
                echo "current row2 check: ". $row2."<br/>";
                remove_from_available($row2,$available);
                $board[] = $row2;
                $col2 = $trie->run_word_check($row1[1].$row2[1],$available);

                if($col2){
                    etc...
                }
            }
        }
    }
}

Answer 1

Here is how you could do it:

• Preprocess your list of 4-letter words, so that you have them as keys (with value 1 or whatever), and also every prefix of it. So when you have a key for 'SWIM', you also will have one for 'S', 'SW', and 'SWI'. That will be useful to quickly check if after choosing a few characters whether there is still a possibility to complete a 4-letter word.

• Preprocess the 16-letter input string: store the individual letters as keys, with the value equal to the number of occurrences in that string. So for 'Message to swimmer', the key 'S' would have value 3.

• Maintain 4 horizontal words and 4 vertical words. Of course, there is some redundancy in this (because the vertical ones can be derived from the horizontal ones), but it will help to have them quickly accessible. These two arrays of 4 words, will start out with all empty strings.

• Then take a letter from that second array (i.e. the available letters with their counts) to use for position 0,0 in the grid, and so store it as the first horizontal word and as first vertical word. Check that there are 4-letter words that start with this.

• If there are 4-letter words possibilities, then use recursion to take a next letter to place at 1,0 in the grid. Add that letter to the first horizontal word (so now it has 2 characters) and put it in the second vertical word (there it will be just that 1 character). Make the check again.

• Repeat the recursion until either all elements in the grid are populated or no letter can be found that, when adding it to the appropriate horizontal and vertical word, yields something that cannot be further completed to match 4-letter words. In that latter case, backtrack and try other characters.

The above is a rough description. Here is the code:

$solution = anagram("Message to swimmer", get_words());
print_r ($solution);

function index_words($word_array) {
    $dict = [ '' => 1 ];
    foreach ($word_array as $word) {
        for ($len = 1; $len <= 4; $len++) {
            $dict[substr($word, 0, $len)] = 1;
        }
    }
    return $dict;
}

function letter_counts($available) {
    $letters = [];
    foreach(str_split(strtoupper($available)) as $letter) {
        if (ctype_alpha($letter)) {
            $letters[$letter] = isset($letters[$letter]) ? $letters[$letter]+1 : 1;
        }
    }
    return $letters;
}

function anagram($available, $word_array) { // Main algorithm
    $dict = index_words($word_array); //keys = all 4 letter words, and all their prefixes
    $letters = letter_counts($available); // key = letter, value = occurrence count
    $hori = ['','','','']; // store the words that are formed horizontally per row
    $vert = ['','','','']; // store the words that are formed horizontally per column

    $recurse = function ($row, $col) 
               use (&$recurse, &$letters, &$dict, &$hori, &$vert, &$limit) {
        if ($row == 4) return true; // all done. backtrack out of recursion
        $h = $hori[$row];
        $v = $vert[$col];
        foreach($letters as $letter => $count) { // for each available character
            if (!$count) continue; // not available any more
            $word1 = $h . $letter;
            $word2 = $v . $letter;
            if (isset($dict[$word1]) && isset($dict[$word2])) {
                // It is still possible to form 4-letter words after placing this letter
                $hori[$row] = $word1;
                $vert[$col] = $word2;
                $letters[$letter]--; 
                // use recursion to find characters for next slots in the grid
                if ($recurse($row + ($col == 3 ? 1 : 0), ($col + 1) % 4)) return true;
                // backtrack
                $letters[$letter]++;
            }
        }
        $hori[$row] = $h;
        $vert[$col] = $v;
    };
    $recurse(0, 0); // start the recursive placement of letters in the grid
    return $hori; // return the 4 words that were placed horizontally
}

function get_words() { // returns a comprehensive list of 4 letter words
    return [
'AAHS', 'AALS', 'ABAC', 'ABAS', 'ABBA', 'ABBE', 'ABBS', 'ABED', 'ABET', 'ABID', 'ABLE', 
/* etc... long list of 4-letter words ... */
'ZOOM', 'ZOON', 'ZOOS', 'ZOOT', 'ZORI', 'ZOUK', 'ZULU', 'ZUPA', 'ZURF', 'ZYGA', 'ZYME', 
'ZZZS'];
}   

You can see it run on eval.in.

With the 4 letter words published here, it finds the following solution in less than 0.2 seconds:

M E G S
O W R E
M E A T
I S M S

... the result depends on the words list of course. I had to look up what OWRE means ;-)