Skip to content

Instantly share code, notes, and snippets.

@daeyun
Last active December 27, 2015 21:49
Show Gist options
  • Save daeyun/7394235 to your computer and use it in GitHub Desktop.
Save daeyun/7394235 to your computer and use it in GitHub Desktop.
C++ Boggle solver. Perform BSF on a graph of 26 vertices.
/* 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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment