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 &lt; 0) || (j &lt; 0) || (i &gt;= N) || (j &gt;= 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)
    }

}
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&lt;String&gt;.

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&lt;String&gt; 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&lt;String&gt; {
    public class BoggleSolver(char[][] board, NavigableSet&lt;String&gt; dictionary) {
        …
    }

    @Override
    public boolean hasNext() {
        …
    }

    @Override
    public String next() {
        …
    }

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