OVERVIEW Purpose: We have discussed recursion and in particular backtracking alg
ID: 3731308 • Letter: O
Question
OVERVIEW Purpose: We have discussed recursion and in particular backtracking algorithms (such as Eight Queens). In this assignment you will get some practice at recursive programming by writing a backtracking algorithm to find phrases in a puzzle. Idea: "Word search" puzzles are common in newspapers, on restaurant placemats and even in their own collections within books. These follows: A user is presented with a 2-dimensional grid of letters and a list of words. The user must find all of the words from the list within the grid, indicating where they are by drawing ovals around them. Words may be formed in any direction up, down, left or right (we will not allow diagonals even though most puzzles do allow them) but all of the letters in a word must be in a straight line vary in format from puzzle to puzzle, but one common format is as This idea can be extended to allow phrases to be embedded in the grids. However, requiring an entire phrase to be in a straight line on the board is not practical, as the dimensions of the board would need to be overly large. Therefore, we will still require the letters in each word to be in a straight line, but we are allowed to change direction between words. For example, we might be given the following 10x10 grid of letters a b s t ract ij a t a d tdat a j tbcdcagh tj pbcd r a gh p j s are sfoh s j ared bfoha j e rea ll yre j and the following phrasesExplanation / Answer
import java.util.ArrayList;
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.FileReader;
public class Solution {
public static void main(String[] args) {
BufferedReader br = null;
FileReader fr = null;
ArrayList<String> arr=null;
try {
fr = new FileReader("grid.txt");
br = new BufferedReader(fr);
arr=new ArrayList<String>();
String sCurrentLine;
while ((sCurrentLine = br.readLine()) != null) {
String temp="";
String[] str=sCurrentLine.split(" ");
for(String s:str)
{
temp+=s.charAt(0);
}
arr.add(temp);
}
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
if (br != null)
br.close();
if (fr != null)
fr.close();
} catch (Exception ex) {
ex.printStackTrace();
}
}
Scanner sc=new Scanner(System.in);
System.out.println("Enter the phrase to search for");
String phrase=sc.nextLine();
int result=exist(arr,phrase);
if(result==1)
System.out.println("Phrase Exists");
else
System.out.println("Phrase does not Exists");
}
public static int exist(ArrayList<String> a, String b) {
int row=a.size();
int col=a.get(0).length();
char[][] arr=new char[row][col];
for(int i=0;i<row;i++)
{
String dummy=a.get(i);
for(int j=0;j<col;j++)
{
arr[i][j]=dummy.charAt(j);
}
}
char c=b.charAt(0);
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(util(arr,0,b,row,col,i,j))
return 1;
}
}
return 0;
}
public static boolean util(char[][] arr,int index,String b,int row,int col,int i,int j)
{
if(i>-1 && j>-1 && i<row && j<col)
{
if(index>=b.length())
return true;
else
{
if(arr[i][j]==b.charAt(index))
{
return (util(arr,index+1,b,row,col,i,j+1) || util(arr,index+1,b,row,col,i,j-1) || util(arr,index+1,b,row,col,i-1,j) || util(arr,index+1,b,row,col,i+1,j) );
}
else
return false;
}
}
else
return false;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.