C++ Boggle solver. Perform BSF on a graph of 26 vertices.

boggle.cpp

/* Author: Daeyun Shin */
#include<map>
#include<cassert>
#include<queue>
using namespace std;
map<char, map<char, bool> > graph;

int boggle(int board[4][4], const char * word) {
    // populate the graph
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            char c = board[i][j];
            for (int p = i - 1; p <= i + 1; p++) {
                for (int q = j - 1; q <= j + 1; q++) {
                    if (p < 0 || p > 3 || q < 0 || q > 3 || (p==i && q==j)) {
                        continue;
                    }
                    graph[c][board[p][q]] = true;
                }
            }
        }
    }

    // perform BFS upto level 4
    queue<char> source;
    queue<char> target;

    int index = 0;
    int level = 1;
    char c = *(word + index);
    source.push(c);

    while(true) {
        index ++;
        c = *(word + index);

        bool is_char_found = false;
        while(!source.empty()) {
            char item = source.front();
            source.pop();

            for (map<char, bool>::iterator it = graph.at(item).begin();
                    it != graph.at(item).end(); it++) {
                if (it->first == c) {
                    target.push(it->first);
                    is_char_found = true;
                }
            }
        }
        if (!is_char_found) {
            return false;
        }
        level ++;
        if (level > 3) {
            return true;
        }
        swap(target, source);
    }
}

int main() {
    int board[4][4] = {
        {'S', 'M', 'E', 'F'},
        {'R', 'A', 'T', 'D'},
        {'L', 'O', 'N', 'I'},
        {'K', 'A', 'F', 'B'}
    };
    
    // Test boggle()
    assert(boggle(board, "TONE") == false);
    assert(boggle(board, "STAR") == false);
    assert(boggle(board, "NODE") == false);
    assert(boggle(board, "ABCD") == false);
    assert(boggle(board, "BIDO") == false);
    assert(boggle(board, "BIDM") == false);
    assert(boggle(board, "BIDS") == false);
    assert(boggle(board, "KLAD") == false);

    assert(boggle(board, "FIND") == true);
    assert(boggle(board, "BIND") == true);
    assert(boggle(board, "RANT") == true);
    assert(boggle(board, "NOTE") == true);
    assert(boggle(board, "SAND") == true);
    assert(boggle(board, "KLAF") == true);
    assert(boggle(board, "FINF") == true);
    assert(boggle(board, "BIDF") == true);
    assert(boggle(board, "BIDT") == true);
}