Question

4. Word Find A popular diversion in the United States, “word find” (or “word search”) puzzles ask the player to find each of a given set of words in a square table filled with single letters. A word can read horizontally (left or right), vertically (up or down), or along a 45 degree diagonal (in any of the four directions) formed by consecutively adjacent cells of the table; it may wrap around the table’s boundaries, but it must read in the same direction with no zigzagging. The same cell of the table may be used in different words, but, in a given word, the same cell may be used no more than once. Write a computer program for solving this puzzle.

Answer 1

I have coded in java. Please compile "WordSearch.java" first. Then, compile and run "SolveWordSearch.java". The "words.txt" file should contain the data as given below. The first 2 lines of the "words.txt" file indicates the number of rows and columns of the puzzle(10x10). The next 10 lines is the puzzle. The next line indicates the number of words to be found and the last 4 lines indicates the words to be found on the given puzzle.

WordSearch.java

import java.util.Scanner;
import java.io.*;
public class WordSearch
{
   private int rows;//instance variable
   private int cols;//instance variable
   private int words;//instance variable
   private char[][] wordSearchchar;//instance variable
   private String[] wordSearchstring;//instance variable  
  
   public WordSearch()//an initialized constructor
   {
   }

   public int addX(int x, int ax)//rows
   {
       x = x + ax;
       if(x < 0)
       {
           x = rows - 1;
       }
       if(x >= rows)
       {
           x = 0;
       }
       return x;
   }

   public int addY(int y, int ay)//columns
   {
       y = y + ay;
       if(y < 0)
       {
           y = cols - 1;
       }
       if(y >= cols)
       {
           y = 0;
       }
       return y;
   }

   public boolean testdirect(int x, int y, int d,String word, int ax, int ay)//checking the directions
   {
       if(d == word.length())
       {
           return true;
       }
       if(wordSearchchar[x][y] == word.charAt(d))
       {
           return testdirect(addX(x, ax), addY(y, ay), d+1, word, ax, ay);
       }
       return false;
   }

   public void wordFind()//gets the matrix of words and checks if the words are there in the scrambled words
   {
       System.out.println();
       System.out.println("The Words Are Found At [Row Column] Respectively:");
       System.out.println();
       for(int d = 0; d < words; d++)
       {
           String word = wordSearchstring[d];
           boolean foundWord = false;
           for(int i = 0; i < rows; i++)
           {
               if(foundWord == true)
               {
                   break;
               }
               for(int j = 0; j < cols; j++)
               {
                   if(wordSearchchar[i][j] == word.charAt(0))
                   {
                       if(testdirect(i, j, 0, word, 1, 0) == true)
                       {
                           System.out.println(i + " " + j);
                           foundWord = true;
                       }
                       else if(testdirect(i, j, 0, word, -1, 0) == true)
                       {
                           System.out.println(i + " " + j);
                           foundWord = true;
                       }
                       else if(testdirect(i, j, 0, word, 0, 1) == true)
                       {
                           System.out.println(i + " " + j);
                           foundWord = true;
                       }
                       else if(testdirect(i, j, 0, word, 0, -1) == true)
                       {
                           System.out.println(i + " " + j);
                           foundWord = true;
                       }
                       else if(testdirect(i, j, 0, word, 1, 1) == true)
                       {
                           System.out.println(i + " " + j);
                           foundWord = true;
                       }
                       else if(testdirect(i, j, 0, word, -1, -1) == true)
                       {
                           System.out.println(i + " " + j);
                           foundWord = true;
                       }
                       else if(testdirect(i, j, 0, word, -1, 1) == true)
                       {
                           System.out.println(i + " " + j);
                           foundWord = true;
                       }
                       else if(testdirect(i, j, 0, word, 1, -1) == true)
                       {
                           System.out.println(i + " " + j);
                           foundWord = true;
                       }
                   }
               }
           }
           if(foundWord == false)
           {
               System.out.println("NOT FOUND");
           }
       }
   }

   public void readWordSearch()//reads in the WordSearch file
   {
       String inputLine;
       Scanner fileInput;
       File inFile = new File("words.txt");
       try
       {
           fileInput = new Scanner(inFile);
           //Pulls the data from the top to make the maze
           //Sets the start and end row for a win
           rows = fileInput.nextInt();
           cols = fileInput.nextInt();
           wordSearchchar = new char[rows][cols];
           fileInput.nextLine();
           for(int i = 0; i < rows; i++)
           {
               inputLine = fileInput.nextLine();
               for(int j = 0; j < cols; j++)
               {
                   wordSearchchar[i][j] = inputLine.charAt(j);
               }
           }
           words = fileInput.nextInt();
           wordSearchstring = new String[words];
           fileInput.nextLine();
           for(int i = 0; i < words; i++)
           {
               wordSearchstring[i] = fileInput.nextLine();
           }
           fileInput.close();
       }
       catch (FileNotFoundException e)
       {
           System.out.println(e);
           System.exit(1);//an IO error and exits the program
       }
   }
   public void printWordSearch()//displays the solved array of words
   {
       System.out.println();
       System.out.println("THE WORD PUZZLE");
       System.out.println("~~~~~~~~~~~~~~~");
       for(int i = 0; i < rows; i++)
       {
           for (int j = 0; j < cols; j++)
           {
               System.out.print(wordSearchchar[i][j]);
           }
           System.out.println();
       }
       System.out.println();
       System.out.println("The Words To Be Searched Are:");
       System.out.println();
       for(int i = 0;i < words; i++)
       {
           System.out.print(wordSearchstring[i]);
           System.out.println();
       }
   }
}

SolveWordSearch.java

import java.lang.Math;
import java.util.Scanner;
import java.io.*;
public class SolveWordSearch
{
   public static void main(String [] args)
   {
       WordSearch WordSearching = new WordSearch();//object creation
       WordSearching.readWordSearch();//WordSearching object reads the word search
       WordSearching.printWordSearch();//WordSearching object prints the word search
       WordSearching.wordFind();//WordSearching object finds the word search
   }
}

words.txt

10
10
ECOMPUTERO
CEDCEVLEVR
MKUJONRPBH
HERPQYOLHF
RVTLCQTHNC
WCWECGIBCG
JHMOSMNNJG
POIUUTOERT
ZXCVBNMNMI
EDRFTGYHUJ
4
COMPUTER
CPU
MONITOR
TEST

Output: