Return to Question

• I removed the Qt dependencies from the code here so that hopefully anyone can compile it if they want. I use the command g++ -o solver -O3 -std=gnu++11 -Wall solver.cpp main.cpp. You will have to grab trie.h from here and a word list from here on GitHub.
• Just yesterday, I tried to optimize the code a little by using a std::set with a custom compare functor to store words and remove duplicates, but I ended up losing some solutions that way.
• I figured out how to store words in a std::set in a way that works now, although the functor seems pretty inefficient. It has good results though. On one hard puzzle, the old code produced 239,711 solutions. The new code produces 195,489. I verified that the lost solutions are duplicates. The time difference between the two versions is negligible.

I suppose I have the usual questions:

• Is the code readable and understandable?
• What improvements can I make to the code or algorithms?
• What can I do to improve performance besides attempting multi-threading?

#ifndef SOLVER_H
#define SOLVER_H

#include <algorithm>
#include <array>
#include <memory>
#include <string>
#include <vector>

#include "solutionentry.h"
#include "trie.h"

class Solver
{

private:

    typedef std::vector<unsigned int> tIntVec;
    typedef std::vector<SolutionEntry> tSolution;

    enum { NullIndex = -1 };
    enum { NullNeighbor = -1, MaxNeighbors = 64 };

public:

    Solver();
    Solver(const std::string &board, int size, const tIntVec &wordlengths,
           const std::string &wordfile);
    ~Solver();

    bool solve();

    void setBoard(const std::string &board)
    {
        mBoard = board;
    }

    void setSize(int size)
    {
        mSize = size;
        mSizeSquared = size * size;
    }

    void setWordLengths(const tIntVec &wordlengths)
    {
        mWordLengths = wordlengths;
    }

    void setWordFile(const std::string &wordfile)
    {
        if (mWordFile != wordfile) {
            mWordFile = wordfile;
        }
    }

    tIntVec getWordLengths() {
        return mWordLengths;
    }

private:
    
    struct WordCompare {
        bool operator()(const std::pair<std::string, tIntVec> &lhs, 
                        const std::pair<std::string, tIntVec> &rhs) const {
            auto leftVector = lhs.second;
            auto rightVector = rhs.second;
            std::sort(leftVector.begin(), leftVector.end());
            std::sort(rightVector.begin(), rightVector.end());
            
            return (lhs.first != rhs.first) || (leftVector != rightVector);
        }
    };

    bool findSolutions(const std::string &board, const tIntVec &wordpath,
                       unsigned int depth = 0);

    void findWords(const std::string &board, int index,
                   unsigned int wordlength, unsigned int depth = 0);

    std::array<int, MaxNeighbors>
    neighbors(const std::string &board, int index) const;

    std::string removeWord(const std::string &board, tIntVec word) const;

    bool initializeDictionary();
    void cleanUp();
    void printSolution() const;

    // Board parameters
    std::string mBoard;
    unsigned int mSize;
    tIntVec mWordLengths;
    std::string mWordFile;
    unsigned int mSizeSquared;

    // Solver variables
    tSolution mSolution;
    tIntVec mWord;
    std::string mPrefix;
    std::set<std::pair<std::string, tIntVec>, WordCompare> mWordList;
    std::unique_ptr<trie_t> mDictionary;

    const int mNeighborDx[8];
    const int mNeighborDy[8];

};

#endif // SOLVER_H

#include <algorithm>
#include <cctype>
#include <chrono>
#include <fstream>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <thread>

#include "solutionentry.h"
#include "trie.h"
#include "solver.h"

Solver::Solver()
    : mDictionary(nullptr),
      mNeighborDx{ -1, 0, 1, -1, 1, -1, 0, 1 },
      mNeighborDy{ -1, -1, -1, 0, 0, 1, 1, 1 }
{ }

Solver::Solver(const std::string &board, int size, const tIntVec &wordlengths,
               const std::string &wordfile)
    : mBoard(board),
      mSize(size),
      mWordLengths(wordlengths),
      mWordFile(wordfile),
      mDictionary(nullptr),
      mNeighborDx{ -1, 0, 1, -1, 1, -1, 0, 1 },
      mNeighborDy{ -1, -1, -1, 0, 0, 1, 1, 1 }
{
    mSizeSquared = mSize * mSize;
}

Solver::~Solver()
{
    cleanUp();
}

bool Solver::solve()
{
    if (!initializeDictionary()) {
        std::cerr << "Unable to initialize the dictionary\n";
        return false;
    }

    cleanUp();
    
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    
    findSolutions(mBoard, tIntVec());

    end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;

    std::cout << elapsed_seconds.count() << '\n';
    
    return true;
}

