# Printing all strings in a Boggle board

I am trying to print all the strings given in a N x N Boggle board. Its basically a N x N scrabble-like board where words can be made from a position - horizontally, vertically and diagonally.

Here is my naive implementation. Is this correct? Any hints on optimizations? Any other useful links?

public class BoggleSolver {

private void solve(String prefix, int i, int j, char[][] Board, boolean[][] marker, int N)
{
if ((i < 0) || (j < 0) || (i >= N) || (j >= N)) return;

if (marker[i][j] == true) return;

String s = prefix + Character.toString(Board[i][j]);

// TODO Fictional dictionary that can tell us if
// a string is a legal word
if (dict.HasWord(s)) System.out.println(s);

// Mark current index and traverse horizontal,vertical
// and diagonal
marker[i][j] = true;

solve(s, i, j + 1, Board, marker, N);
solve(s, i + 1, j, Board, marker, N);
solve(s, i + 1, j + 1, Board, marker, N);
}

public void solve(char[][] Board, int N)
{
boolean[][] marker = new boolean[N][N];

solve("", 0, 0, Board, marker, N);
}
public static void main(String[] args) {

// TODO make board and call solve(board, N)
}

}

• You have to mark the current position as unused as you return from recursion. – Martin York Dec 28 '13 at 23:36
• You also only go "right" or "down" or "down right". There are actually 8 different directions you can choose from any single tile. – Martin York Dec 28 '13 at 23:38

I wouldn't consider that a Boggle solver, as you only consider words that start at [0, 0] and progress east, south, or southeast. (With coordinates that are always nondecreasing, you need not have bothered using marker to prevent backtracking.)

A complete search will probably take an extremely long time. You should use a dictionary that can check whether there are any words that begin with some prefix, so that you can prune fruitless search paths. Use a trie data structure, or possibly a TreeSet<String>.

Board, N, and HasWord(…) all have improper capitalization. It doesn't make sense to require N to be passed in explicitly, since it should be detectable from the board's dimensions.

Appending a character to a string can be simply written as prefix + board[i][j].

I would recommend redesigning the class with a more versatile interface, because printing the results to System.out limits reusability.

public interface BoggleSolutionHandler {
public void foundWord(String word);
}

public class BoggleSolver {
public static void solve(char[][] board, BoggleSolutionHandler callback, NavigableSet<String> dictionary) {
…
}
}


An iterator would be even nicer to use, but probably harder to implement since you can't take advantage of recursion:

public class BoggleSolver implements Iterator<String> {
public class BoggleSolver(char[][] board, NavigableSet<String> dictionary) {
…
}

@Override
public boolean hasNext() {
…
}

@Override
public String next() {
…
}

@Override
public void remove() {
throw new UnsupportedOperationException();
}
}