Boggle Word Checker in Java

The challenge

Write a function that determines whether a string is a valid guess in a Boggle board, as per the rules of Boggle. A Boggle board is a 2D array of individual characters, e.g.:

[ ['I','L','A','W'],
  ['B','N','G','E'],
  ['I','U','A','O'],
  ['A','S','R','L'] ]

Valid guesses are strings which can be formed by connecting adjacent cells (horizontally, vertically, or diagonally) without re-using any previously used cells.

For example, in the above board “BINGO”, “LINGO”, and “ILNBIA” would all be valid guesses, while “BUNGIE”, “BINS”, and “SINUS” would not.

Your function should take two arguments (a 2D array and a string) and return true or false depending on whether the string is found in the array as per Boggle rules.

Test cases will provide various array and string sizes (squared arrays up to 150×150 and strings up to 150 uppercase letters). You do not have to check whether the string is a real word or not, only if it’s a valid guess.

The solution in Java code

Option 1:

public class Boggle {
    private final boolean result;
    
    private static boolean check(String guess, char[][] board, int i, int j, int k){
        if (k>=guess.length()) return true;
        if ((i<0)||(j<0)||(i>=board.length)||(j>=board[0].length))return false;
        if (board[i][j]==guess.charAt(k)){
            board[i][j] = 0;
            k++;
            boolean r = check(guess, board, i-1, j-1,k)|
                check(guess, board, i-1, j,k)||
                check(guess, board, i-1, j+1,k)||
                check(guess, board, i, j-1,k)||
                check(guess, board, i, j+1,k)||
                check(guess, board, i+1, j-1,k)||
                check(guess, board, i+1, j,k)||
                check(guess, board, i+1, j+1,k);
            board[i][j] = guess.charAt(--k);
            return r;
        }else
            return false;
    }
    
    static boolean validGuess(String guess, char[][] board){
        for (int i=0; i<board.length;i++)
            for (int j=0; j<board[0].length;j++)
                if (check(guess, board, i, j, 0)) return true;
        return false;
    }
    
    public Boggle(final char[][] board, final String word) {
        result = validGuess(word, board);
    }
    
    public boolean check() {
        return result;
    }
}

Option 2:

public class Boggle {
    char[][] board;
    String word;
    int[][] dir = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,1},{-1,-1},{1,-1}};
    int m, n;
    
    public Boggle(final char[][] board, final String word) {
        this.board = board;
        this.word = word;
        m = board.length;
        n = m == 0 ? 0 : board[0].length;
    }
    
    public boolean check() {
        for (int x = 0; x < m; ++x)
            for (int y = 0; y < n; ++y)
                if (dfs(0, x, y))
                    return true;
        return false;
    }
    
    private boolean dfs(int idx, int x, int y) {
        if (idx == word.length()) return true;
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] == '*') return false;
        if (board[x][y] == word.charAt(idx)) {
            board[x][y] = '*';
            for (int i = 0; i < dir.length; ++i) {
                if (dfs(idx+1, x+dir[i][0], y+dir[i][1])) {
                    board[x][y] = word.charAt(idx);
                    return true;
                }
            }
            board[x][y] = word.charAt(idx);
        }
        return false;
    }
}

Option 3:

import java.util.*;
public class Boggle {
    private char[][] board;
    private final String word;
    
    public Boggle(final char[][] board, final String word) {
        this.board = board;
        this.word = word;
    }
    
    public boolean check() {
      for (int i=0; i<board.length; i++) 
        for (int j=0; j<board[i].length; j++) 
          if (board[i][j]==word.charAt(0))
            if (around(i, j, 1)) 
            return true;
      return false;
    } 
    
    public boolean around(int x, int y, int letter) {
      if (letter==word.length()) return true;
      char c = board[x][y];
      board[x][y]='!';
      for (int i=x-1; i<=x+1; i++) 
        for (int j=y-1; j<=y+1; j++) {
          try {
          if (board[i][j]==word.charAt(letter))
            if (around(i,j,letter+1)) return true;
          }
          catch (IndexOutOfBoundsException e) {
          continue;
          }
        } 
      board[x][y]=c;
      return false;
    }
}

Test cases to validate our solution

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.util.Arrays;


public class SolutionTest {
    
    final private static char[][] board = {
        {'E','A','R','A'},
        {'N','L','E','C'},
        {'I','A','I','S'},
        {'B','Y','O','R'}
    };
    
    private static String[]  toCheck   = {"C", "EAR","EARS","BAILER","RSCAREIOYBAILNEA" ,"CEREAL" ,"ROBES"};
    private static boolean[] expecteds = {true, true, false, true,    true,               false,    false };
    
    @Test
    public void sampleTests() {
        for (int i=0 ; i < toCheck.length ; i++) {
            assertEquals( expecteds[i], new Boggle(deepCopy(board), toCheck[i]).check() );
        }
    }
    
    private char[][] deepCopy(char[][] arr) {
        return Arrays.stream(arr)
                     .map( a -> Arrays.copyOf(a, a.length) )
                     .toArray(char[][]::new);
    }
}