bool Solver::findSolutions(const std::string &board, const Solver::tIntVec &wordpath,
                           unsigned int depth)
{
    // A complete solution has been found
    if (depth == mWordLengths.size()) {
        printSolution();
        mSolution.pop_back();
        return true;
    }

    // Remove current word from the board
    std::string newBoard = removeWord(board, wordpath);

    // Find any words that may exist on the new board
    mWordList.clear();
    findWords(newBoard, Solver::NullIndex, mWordLengths[depth]);
    auto currentWords = mWordList;

    for (const auto &word : currentWords) {
        mSolution.push_back(SolutionEntry(word.second, newBoard, depth));
        findSolutions(newBoard, word.second, depth + 1);
    }

    if (!mSolution.empty()) {
        mSolution.pop_back();
    }

    return true;
}

void Solver::findWords(const std::string &board, int index,
                       unsigned int wordlength, unsigned int depth)
{
    // We have a valid word
    if (depth == wordlength && mDictionary->isWord(mPrefix)) {
        mWordList.insert(std::make_pair(mPrefix, mWord));
        mWord.pop_back();
        mPrefix.pop_back();
        return;
    }

    for (const auto n : neighbors(board, index)) {
        // Visit a neighbor only if we haven't encountered it before
        if (n != Solver::NullNeighbor &&
            std::find(mWord.begin(), mWord.end(), n) == mWord.end()) {
            mWord.push_back(n);
            mPrefix += board[n];

            // Recursive step
            if (mDictionary->isPrefix(mPrefix)) {
                findWords(board, n, wordlength, depth + 1);
            } else {
                mWord.pop_back();
                mPrefix.pop_back();
            }
        }
    }

    if (!mWord.empty()) {
        mWord.pop_back();
    }

    if (!mPrefix.empty()) {
        mPrefix.pop_back();
    }
}

std::array<int, Solver::MaxNeighbors>
Solver::neighbors(const std::string &board, int index) const
{
    std::array<int, Solver::MaxNeighbors> n{};
    n.fill(Solver::NullNeighbor);

    // Return consecutive integers from 0 to mSizeSquared
    if (index == Solver::NullIndex) {
        std::iota(n.begin(), n.begin() + mSizeSquared, 0);
        return n;
    }

    // Otherwise, return the actual neighbors of the letter at index
    int x, y, pos;
    int row = index / mSize;
    int col = index % mSize;
    for (int i = 0, j = 0; i < 8; ++i) {
        x = row + mNeighborDx[i];
        y = col + mNeighborDy[i];
        pos = x * mSize + y;
        if (x >= 0 && static_cast<unsigned int>(x) < mSize &&
            y >= 0 && static_cast<unsigned int>(y) < mSize && board[pos] != ' ') {
            n[j] = pos;
            ++j;
        }
    }

    return n;
}

std::string Solver::removeWord(const std::string &board, Solver::tIntVec word) const
{
    std::string newBoard(board);
    std::sort(word.begin(), word.end());

    for (const auto &n : word) {
        // Remove the letter at index n
        newBoard[n] = ' ';

        // Move the letters above n down one position
        int index = n - mSize;
        while (index >= 0) {
            if (newBoard[index] == ' ') {
                index -= mSize;
            } else {
                char tmp = newBoard[index];
                newBoard[index] = ' ';
                newBoard[index + mSize] = tmp;
                index -= mSize;
            }
        }
    }

    return newBoard;
}

bool Solver::initializeDictionary()
{
    std::ifstream inf(mWordFile);

    if (inf.is_open()) {
        mDictionary.reset(new trie_t);
        std::string curWord;

        while (inf >> curWord) {
            std::transform(curWord.begin(), curWord.end(), curWord.begin(),
                           [](unsigned char ch){ return std::tolower(ch); });
            if (curWord.find_first_not_of("abcdefghijklmnopqrstuvwxyz") == std::string::npos) {
                for (const auto &length : mWordLengths) {
                    // Only add words of the length we'll be working with
                    if (curWord.length() == length) {
                        mDictionary->addWord(curWord);
                        break;
                    }
                }
            }
        }

        inf.close();
        return true;
    } else {
        std::cerr << "Unable to open file " << mWordFile;
        return false;
    }
}

void Solver::cleanUp()
{
    mSolution.clear();
    mWord.clear();
    mWordList.clear();
    mPrefix.clear();
}

void Solver::printSolution() const
{
    for (const auto &s : mSolution) {
        std::cout << s.getWord() << " ";
    }
    std::cout << '\n';
}

• I removed the Qt dependencies from the code here so that hopefully anyone can compile it if they want. I use the command g++ -o solver -O3 -std=gnu++11 -Wall solver.cpp main.cpp. You will have to grab trie.h from here and a word list from here on GitHub.
• Just yesterday, I tried to optimize the code a little by using a std::set with a custom compare functor to store words and remove duplicates, but I ended up losing some solutions that way.
• I figured out how to store words in a std::set in a way that works now, although the functor seems pretty inefficient. It has good results though. On one hard puzzle, the old code produced 239,711 solutions. The new code produces 195,489. I verified that the lost solutions are duplicates. The time difference between the two versions is negligible.
• Changed where I push back onto mWord. On harder puzzles, this results in millions or billions fewer calls to push_back and no calls to pop_back. Hardly any savings as far as runtime, but I'll take it.

