Boggle Solver

Attempt 1:

Use Arrays and Lists and a recursive function to loop over all letters in the boggle board and find all possible words of size [min-length] to size [max-length] where min-length >= max-length.

Code:

Apr 16, 2010 2:42:59 PM

  1  package boggle;
  2  
  3  import java.util.ArrayList;
  4  import java.util.Arrays;
  5  import java.util.HashSet;
  6  import java.util.List;
  7  import java.util.Random;
  8  import java.util.Set;
  9  
 10  /**
 11   * Boggle Solver
 12   * @author: Alok Mishra
 13   * @version: 1.0
 14   * Description:
 15   *   Run this with condition that minThreshold >= maxThreshold.
 16   *
 17   * Solution Steps:
 18   *  X,G,S,X,   -> Board        [X,G,S,X,L,I,H,Y,P,J,O,A,F,R,O,C]
 19   *  L,I,H,Y,   -> Marked Board [-1,-1 .......................-1]
 20   *  P,J,O,A,
 21   *  F,R,O,C,
 22   *
 23   * For each letter L in Board
 24   *   intialize marked board
 25   *   wordsList = {}
 26   *   findWords(L, pos-L, Board, MarkedBoard,wordsList)
 27   *
 28   * findWords(L, pos-L, Board, MarkedBoard,curLettersList,wordList)
 29   *  if marked(pos-L) return
 30   *  mark(pos-L)
 31   *  add L to curLettersList
 32   *  add curLettersList to wordList if valid
 33   *  Neighbours[] <- getAllNeighbours(L)
 34   *  for each neighbour N in Neighbours
 35   *     findWords(N, pos-N, Board, MarkedBoard,curLettersList,wordList)
 36   *
 37   * Recursion base conditions:
 38   *  Letter is marked
 39   *  Size of current letters list is reached (16 letter word might be a little too much for this)
 40   *
 41   */
 42  public class BoggleSolverArrayImpl
 43  {
 44    private static final int BOARD_SIDE = 4;
 45    private static final int minTHRESHOLD =
 46      3; //how many letters in a word - min'
 47    private static final int maxTHRESHOLD =
 48      4; //how many letters in a word - max
 49    String[] mBoard = new String[BOARD_SIDE * BOARD_SIDE];
 50  
 51    Random mRandomGen = new Random();
 52  
 53  
 54    public static void main(String[] args)
 55    {
 56      if (minTHRESHOLD > maxTHRESHOLD)
 57        System.exit(1);
 58   
 59      BoggleSolverArrayImpl boggleRunner = new BoggleSolverArrayImpl();
 60      System.out.println("-- BOARD --");
 61      boggleRunner.shake();
 62      boggleRunner.solveForAllLetters();
 63    }
 64  
 65    /**
 66     * Randomize the chars in the board
 67     */
 68    private void shake()
 69    {
 70      for (int i = 0; i < mBoard.length; i++)
 71      {
 72        int pos = getNextInt();
 73        char c = (char) (65 + pos);
 74        mBoard[i] = c + "";
 75        System.out.print(mBoard[i] + ",");
 76        if ((i + 1) % 4 == 0 && i > 0)
 77          System.out.println("");
 78      }
 79    }
 80  
 81  
 82    public void solveForAllLetters()
 83    {
 84      // For all letters in the board find the
 85      // words starting with that letter
 86      for (int i = 0; i < mBoard.length; i++)
 87      {
 88        System.out.println("WORDS Starting with " + mBoard[i]);
 89        solveForOneLetter(i);
 90      }
 91    }
 92  
 93    public void solveForOneLetter(int pPositionOfLetter)
 94    {
 95      int[] marked = new int[mBoard.length];
 96      for (int j = 0; j < marked.length; j++)
 97        marked[j] = 1;
 98      List<String> wordsFound = new ArrayList<String>();
 99      List<String> currentLetters = new ArrayList<String>();
100      findWords(marked, wordsFound, pPositionOfLetter, currentLetters);
101      System.out.println(" Found " + wordsFound.size());
102      print(wordsFound);
103    }
104  
105    /**
106     * @param markedArr
107     * @param wordsFound
108     * @param currentPos
109     * @param currentLetters
110     *
111     * Recursive method to go through the uncharter spaces and build new
112     * VALID words ... VALIDITY is determined by the isValidWord method.
113     * Implement a dictionary there to check the validity of the word
114     * or not ...
115     *
116     */
117    private void findWords(int[] markedArr, List<String> wordsFound,
118                           int currentPos, List<String> currentLetters)
119    {
120      if (markedArr[currentPos] == -1)
121        return;
122      markedArr[currentPos] = -1;
123      currentLetters.add(mBoard[currentPos]);
124      if (currentLetters.size() > maxTHRESHOLD)
125        return;
126      if (isValidWord(currentLetters))
127      {
128        wordsFound.add(getString(currentLetters));
129      }
130  
131      int[] neighbours = getNeighboursNotMarked(currentPos, markedArr);
132      //System.out.println(Arrays.toString(neighbours));
133      for (int i = 0; i < neighbours.length; i++)
134      {
135        if (neighbours[i] != -1)
136        {
137          int[] dupMarked = getDuplicate(markedArr);
138          List<String> clonedCurrentLetters = cloneList(currentLetters);
139          findWords(dupMarked, wordsFound, i, clonedCurrentLetters);
140        }
141      }
142    }
143  
144    /**
145     * @param pCurrentLetters
146     * @return
147     * !TODO
148     * Implement a proper dictionary here - WS call perhaps?
149     */
150    private boolean isValidWord(List<String> pCurrentLetters)
151    {
152      if (pCurrentLetters.size() >= minTHRESHOLD)
153        return true;
154      else
155        return false;
156    }
157  
158  
159    private int[] getNeighboursNotMarked(int pCurrentPos, int[] pMarkedArr)
160    {
161      int[] nonMarkedNeighbours = new int[16];
162      for (int i = 0; i < pMarkedArr.length; i++)
163        nonMarkedNeighbours[i] = -1;
164  
165      int up = pCurrentPos - 4;
166      if (validNeighbour(up, pMarkedArr))
167      {
168        nonMarkedNeighbours[up] = 1;
169      }
170  
171      int dn = pCurrentPos + 4;
172      if (validNeighbour(dn, pMarkedArr))
173      {
174        nonMarkedNeighbours[dn] = 1;
175      }
176      int left = pCurrentPos - 1;
177      if (validNeighbour(left, pMarkedArr))
178      {
179        nonMarkedNeighbours[left] = 1;
180      }
181      int right = pCurrentPos + 1;
182      if (validNeighbour(right, pMarkedArr))
183      {
184        nonMarkedNeighbours[right] = 1;
185      }
186      int upleft = up - 1;
187      if (validNeighbour(upleft, pMarkedArr))
188      {
189        nonMarkedNeighbours[upleft] = 1;
190      }
191      int upright = up + 1;
192      if (validNeighbour(upright, pMarkedArr))
193      {
194        nonMarkedNeighbours[upright] = 1;
195      }
196      int dnleft = dn - 1;
197      if (validNeighbour(dnleft, pMarkedArr))
198      {
199        nonMarkedNeighbours[dnleft] = 1;
200      }
201      int dnright = dn + 1;
202      if (validNeighbour(dnright, pMarkedArr))
203      {
204        nonMarkedNeighbours[dnright] = 1;
205      }
206  
207  
208      //[ 1,  1,  1, -1,
209      //  1, -1,  1, -1,
210      //  1,  1,  1, -1,
211      // -1, -1, -1, -1]
212  
213      return nonMarkedNeighbours;
214    }
215  
216    private boolean validNeighbour(int neighb, int[] pMarkedArr)
217    {
218      if (neighb > -1 && neighb < 16 && pMarkedArr[neighb] != -1)
219        return true;
220      else
221        return false;
222    }
223  
224    private int[] getDuplicate(int[] pMarkedArr)
225    {
226      int[] dup = new int[pMarkedArr.length];
227      for (int i = 0; i < pMarkedArr.length; i++)
228      {
229        dup[i] = pMarkedArr[i];
230      }
231      return dup;
232    }
233  
234    private List<String> cloneList(List<String> pCurrentLetters)
235    {
236      List<String> ret = new ArrayList<String>();
237      for (String s: pCurrentLetters)
238        ret.add(s);
239      return ret;
240    }
241  
242  
243    private void print(List<String> pWordsFound)
244    {
245      int i = 0;
246      for (String s: pWordsFound)
247      {
248        System.out.print(s + ",");
249        i++;
250        if (i % 15 == 0 && i > 0)
251          System.out.println("");
252      }
253      System.out.println("");
254    }
255  
256  
257    private int getNextInt()
258    {
259      while (true)
260      {
261        int num = mRandomGen.nextInt(26);
262        if (num > -1 && num <= 26)
263          return num;
264  
265      }
266    }
267  
268    private String getString(List<String> pCurrentLetters)
269    {
270      StringBuffer sb = new StringBuffer();
271      for (String s: pCurrentLetters)
272        sb.append(s);
273      return sb.toString();
274    }
275  }