4
\$\begingroup\$

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)
    }

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

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();
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.