• Is the code readable and understandable?
• I do a LOT of string concatenation in findWords with the statement mPrefix += board[n]; and the results stand out in my profiling with callgrind. Is std::string as good as I can get here?
• What can I do to improve performance besides attempting multi-threading?
• What improvements can I make to the code or algorithms in general?

#ifndef SOLVER_H
#define SOLVER_H

#include <algorithm>
#include <array>
#include <memory>
#include <set>
#include <string>
#include <vector>

#include "solutionentry.h"
#include "trie.h"

class Solver
{

private:

    typedef std::vector<unsigned int> tIntVec;
    typedef std::vector<SolutionEntry> tSolution;

    enum { NullIndex = -1 };
    enum { NullNeighbor = -1, MaxNeighbors = 64 };

public:

    Solver();
    Solver(const std::string &board, int size, const tIntVec &wordlengths,
           const std::string &wordfile);
    ~Solver();

    bool solve();

    void setBoard(const std::string &board)
    {
        mBoard = board;
    }

    void setSize(int size)
    {
        mSize = size;
        mSizeSquared = size * size;
    }

    void setWordLengths(const tIntVec &wordlengths)
    {
        mWordLengths = wordlengths;
    }

    void setWordFile(const std::string &wordfile)
    {
        if (mWordFile != wordfile) {
            mWordFile = wordfile;
        }
    }

    tIntVec getWordLengths() {
        return mWordLengths;
    }

private:
    
    struct WordCompare {
        bool operator()(const std::pair<std::string, tIntVec> &lhs, 
                        const std::pair<std::string, tIntVec> &rhs) const {
            auto leftVector = lhs.second;
            auto rightVector = rhs.second;
            std::sort(leftVector.begin(), leftVector.end());
            std::sort(rightVector.begin(), rightVector.end());
            
            return (lhs.first != rhs.first) || (leftVector != rightVector);
        }
    };

    bool findSolutions(const std::string &board, const tIntVec &wordpath,
                       unsigned int depth = 0);

    void findWords(const std::string &board, int index,
                   unsigned int wordlength, unsigned int depth = 0);

    std::array<int, MaxNeighbors>
    neighbors(const std::string &board, int index) const;

    std::string removeWord(const std::string &board, tIntVec word) const;

    bool initializeDictionary();
    void cleanUp();
    void printSolution() const;

    // Board parameters
    std::string mBoard;
    unsigned int mSize;
    tIntVec mWordLengths;
    std::string mWordFile;
    unsigned int mSizeSquared;

    // Solver variables
    tSolution mSolution;
    tIntVec mWord;
    std::string mPrefix;
    std::set<std::pair<std::string, tIntVec>, WordCompare> mWordList;
    std::unique_ptr<trie_t> mDictionary;

    const int mNeighborDx[8];
    const int mNeighborDy[8];

};

#endif // SOLVER_H

#include <algorithm>
#include <cctype>
#include <chrono>
#include <fstream>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <thread>

#include "solutionentry.h"
#include "trie.h"
#include "solver.h"

Solver::Solver()
    : mDictionary(nullptr),
      mNeighborDx{ -1, 0, 1, -1, 1, -1, 0, 1 },
      mNeighborDy{ -1, -1, -1, 0, 0, 1, 1, 1 }
{ }

Solver::Solver(const std::string &board, int size, const tIntVec &wordlengths,
               const std::string &wordfile)
    : mBoard(board),
      mSize(size),
      mWordLengths(wordlengths),
      mWordFile(wordfile),
      mDictionary(nullptr),
      mNeighborDx{ -1, 0, 1, -1, 1, -1, 0, 1 },
      mNeighborDy{ -1, -1, -1, 0, 0, 1, 1, 1 }
{
    mSizeSquared = mSize * mSize;
}

Solver::~Solver()
{
    cleanUp();
}

bool Solver::solve()
{
    if (!initializeDictionary()) {
        std::cerr << "Unable to initialize the dictionary\n";
        return false;
    }

    cleanUp();
    
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    
    findSolutions(mBoard, tIntVec());

    end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;

    std::cout << elapsed_seconds.count() << '\n';
    
    return true;
}

bool Solver::findSolutions(const std::string &board, const Solver::tIntVec &wordpath,
                           unsigned int depth)
{
    // A complete solution has been found
    if (depth == mWordLengths.size()) {
        printSolution();
        mSolution.pop_back();
        return true;
    }

    // Remove current word from the board
    std::string newBoard = removeWord(board, wordpath);

    // Find any words that may exist on the new board
    mWordList.clear();
    findWords(newBoard, Solver::NullIndex, mWordLengths[depth]);
    auto currentWords = mWordList;

    for (const auto &word : currentWords) {
        mSolution.push_back(SolutionEntry(word.second, newBoard, depth));
        findSolutions(newBoard, word.second, depth + 1);
    }

    if (!mSolution.empty()) {
        mSolution.pop_back();
    }

    return true;
}

