Solution.java

import java.util.*;

public class Solution {
	private static String[][] board = 
		{{ "A",  "T",  "E",  "E" },
		{ "A",  "P",  "Y",  "O" },
		{ "T",  "I",  "N",  "U" },
		{ "E",  "D",  "S",  "E" }};
	private static boolean[][] visited = 
			{{false,false,false,false},
			{false,false,false,false},
			{false,false,false,false},
			{false,false,false,false}};
	private static List<String> result = new ArrayList<String>();
	private static List<String> dictionary = new ArrayList<String>();
	public static void main(String[] args) {
		dictionary.add("EYE");
		dictionary.add("SUN");
		dictionary.add("TINY");
		dictionary.add("SEND");
		dictionary.add("PIN");
		dictionary.add("ATE");
		dictionary.add("TINS");
		dictionary.add("TIN");
		dictionary.add("TIDE");
		
		//invalid words
		dictionary.add("ATET");//FOR LACK OF BETTER ONE THAN SUNS UPON QUICK LOOK
		dictionary.add("SUNS");
		
		for ( int i = 0; i < board.length; i++ ){
			for ( int j = 0; j < board[0].length; j++){
				visited = new boolean[board.length][board.length];
				wordSearch(i, j, "");
			}
		}
		System.out.println(result);
	}
	private static void wordSearch(int i, int j, String soFar) {
		
		//removed return logic for edge case return because it needs
		//to be handled dynamically to ensure each cell is hit
		if (visited[i][j]){
			return;
		}
		soFar += board[i][j];
		
		//logic to return if the recursion path no longer matches
		//up with the beginning of any words in the dictionary
		if(!stillValid(soFar)){
			return;
		}
		visited[i][j]=true;
		
		//add to result set if in dictionary and has not been found
		//(satisfies the no duplicate print requirement)
		if (dictionary.contains(soFar) && !result.contains(soFar)){
			result.add(soFar);
		}
		
		//added the logic to select where the recursion proceeds
		//making sure to deal with edge cases this had to be moved
		//because the implementation from yesterday would not have
		//allowed the algorithm to hit all possible branches
		if ( i > 0){
			wordSearch( i-1,j,soFar );
			if ( j > 0 ){
				wordSearch( i-1, j-1, soFar );
			}
			if ( j < board[0].length-1 ){
				wordSearch(i-1,j+1,soFar);
			}
		}
		if ( j > 0 ){
			wordSearch( i, j-1, soFar );
		}
		if ( i < board.length - 1 ){
			if ( j > 0 ){
				wordSearch( i+1, j-1, soFar );
			}
			if ( j < board[0].length-1 ){
				wordSearch(i+1,j,soFar);
			}
			wordSearch(i+1,j,soFar);
		}
		if ( j < board[0].length-1 ){
			wordSearch(i,j+1,soFar);
		}
		//Set to false because there could still be a another
		//case to recurse upon at this cell if we have reached
		//this point then return
		visited[i][j]=false;
		return;
	}
	
	//helper method to return if the word that has been compiled
	//during recursion is still part of the dictionary
	public static boolean stillValid(String soFar){
		for(String x : dictionary){
			if(x.length()>=soFar.length()){
				if(soFar.equals(x.substring(0, soFar.length()))){
					return true;
				}
			}
		}
		return false;
	}
}