2D Array Deep Copy
by Isai Damier, Android Engineer @ Google

 * Author: Isai Damier
 * Title: BoggleSolver.java
 * Project: geekviewpoint
 * Package: game.programming
 * Description:
 *   Boggle is a word game. A player is given a rectangular board of
 *   letters and is expected to find words by chaining together
 *   adjacent letters. A chain of letters may form a straight line
 *   (horizontal, vertical, or diagonal), or a spiral, or any other
 *   random pattern. Boggle has one rule: the same lettered tile may
 *   not be used more than once.
 *   Now when a real human person plays boggle, the person
 *   implicitly uses the dictionary in his/her head, as it were.
 *   For a program to play boggle, however, it must be given a
 *   dictionary so to know which words are valid.
 *   The best data-structure to hold a dictionary for a boggle
 *   solver is a trie (http://www.geekviewpoint.com/java/trie/add_word).
 *   As a prefix tree, a trie allows the solver to check if a sequence
 *   of letter is a prefix. If a sequence is not a prefix, the solver can
 *   simply stop elongating the sequence and try a different sequence.
 *   Hence the solver will complete the solution much much faster.
 *   Disclaimer: Boggle is a word/board game designed by Allan Turoff
 *   and trademarked by Parker Brothers, a division of Hasbro.
 *   GeekViewpoint is not affiliated with Allan Turoff or Hasbro.
 package game.programming;

import datastructure.Trie;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class BoggleSolver {

   * Description: Given an array, return a deep copy. The copy
   *   returned is independent of the input array: changing a
   *   value in the input array will not affect the copy once
   *   the copy is made. Changing a value in the copy will not
   *   affect the original either.
  private boolean[][] deepCopy(boolean[][] A) {
    boolean[][] B = new boolean[A.length][A[0].length];
    for (int x = 0; x < A.length; x++) {
      for (int y = 0; y < A[0].length; y++) {
        if (A[x][y])//write only when necessary
          B[x][y] = A[x][y];
    return B;
package game.programming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;
import org.junit.After;
import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;

public class BoggleSolverTest {

  List<String> goodWords, badWords, dictionary;
  BoggleSolver boggleSolver = new BoggleSolver();

   * @throws Exception
   * Description: create the dictionaries.
  public void setUp() throws Exception {
    goodWords = Arrays.asList("readied", "reaved", "randie", "navaid",
            "larned", "errand", "envied", "endive", "earned", "darnel",
            "darned", "dandle", "daidle", "adread", "vexed", "veena",
            "varna", "varan", "vaned", "reran", "reave", "raved",
            "ranee", "narre", "naled", "lande", "evade", "erned",
            "eland", "eaved", "eaned", "drear", "dread", "drave",
            "dived", "divan", "denar", "darre", "darer", "arear",
            "aread", "alane", "aland", "adrad", "vied", "vide", "vare",
            "vara", "vane", "vade", "rear", "rean", "read", "rave",
            "rare", "rand", "rana", "rale", "rade", "need", "nave",
            "nare", "nard", "nala", "nada", "lend", "leed", "larn",
            "lare", "lane", "land", "lana", "idle", "idee", "exed",
            "erne", "elan", "eide", "eevn", "eave", "earn", "eard",
            "drad", "dive", "diva", "died", "deva", "deid", "deev",
            "deen", "darn", "dare", "dada", "avid", "arna", "area",
            "arar", "anal", "alee", "alar", "alan", "aide", "vie",
            "vid", "via", "vex", "vee", "var", "van", "vae", "ran",
            "rad", "nee", "ned", "nae", "lex", "lee", "led", "lar",
            "ide", "err", "ern", "era", "end", "eld", "een", "eel",
            "ear", "ean", "div", "die", "did", "dex", "dev", "den",
            "del", "dei", "dee", "dan", "dae", "dad", "ave", "ava",
            "are", "ard", "ane", "and", "ana", "ale", "ala", "aid",
            "ade", "aal");

    badWords = Arrays.
            asList("amazon", "forest", "dangerous", "lovely", "resistible");

    dictionary = new ArrayList<String>();

   * @throws Exception
   * Description: Destroy all resources after use.
  public void tearDown() throws Exception {
    goodWords = badWords = null;
    boggleSolver = null;

   * Test of solver method, of class BoggleSolver.
  public void testSolver() {
    char[][] board = {{'a', 'l', 'e', 'x'},
                      {'a', 'n', 'd', 'e'},
                      {'r', 'a', 'v', 'i'},
                      {'e', 'r', 'd', 'a'}

    Set<String> result = boggleSolver.solver(goodWords, board);
    assertEquals(result.size(), goodWords.size());
    for (String g : goodWords) {
      if (!result.contains(g)) {
        fail("Boggle solver fails to find " + g);
    for (String b : badWords) {
      if (result.contains(b)) {
        fail("Boggle solver should not have found " + b);