void Solver::findWords(const std::string &board, int index,
                       unsigned int wordlength, unsigned int depth)
{
    // We have a valid word
    if (depth == wordlength && mDictionary->isWord(mPrefix)) {
        mWordList.insert(std::make_pair(mPrefix, mWord));
        mWord.pop_back();
        mPrefix.pop_back();
        return;
    }

    for (const auto n : neighbors(board, index)) {
        // Visit a neighbor only if we haven't encountered it before
        if (n != Solver::NullNeighbor &&
            std::find(mWord.begin(), mWord.end(), n) == mWord.end()) {
            mPrefix += board[n];
            if (mDictionary->isPrefix(mPrefix)) {
                // Recursive step
                mWord.push_back(n);
                findWords(board, n, wordlength, depth + 1);
            } else {
                mPrefix.pop_back();
            }
        }
    }

    if (!mWord.empty()) {
        mWord.pop_back();
    }

    if (!mPrefix.empty()) {
        mPrefix.pop_back();
    }
}

std::array<int, Solver::MaxNeighbors>
Solver::neighbors(const std::string &board, int index) const
{
    std::array<int, Solver::MaxNeighbors> n{};
    n.fill(Solver::NullNeighbor);

    // Return consecutive integers from 0 to mSizeSquared
    if (index == Solver::NullIndex) {
        std::iota(n.begin(), n.begin() + mSizeSquared, 0);
        return n;
    }

    // Otherwise, return the actual neighbors of the letter at index
    int x, y, pos;
    int row = index / mSize;
    int col = index % mSize;
    for (int i = 0, j = 0; i < 8; ++i) {
        x = row + mNeighborDx[i];
        y = col + mNeighborDy[i];
        pos = x * mSize + y;
        if (x >= 0 && static_cast<unsigned int>(x) < mSize &&
            y >= 0 && static_cast<unsigned int>(y) < mSize && board[pos] != ' ') {
            n[j] = pos;
            ++j;
        }
    }

    return n;
}

std::string Solver::removeWord(const std::string &board, Solver::tIntVec word) const
{
    std::string newBoard(board);
    std::sort(word.begin(), word.end());

    for (const auto &n : word) {
        // Remove the letter at index n
        newBoard[n] = ' ';

        // Move the letters above n down one position
        int index = n - mSize;
        while (index >= 0) {
            if (newBoard[index] == ' ') {
                index -= mSize;
            } else {
                char tmp = newBoard[index];
                newBoard[index] = ' ';
                newBoard[index + mSize] = tmp;
                index -= mSize;
            }
        }
    }

    return newBoard;
}

bool Solver::initializeDictionary()
{
    std::ifstream inf(mWordFile);

    if (inf.is_open()) {
        mDictionary.reset(new trie_t);
        std::string curWord;

        while (inf >> curWord) {
            std::transform(curWord.begin(), curWord.end(), curWord.begin(),
                           [](unsigned char ch){ return std::tolower(ch); });
            if (curWord.find_first_not_of("abcdefghijklmnopqrstuvwxyz") == std::string::npos) {
                for (const auto &length : mWordLengths) {
                    // Only add words of the length we'll be working with
                    if (curWord.length() == length) {
                        mDictionary->addWord(curWord);
                        break;
                    }
                }
            }
        }

        inf.close();
        return true;
    } else {
        std::cerr << "Unable to open file " << mWordFile;
        return false;
    }
}

void Solver::cleanUp()
{
    mSolution.clear();
    mWord.clear();
    mWordList.clear();
    mPrefix.clear();
}

void Solver::printSolution() const
{
    for (const auto &s : mSolution) {
        std::cout << s.getWord() << " ";
    }
    std::cout << '\n';
}

• I removed the Qt dependencies from the code here so that hopefully anyone can compile it if they want. I use the command g++ -o solver -O3 -std=gnu++11 -Wall solver.cpp main.cpp. You will have to grab trie.h from here and a word list from here on GitHub.
• Just yesterday, I tried to optimize the code a little by using a std::set with a custom compare functor to store words and remove duplicates, but I ended up losing some solutions that way.

#ifndef SOLVER_H
#define SOLVER_H

#include <array>
#include <memory>
#include <string>
#include <vector>

#include "solutionentry.h"
#include "trie.h"

class Solver
{

private:

    typedef std::vector<unsigned int> tIntVec;
    typedef std::vector<SolutionEntry> tSolution;

    enum { NullIndex = -1 };
    enum { NullNeighbor = -1, MaxNeighbors = 64 };

public:

    Solver();
    Solver(const std::string &board, int size, const tIntVec &wordlengths,
           const std::string &wordfile);
    ~Solver();

    bool solve();

    void setBoard(const std::string &board)
    {
        mBoard = board;
    }

