Title: WordSearch - Problem Solving
Course: CPS 161: An Intro to Programming with Java - DL MM MASTER

WordSearch - Problem Solving

In this video, we discuss coming up with a program to solve the famous Word Search puzzle you find on the back of cereal boxes.

We could have done this after covering our Arrays chapter, but I held this back and included in my "Extras Week"

The solution from the video is shown below:

WordSearch.java


enum DIRECTION {UP, DOWN, LEFT, RIGHT, DIAG_UP_RIGHT, DIAG_UP_LEFT,
    DIAG_DOWN_RIGHT, DIAG_DOWN_LEFT};

    class Coord
    {
        int row,  col;
        Coord(int r, int c)
        {
            row=r;
            col=c;
        }

    }

    public class WordSearch {
        char[][] wordsSearch;
        boolean[][]foundArray;
        Coord[] saveCoords;
        String[] words;
        int rows, cols;
        DIRECTION[] directions = DIRECTION.values();

        WordSearch(String[]wsearch, String[]words)
        {
            this.words = words;
            rows = wsearch.length;
            if (rows <= 0)
                throw new RuntimeException("Empty wordsSearch Array");
            cols = wsearch[0].length();
            wordsSearch = new char[rows][cols];
            foundArray = new boolean[rows][cols];

            for (int r=0; r < rows; r++)
            {
                if (wsearch[r].length() != cols)
                    throw new RuntimeException("Uneven columns at row: "+ r);
                for (int c=0; c < cols; c++)
                {
                    wordsSearch[r][c] = wsearch[r].charAt(c);
                    foundArray[r][c] = false;
                }
            }
            saveCoords = new Coord[Math.max(rows, cols)];
        }
        void solve()
        {
            for (int w = 0; w < words.length; w++)
            {
                if (find(words[w]))
                {
                    System.out.println("Found word: " + words[w]);
                    display();
                }
                else
                    System.out.println("Couldn't find word: "+words[w]);
            }
        }
        boolean find(String word)
        {
            for (int r=0; r < rows; r++)
            {
                for (int c=0; c < cols; c++)
                {
                    for (int d=0; d < directions.length; d++)
                    {
                        if (find(word, r, c, directions[d]))
                        {
                            for (int i=0; i < word.length(); i++)
                            {
                                foundArray[saveCoords[i].row][saveCoords[i].col]=true;
                            }
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        boolean find(String word, int r, int c, DIRECTION d)
        {
            for (int i=0; i < word.length(); i++)
            {
                if (wordsSearch[r][c] != word.charAt(i))
                    return false;
                saveCoords[i] = new Coord(r,c);
                if (i == word.length()-1) // last letter ... don't need to move to the next
                    break;
                switch(d)
                {
                case UP:
                    r -=1;
                    break;
                case DOWN:
                    r+=1;
                    break;
                case LEFT:
                    c -=1;
                    break;
                case RIGHT:
                    c +=1;
                    break;
                case DIAG_UP_RIGHT:
                    r -= 1;
                    c += 1;
                    break;
                case DIAG_UP_LEFT:
                    r -= 1;
                    c -= 1;
                    break;
                case DIAG_DOWN_RIGHT:
                    r += 1;
                    c += 1;
                    break;
                case DIAG_DOWN_LEFT:
                    r += 1;
                    c -= 1;
                    break;
                }
                if (r < 0 || c < 0 || r >= rows || c >= cols)
                    return false;
            }
            return true;
        }
        void display()
        {
            for (int c=0; c < cols; c++)
                System.out.print("**");
            System.out.println();
            for (int r = 0; r < rows; r++)
            {
                for (int c=0; c < cols; c++)
                {
                    if (foundArray[r][c])
                        System.out.print(wordsSearch[r][c]+" ");
                    else
                        System.out.print("  ");

                }
                System.out.println();
            }
            for (int c=0; c < cols; c++)
                System.out.print("--");
            System.out.println();
        }

        public static void main(String[] args) {
            String[] wordSearchArr={
                    "HMNZNRXADKLWEVG",
                    "PEOSRXLHZNMRFFX",
                    "IJMMCQNNRRKUHNJ",
                    "UXAUOOOFYQKZABJ",
                    "HHNUPIOEEESRRUX",
                    "AKNGCKPPVVBEDUP",
                    "KLIMXVSKXKAQEGD",
                    "CMCBHHYQNKNPLQT",
                    "SXIGCLBQFUIKIGJ",
                    "TWBNXOCAZQSZCNU",
                    "PZUVWESUVUIMIIO",
                    "YRALRTYOBTAXONQ",
                    "CWREZWUQTMRYURM",
                    "LNAWAALMONDSSOF",
                    "XLQLOCNQHOJPKMF",
                    "HHNUPIOEEESRRUX"
            };
            String[] wordsList ={"MILK", "BRAN", "CEREAL", "SPOON",
                    "BOWL", "RAISIN", "BREAKFAST",
                    "MORNING","DELICIOUS","SCOOP",
                    "ALMONDS","CINNAMON", "CRUNCH",
            "SUN"};

            WordSearch ws = new WordSearch(wordSearchArr, wordsList);
            ws.solve();
            ws.display();

        }

    }



Last Updated: November 18, 2013 12:51 PM