# Unboggler

# Boggle

Boggle is a classic board game in which players search for words constructed by connecting adjacent tiles in a grid of letters. Letters can be used at most once, and are allowed to connect horizontally, vertically, or diagonally. Listing all words in a Boggle board is a common interview question, easily achieved by querying a trie data structure assembled from a list of dictionary words. Use the widget below to see it in action!

# Unboggle

Boggle was easy enough, so let’s try **Unboggle**, or reverse boggle, where the goal is to reconstruct a Boggle board from a given list of words. There is no obvious way to divide-and-conquer the problem and no obvious greedy algorithm guaranteed to use all the words in the list. Instead, I encode Unboggle as a **boolean satisfiability** problem using `logic-solver.js`

, a convenient wrapper around the general-purpose `minisat`

solver, which has been compiled to JavaScript using `emscripten`

.

## The Unboggler

Try it out below! For a 4x4 grid and about 10 words, you can expect the Unboggle search to take about 30 seconds. Since the solver isn’t designed to detect unsatisfiability, the Unboggler may hang for much longer if no satisfying board exists!

## SAT Solvers

SAT solvers search for a satisfying assignment of `true`

and `false`

values to a boolean formula containing literals, conjunction, disjunction, and negation. For example, the formula

is satisfied by the assignment $x_1 = x_2 = \mathtt{true}$ and $x_3 = x_4 = \mathtt{false}$. Integer constraints like $y=11$ can be encoded as binary constraints on the individual binary digits $y = y_4 y_3 y_2 y_1$, like so:

$y_4 \wedge \neg y_3 \wedge y_2 \wedge y_1$Thankfully, `logic-solver.js`

takes care of binary encodings for us and supports basic arithmetic constraints like $(=, <, >, \leq, \geq)$, together with addition and subtraction.

## SAT Encoding

To encode Unboggle as a satisfiability problem, suppose we wish to fit $m$ words on an $n \times n$ board. Assume an average word length $\ell$.

- For each letter of every word on the list, we use two integer variables to represent the letter’s grid coordinates, requiring $L = 2 m \ell \lceil \log_2 n \rceil$ binary literals.
- When the board size is not a power of two, each coordinate needs an upper bound.
- Adjacent letters within the same word must be adjacent on the board.
- A word cannot overlap itself; its coordinate pairs must all be distinct.
- Two different words can only intersect at a common letter; that is, two different letters from distinct words cannot occupy the same space.

The number of constraints increases roughly quadratically with the number of words, so Unboggling more than ten words may take quite a while! The code below uses `logic-solver.js`

to represent these constraints:

```
function encode(numRows, numCols, words){
let solver = new Logic.Solver();
// dimensions
let numWords = words.length;
let numRowBits = Math.ceil(Math.log2(numRows));
let numColBits = Math.ceil(Math.log2(numCols));
// bit constants
let const_1 = Logic.constantBits(1);
let const_numRows = Logic.constantBits(numRows);
let const_numCols = Logic.constantBits(numCols);
// word constraints
let wordPaths = [];
for(let w = 0; w < numWords; w++){
// translate word
let word = words[w];
let wordPath = [];
for(let i = 0; i < word.length; i++){
// location of ith letter stored in variables:
// p_(w)_(i)_r and p_(w)_(i)_c
let pr = Logic.variableBits(`p_${w}_${i}_r`, numRowBits);
let pc = Logic.variableBits(`p_${w}_${i}_c`, numColBits);
wordPath.push([pr,pc]);
// enforce board boundaries on paths (coordinates zero-indexed)
solver.require(Logic.lessThan(pr, const_numRows));
solver.require(Logic.lessThan(pc, const_numCols));
// adjacent letters in word must be adjacent on board
if(i > 0){
// x difference
solver.require(Logic.lessThanOrEqual(wordPath[i-1][0], Logic.sum(wordPath[i][0], const_1)));
solver.require(Logic.lessThanOrEqual(wordPath[i][0], Logic.sum(wordPath[i-1][0], const_1)));
// y difference
solver.require(Logic.lessThanOrEqual(wordPath[i-1][1], Logic.sum(wordPath[i][1], const_1)));
solver.require(Logic.lessThanOrEqual(wordPath[i][1], Logic.sum(wordPath[i-1][1], const_1)));
}
}
// path cannot overlap itself
for(let i = 0; i < word.length; i++){
for(let j = i+1; j < word.length; j++){
solver.require(Logic.atMostOne(
Logic.equalBits(wordPath[i][0],wordPath[j][0]),
Logic.equalBits(wordPath[i][1],wordPath[j][1])
));
}
}
wordPaths.push(wordPath);
}
// now, ensure word paths are all compatible
for(let w1 = 0; w1 < numWords; w1++){
for(let w2 = w1+1; w2 < numWords; w2++){
let word1 = words[w1];
let word2 = words[w2];
for(let i = 0; i < word1.length; i++){
for(let j = 0; j < word2.length; j++){
// no constraint if words have letter in common
if(word1[i] == word2[j]){ continue; }
// prevent different letters from occupying same space
solver.require(Logic.atMostOne(
Logic.equalBits( wordPaths[w1][i][0], wordPaths[w2][j][0] ),
Logic.equalBits( wordPaths[w1][i][1], wordPaths[w2][j][1] )
));
}
}
}
}
// find solution
return {
solution: solver.solve(),
wordPaths: wordPaths
};
}
```