    void setSize(int size)
    {
        mSize = size;
        mSizeSquared = size * size;
    }

    void setWordLengths(const tIntVec &wordlengths)
    {
        mWordLengths = wordlengths;
    }

    void setWordFile(const std::string &wordfile)
    {
        if (mWordFile != wordfile) {
            mWordFile = wordfile;
        }
    }

    tIntVec getWordLengths() {
        return mWordLengths;
    }

private:

    bool findSolutions(const std::string &board, const tIntVec &wordpath,
                       unsigned int depth = 0);

    void findWords(const std::string &board, int index,
                   unsigned int wordlength, unsigned int depth = 0);

    std::array<int, MaxNeighbors>
    neighbors(const std::string &board, int index) const;

    std::string removeWord(const std::string &board, tIntVec word) const;

    bool initializeDictionary();
    void cleanUp();
    void printSolution() const;

    // Board parameters
    std::string mBoard;
    unsigned int mSize;
    tIntVec mWordLengths;
    std::string mWordFile;
    unsigned int mSizeSquared;

    // Solver variables
    tSolution mSolution;
    tIntVec mWord;
    std::string mPrefix;
    std::vector<tIntVec> mWordList;
    std::unique_ptr<trie_t> mDictionary;

    const int mNeighborDx[8];
    const int mNeighborDy[8];

};

#endif // SOLVER_H

#include <algorithm>
#include <cctype>
#include <chrono>
#include <fstream>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <thread>

#include "solutionentry.h"
#include "trie.h"
#include "solver.h"

Solver::Solver()
    : mDictionary(nullptr),
      mNeighborDx{ -1, 0, 1, -1, 1, -1, 0, 1 },
      mNeighborDy{ -1, -1, -1, 0, 0, 1, 1, 1 }
{ }

Solver::Solver(const std::string &board, int size, const tIntVec &wordlengths,
               const std::string &wordfile)
    : mBoard(board),
      mSize(size),
      mWordLengths(wordlengths),
      mWordFile(wordfile),
      mDictionary(nullptr),
      mNeighborDx{ -1, 0, 1, -1, 1, -1, 0, 1 },
      mNeighborDy{ -1, -1, -1, 0, 0, 1, 1, 1 }
{
    mSizeSquared = mSize * mSize;
}

Solver::~Solver()
{
    cleanUp();
}

bool Solver::solve()
{
    if (!initializeDictionary()) {
        std::cerr << "Unable to initialize the dictionary\n";
        return false;
    }

    cleanUp();
    
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    
    findSolutions(mBoard, tIntVec());

    end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;

    std::cout << elapsed_seconds.count() << '\n';
    
    return true;
}

bool Solver::findSolutions(const std::string &board, const Solver::tIntVec &wordpath,
                           unsigned int depth)
{
    // A complete solution has been found
    if (depth == mWordLengths.size()) {
        printSolution();
        mSolution.pop_back();
        return true;
    }

    // Remove current word from the board
    std::string newBoard = removeWord(board, wordpath);

    // Find any words that may exist on the new board
    mWordList.clear();
    findWords(newBoard, Solver::NullIndex, mWordLengths[depth]);
    auto currentWords = mWordList;

    for (const auto &word : currentWords) {
        mSolution.push_back(SolutionEntry(word, newBoard, depth));
        findSolutions(newBoard, word, depth + 1);
    }

    if (!mSolution.empty()) {
        mSolution.pop_back();
    }

    return true;
}

void Solver::findWords(const std::string &board, int index,
                       unsigned int wordlength, unsigned int depth)
{
    // We have a valid word
    if (depth == wordlength && mDictionary->isWord(mPrefix)) {
        //mWordList.push_back(mWord);
        mWordList.push_back(mWord);
        mWord.pop_back();
        mPrefix.pop_back();
        return;
    }

    for (const auto n : neighbors(board, index)) {
        // Visit a neighbor only if we haven't encountered it before
        if (n != Solver::NullNeighbor &&
            std::find(mWord.begin(), mWord.end(), n) == mWord.end()) {
            mWord.push_back(n);
            mPrefix += board[n];

            // Recursive step
            if (mDictionary->isPrefix(mPrefix)) {
                findWords(board, n, wordlength, depth + 1);
            } else {
                mWord.pop_back();
                mPrefix.pop_back();
            }
        }
    }

    if (!mWord.empty()) {
        mWord.pop_back();
    }

    if (!mPrefix.empty()) {
        mPrefix.pop_back();
    }
}

std::array<int, Solver::MaxNeighbors>
Solver::neighbors(const std::string &board, int index) const
{
    std::array<int, Solver::MaxNeighbors> n{};
    n.fill(Solver::NullNeighbor);

    // Return consecutive integers from 0 to mSizeSquared
    if (index == Solver::NullIndex) {
        std::iota(n.begin(), n.begin() + mSizeSquared, 0);
        return n;
    }

    // Otherwise, return the actual neighbors of the letter at index
    int x, y, pos;
    int row = index / mSize;
    int col = index % mSize;
    for (int i = 0, j = 0; i < 8; ++i) {
        x = row + mNeighborDx[i];
        y = col + mNeighborDy[i];
        pos = x * mSize + y;
        if (x >= 0 && static_cast<unsigned int>(x) < mSize &&
            y >= 0 && static_cast<unsigned int>(y) < mSize && board[pos] != ' ') {
            n[j] = pos;
            ++j;
        }
    }

    return n;
}

std::string Solver::removeWord(const std::string &board, Solver::tIntVec word) const
{
    std::string newBoard(board);
    std::sort(word.begin(), word.end());

    for (const auto &n : word) {
        // Remove the letter at index n
        newBoard[n] = ' ';

        // Move the letters above n down one position
        int index = n - mSize;
        while (index >= 0) {
            if (newBoard[index] == ' ') {
                index -= mSize;
            } else {
                char tmp = newBoard[index];
                newBoard[index] = ' ';
                newBoard[index + mSize] = tmp;
                index -= mSize;
            }
        }
    }

    return newBoard;
}

bool Solver::initializeDictionary()
{
    std::ifstream inf(mWordFile);

    if (inf.is_open()) {
        mDictionary.reset(new trie_t);
        std::string curWord;

        while (inf >> curWord) {
            std::transform(curWord.begin(), curWord.end(), curWord.begin(),
                           [](unsigned char ch){ return std::tolower(ch); });
            if (curWord.find_first_not_of("abcdefghijklmnopqrstuvwxyz") == std::string::npos) {
                for (const auto &length : mWordLengths) {
                    // Only add words of the length we'll be working with
                    if (curWord.length() == length) {
                        mDictionary->addWord(curWord);
                        break;
                    }
                }
            }
        }

        inf.close();
        return true;
    } else {
        std::cerr << "Unable to open file " << mWordFile;
        return false;
    }
}

void Solver::cleanUp()
{
    mSolution.clear();
    mWord.clear();
    mWordList.clear();
    mPrefix.clear();
}

void Solver::printSolution() const
{
    for (const auto &s : mSolution) {
        std::cout << s.getWord() << " ";
    }
    std::cout << '\n';
}

• I removed the Qt dependencies from the code here so that hopefully anyone can compile it if they want. I use the command g++ -o solver -O3 -std=gnu++11 -Wall solver.cpp main.cpp. You will have to grab trie.h from here and a word list from here on GitHub.
• Just yesterday, I tried to optimize the code a little by using a std::set with a custom compare functor to store words and remove duplicates, but I ended up losing some solutions that way.
• I figured out how to store words in a std::set in a way that works now, although the functor seems pretty inefficient. It has good results though. On one hard puzzle, the old code produced 239,711 solutions. The new code produces 195,489. I verified that the lost solutions are duplicates. The time difference between the two versions is negligible.

#ifndef SOLVER_H
#define SOLVER_H

#include <algorithm>
#include <array>
#include <memory>
#include <string>
#include <vector>

#include "solutionentry.h"
#include "trie.h"

class Solver
{

private:

    typedef std::vector<unsigned int> tIntVec;
    typedef std::vector<SolutionEntry> tSolution;

    enum { NullIndex = -1 };
    enum { NullNeighbor = -1, MaxNeighbors = 64 };

public:

    Solver();
    Solver(const std::string &board, int size, const tIntVec &wordlengths,
           const std::string &wordfile);
    ~Solver();

    bool solve();

    void setBoard(const std::string &board)
    {
        mBoard = board;
    }

    void setSize(int size)
    {
        mSize = size;
        mSizeSquared = size * size;
    }

    void setWordLengths(const tIntVec &wordlengths)
    {
        mWordLengths = wordlengths;
    }

    void setWordFile(const std::string &wordfile)
    {
        if (mWordFile != wordfile) {
            mWordFile = wordfile;
        }
    }

    tIntVec getWordLengths() {
        return mWordLengths;
    }

private:
    
    struct WordCompare {
        bool operator()(const std::pair<std::string, tIntVec> &lhs, 
                        const std::pair<std::string, tIntVec> &rhs) const {
            auto leftVector = lhs.second;
            auto rightVector = rhs.second;
            std::sort(leftVector.begin(), leftVector.end());
            std::sort(rightVector.begin(), rightVector.end());
            
            return (lhs.first != rhs.first) || (leftVector != rightVector);
        }
    };

    bool findSolutions(const std::string &board, const tIntVec &wordpath,
                       unsigned int depth = 0);

    void findWords(const std::string &board, int index,
                   unsigned int wordlength, unsigned int depth = 0);

    std::array<int, MaxNeighbors>
    neighbors(const std::string &board, int index) const;

    std::string removeWord(const std::string &board, tIntVec word) const;

    bool initializeDictionary();
    void cleanUp();
    void printSolution() const;

    // Board parameters
    std::string mBoard;
    unsigned int mSize;
    tIntVec mWordLengths;
    std::string mWordFile;
    unsigned int mSizeSquared;

    // Solver variables
    tSolution mSolution;
    tIntVec mWord;
    std::string mPrefix;
    std::set<std::pair<std::string, tIntVec>, WordCompare> mWordList;
    std::unique_ptr<trie_t> mDictionary;

    const int mNeighborDx[8];
    const int mNeighborDy[8];

};

#endif // SOLVER_H

#include <algorithm>
#include <cctype>
#include <chrono>
#include <fstream>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <thread>

#include "solutionentry.h"
#include "trie.h"
#include "solver.h"

Solver::Solver()
    : mDictionary(nullptr),
      mNeighborDx{ -1, 0, 1, -1, 1, -1, 0, 1 },
      mNeighborDy{ -1, -1, -1, 0, 0, 1, 1, 1 }
{ }

Solver::Solver(const std::string &board, int size, const tIntVec &wordlengths,
               const std::string &wordfile)
    : mBoard(board),
      mSize(size),
      mWordLengths(wordlengths),
      mWordFile(wordfile),
      mDictionary(nullptr),
      mNeighborDx{ -1, 0, 1, -1, 1, -1, 0, 1 },
      mNeighborDy{ -1, -1, -1, 0, 0, 1, 1, 1 }
{
    mSizeSquared = mSize * mSize;
}

Solver::~Solver()
{
    cleanUp();
}

bool Solver::solve()
{
    if (!initializeDictionary()) {
        std::cerr << "Unable to initialize the dictionary\n";
        return false;
    }

    cleanUp();
    
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    
    findSolutions(mBoard, tIntVec());

    end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;

    std::cout << elapsed_seconds.count() << '\n';
    
    return true;
}

bool Solver::findSolutions(const std::string &board, const Solver::tIntVec &wordpath,
                           unsigned int depth)
{
    // A complete solution has been found
    if (depth == mWordLengths.size()) {
        printSolution();
        mSolution.pop_back();
        return true;
    }

    // Remove current word from the board
    std::string newBoard = removeWord(board, wordpath);

    // Find any words that may exist on the new board
    mWordList.clear();
    findWords(newBoard, Solver::NullIndex, mWordLengths[depth]);
    auto currentWords = mWordList;

    for (const auto &word : currentWords) {
        mSolution.push_back(SolutionEntry(word.second, newBoard, depth));
        findSolutions(newBoard, word.second, depth + 1);
    }

    if (!mSolution.empty()) {
        mSolution.pop_back();
    }

    return true;
}

void Solver::findWords(const std::string &board, int index,
                       unsigned int wordlength, unsigned int depth)
{
    // We have a valid word
    if (depth == wordlength && mDictionary->isWord(mPrefix)) {
        mWordList.insert(std::make_pair(mPrefix, mWord));
        mWord.pop_back();
        mPrefix.pop_back();
        return;
    }

    for (const auto n : neighbors(board, index)) {
        // Visit a neighbor only if we haven't encountered it before
        if (n != Solver::NullNeighbor &&
            std::find(mWord.begin(), mWord.end(), n) == mWord.end()) {
            mWord.push_back(n);
            mPrefix += board[n];

            // Recursive step
            if (mDictionary->isPrefix(mPrefix)) {
                findWords(board, n, wordlength, depth + 1);
            } else {
                mWord.pop_back();
                mPrefix.pop_back();
            }
        }
    }

    if (!mWord.empty()) {
        mWord.pop_back();
    }

    if (!mPrefix.empty()) {
        mPrefix.pop_back();
    }
}

std::array<int, Solver::MaxNeighbors>
Solver::neighbors(const std::string &board, int index) const
{
    std::array<int, Solver::MaxNeighbors> n{};
    n.fill(Solver::NullNeighbor);

    // Return consecutive integers from 0 to mSizeSquared
    if (index == Solver::NullIndex) {
        std::iota(n.begin(), n.begin() + mSizeSquared, 0);
        return n;
    }

    // Otherwise, return the actual neighbors of the letter at index
    int x, y, pos;
    int row = index / mSize;
    int col = index % mSize;
    for (int i = 0, j = 0; i < 8; ++i) {
        x = row + mNeighborDx[i];
        y = col + mNeighborDy[i];
        pos = x * mSize + y;
        if (x >= 0 && static_cast<unsigned int>(x) < mSize &&
            y >= 0 && static_cast<unsigned int>(y) < mSize && board[pos] != ' ') {
            n[j] = pos;
            ++j;
        }
    }

    return n;
}

std::string Solver::removeWord(const std::string &board, Solver::tIntVec word) const
{
    std::string newBoard(board);
    std::sort(word.begin(), word.end());

    for (const auto &n : word) {
        // Remove the letter at index n
        newBoard[n] = ' ';

        // Move the letters above n down one position
        int index = n - mSize;
        while (index >= 0) {
            if (newBoard[index] == ' ') {
                index -= mSize;
            } else {
                char tmp = newBoard[index];
                newBoard[index] = ' ';
                newBoard[index + mSize] = tmp;
                index -= mSize;
            }
        }
    }

    return newBoard;
}

bool Solver::initializeDictionary()
{
    std::ifstream inf(mWordFile);

    if (inf.is_open()) {
        mDictionary.reset(new trie_t);
        std::string curWord;

        while (inf >> curWord) {
            std::transform(curWord.begin(), curWord.end(), curWord.begin(),
                           [](unsigned char ch){ return std::tolower(ch); });
            if (curWord.find_first_not_of("abcdefghijklmnopqrstuvwxyz") == std::string::npos) {
                for (const auto &length : mWordLengths) {
                    // Only add words of the length we'll be working with
                    if (curWord.length() == length) {
                        mDictionary->addWord(curWord);
                        break;
                    }
                }
            }
        }

        inf.close();
        return true;
    } else {
        std::cerr << "Unable to open file " << mWordFile;
        return false;
    }
}

void Solver::cleanUp()
{
    mSolution.clear();
    mWord.clear();
    mWordList.clear();
    mPrefix.clear();
}

void Solver::printSolution() const
{
    for (const auto &s : mSolution) {
        std::cout << s.getWord() << " ";
    }
    std::cout << '\n';
}

My approach is just brute force. I have one recursive function findWords() to find words on the board, and another recursive function findSolutions() that uses those words to find complete solutions. I look for every possible permutation of words and solutions. I believe these are both DFS algorithms. I'm hoping that the code is fairly self-explanatory, but that is one of the reasons I'm here. If anyone wants more details (for example, the initial conditions of the recursive functions), I'd be happy to explain them here.

• For findWords, I use a trie data structure defined in trie.h (not shown here) that makes it very convenient to test whether a set of letters is a valid prefix (e.g. qu is valid, qz is not), and whether it is a valid word at the end. I did not write this code. It is available here. It's not licensed. Unless the author intends to license his/her work, my project will remain a personal one on my computer.
• The code here is part of a larger Qt GUI that I wrote, hence the Q_OBJECT, emit, signals and slots, etc.
• My use of a fixed-size std::array and mSizeSquared for neighbors() together resulted in about a 30% increase in performance vs. using a vector and mSize*mSize.
• I tried a different approach to findWords() once. Rather than looking for prefixes on the board and seeing if they exist in the dictionary, I tried the reverse. I looked at the words in the dictionary and checked whether they existed on the board. I thought this might reduce the search space. However, it was slower... Maybe my implementation was flawed.

My approach is just brute force. I have one recursive function findWords() to find words on the board, and another recursive function findSolutions() that uses those words to find complete solutions. I look for every possible permutation of words and solutions. I believe these are both DFS algorithms. I'm hoping that the code is fairly self-explanatory, but that is one of the reasons I'm here.

I decided to represent the game board as a string of characters. For example, "abcdefghi" might be a 3x3 board. To begin solving, findSolutions() calls findWords(), which in turn calls neighbors(). Neighbors are defined as the indexes of letters adjacent to the letter we're currently looking at in findWords(). A typical result of neighbors might be { 1, 3, 4, -1, -1, ... } (the -1s are filler since I use a fixed size std::array). findWords() recurses over the neighbors until a word is found (or not). Note that a "word" is just another set of indexes.

findSolutions() uses the same type of algorithm. Using a word passed in from the previous level of recursion, it removes that word from the board and calls findWords() to find words on that new board. It then recurses over those words until it finds a complete solution. Solutions are packed into a vector of SolutionEntry, which makes solutions easy to deal with in the Qt GUI.

• For findWords, I use a trie data structure defined in trie.h (not shown here) that makes it very convenient to test whether a set of letters is a valid prefix (e.g. qu is valid, qz is not), and whether it is a valid word at the end. I did not write this code. It is available here. It's not licensed. Unless the author intends to license his/her work, my project will remain a personal one on my computer.
• The code here is part of a larger Qt GUI that I wrote, hence the Q_OBJECT, emit, signals and slots, etc.
• My use of a fixed-size std::array and mSizeSquared for neighbors() together resulted in about a 30% increase in performance vs. using a vector and mSize*mSize.
• I tried a different approach to findWords() once. Rather than looking for prefixes on the board and seeing if they exist in the dictionary, I tried the reverse. I looked at the words in the dictionary and checked whether they existed on the board. I thought this might reduce the search space. However, it was slower... Maybe my implementation was flawed.

Updates

• I removed the Qt dependencies from the code here so that hopefully anyone can compile it if they want. I use the command g++ -o solver -O3 -std=gnu++11 -Wall solver.cpp main.cpp. You will have to grab trie.h from here and a word list from here on GitHub.
• Just yesterday, I tried to optimize the code a little by using a std::set with a custom compare functor to store words and remove duplicates, but I ended up losing some solutions that way.