The New York Times includes a daily puzzle called "Letter Boxed." It involves a set of 12 letters arranged around the sides of a square, such as the following: N OM K To solve the puzzle, you need to come up with a sequence of English words in which each letter in the puzzle appears at least once. In addition, the words in the sequence must observe the following constraints: Each word must be at least 3 letters long. Adjacent letters must come from different sides of the square. For example, when solving the puzzle above, if the first letter in a word is T, the second letter in that word cannot be either A or E, since A and E are on the same side of the square as T. One word that can be formed from the puzzle above is TIME. I is on a different side of the square than T, M is on a different side than I, and E is on a different side than M. The last letter of one word of the sequence must match the first letter in the next word in the sequence. For example, if we use TIME as the first word in our solution, the second word must then begin with E, since TIME ends with E. For a given puzzle, there are many possible solutions, but solutions that use fewer words are preferred. For the puzzle above, one possible solution is LIMES STONES SHAKY However, an even better solution is MILESTONES SHAKY because it uses fewer words. In this problem, you will write a program that solves this type of puzzle using recursive backtracking! We have provided: a class called LetterSquare that will serve as a blueprint for objects that represent a Letter Square puzzle, and that can be used to solve the puzzle. We have included some starter code, and you will implement two key methods of the class. a separate class called Dictionary that serves as a blueprint for a Dictionary object that you can use to check if a string is a word or the prefix of a word in a collection of common English words. You should not modify this class in any way. a text file called word_list.txt containing the words in the dictionary. Begin by reading over the code that we have given you in Lettersquare.java. The provided code includes: a constant called dictionary that refers to the Dictionary object described above. The two key methods in this object are: o dictionary.hasString(s), which returns true if the string s is either a word or the prefix of a word in the dictionary of words, and false otherwise. For example, because "game" is a word in the dictionary, all of the following calls will return true: dictionary.hasString("g") dictionary.hasString("ga") dictionary.hasString("gam") dictionary.hasstring("game") However, dictionary.hasstring("gome") will return false, because the string "gome" is neither a word nor the prefix of a word in the dictionary. o dictionary.hasFullword(s), which returns true if the string s is a "full word" (i.e., a word that can stand on its own, and is not only a prefix) in the dictionary of words, and false otherwise. For example: dictionary.hasFullword("game") will return true, because "game" is a full word in the dictionary. dictionary.hasFullword("g"), dictionary.hasFullword("ga"), and dictionary.has Fullword("gam") will all return false, because these strings are not full words in the dictionary. a field called sides that refers to an array of strings. It is used to store the letters on each side of the puzzle, with each side represented by a three-letter string. For example, the sides of the puzzle above would be stored as the following array: {"tae", "nih", "omk", "lys"} (Either lower-case or upper-case characters can be used.) a field called letters that refers to an array of single-letter strings. This array is used to store the individual letters in the puzzle. For example, the letters in the puzzle above would be stored as the following array: {"t", "a", "e", "n", "i", "h", "o", "m", "k", "1" "y", "s"} a field called words that refers to an array of strings. It will be used to store the words in the solution to the puzzle. When the LetterSquare object is created, this array is initially filled with empty strings. a constructor that takes an array representing the sides of the puzzle and initializes the fields. a tostring method that returns a string representation of the puzzle that will be used when you print a LetterSquare object. private static helper methods that make it easier to perform two types of operations on string objects: o one called lastLetter (word) that can be used to obtain a single-letter string consisting of the last letter in the string word; for example, lastLetter("world") would return the string "d". o one called remove Last (word) that takes a string word and returns the new string formed by removing the last letter in word; for example, removeLast("world") would return the string "worl". a private method called addLetter that takes a single-character string letter and an integer wordNum, and that adds the specified letter to the end of the word in position wordNum of the words array. a private method called remove Letter that takes an integer wordNum and that removes the last letter from the word in position wordNum in the words array. a private method called alreadyUsed that takes an arbitrary string word and that returns the boolean value true if word is already one of the words in the solution, and false otherwise. a private method called onsameside that takes two single-character strings letter1 and letter2, and that returns true if letter1 and letter2 are on the same side of the puzzle, and false otherwise. a private method called all Lettersused that returns the boolean value true if all of the letters in the puzzle have been used somewhere in the solution, and false otherwise. a private method called printsolution that takes an integer wordNum and prints the words in positions 0 through wordNum of the words array. the skeleton of a private method called solveRB that you will implement. This is the recursive-backtracking method, and it should return true if a solution to the puzzle has been found and false if no solution has been found (i.e., if the method is backtracking). the skeleton of a private method called isvalid that you will also implement. This method should be called by solveRB to check if a given letter would work as the next letter in the current word. a public method named solve that clients can call to solve a LetterSquare puzzle. It repeatedly calls solveRB with increasing values of maxwords until it finds a solution to the puzzle, or until it has tried and failed to find solutions of up to 10 words. a main method that allows the user to enter and solve a puzzle. The only methods that you should change are solveRB and isvalid. All of the other provided methods should be left unchanged. You are welcome to add your own additional helper methods, although doing so is not required. Task 2: implement isvalid Once you have reviewed the provided code, you can begin to implement the bodies of the two methods that you are required to write. You should not change the headers that we have provided. You should start by implementing the isvalid helper method that will be used to check if a given letter would work as the next letter in the current word, given the words and prefixes in the dictionary and the constraints of the puzzle described at the beginning of the problem. This method must take three parameters: letter: a single-character string representing the letter whose validity is being tested wordNum: an integer specifying the index of the position in the words array of the word that is currently being built charNum: an integer specifying the index of the position within the current word that letter is being considered for. It should return true if the specified letter is a valid choice for the letter in position charNum of the word in position wordNum of the words array, and false otherwise. You may assume that only appropriate values will be passed in. In particular, you may assume that letter is one of the letters of the puzzle. The constraints that you need to check will depend on the value of the charNum parameter (and possibly also of the wordNum parameter). For example, let's assume that we have the following situation: We are solving the puzzle shown at the start of the problem (the one with sides {"tae", "nih", "omk", "lys"}). We are looking for a solution of at most 2 words. The current partial solution is {"time", ...}. We are within the call this. solveRB(0, 4, 2) - i.e., we are attempting to expand the word in position 0 ("time") by finding a letter that would work in position 4 of that word. Given this situation: this.isvalid("1", 0, 4) should return true because "1" is on a different side of the puzzle than "e" (the letter that was added to give "time") and "timel" is a word and/or a prefix of a word in the dictionary (which we know because dictionary.hasString("timel") returns true) this.isvalid("s", 0, 4) should also return true because "s" is on different side of the puzzle than "e" and dictionary.hasString("times") returns true this.isvalid("a", 0, 4) should return false because "a" is on the same side of the puzzle as "e" this.isvalid("y", 0, 4) should return false because "timey" is neither a word nor a prefix of a word in the dictionary (which we know because dictionary.hasstring("timey") returns false). Now imagine that we have added the letter "s" to the partial solution described above to give a new partial solution {"times", ... } and that we are now focused on the first letter in second word in the solution (i.e., that we are within the call this. solveRB (1, 0, 2)). Given this situation: this.isvalid("s", 1, 0) should return true because we are focused on the first letter in a new word and "s" is the last letter of the previous word ("times") this.isvalid("1", 1, 0) should return false because we are focused on the first letter in a new word and "1" is not the last letter of the previous word. Other notes: You should take advantage of one or more of the methods in the Dictionary object given by the class constant dictionary. You will need a special case for handling the first character of the first word in the solution. In that case, any letter of the puzzle is valid! When is considering a case in which the current word is being expanded by one letter, the method should return false if adding the letter would produce a word that is already part of the solution. Otherwise, you could end up producing a solution that repeatedly uses the same word (e.g., {"toast", "toast", . }). Note that we have given you a helper method that makes it easy to check for this case! isvalid should only determine if the specified letter is a valid choice for the next letter. It should not actually add the letter to the solution. Task 3: implement solveRB The recursive-backtracking method (solveRB) must take three integer parameters: wordNum: the index of the position in the words array of the word that is currently being built charNum: the index of the character within the current word that this call is responsible for adding maxwords: the maximum number of words that the solution is allowed to have. It should follow the same basic approach as the recursive-backtracking template from lecture (the one designed to find a single solution). However, there will be a couple of key differences: In addition to a base case that checks if the puzzle has been solved, you will need a second base case for calls in which wordNum is too big, given the value of maxwords. For example, the call this.solveRB (3, 0, 3) should return false, because if maxwords is 3, we shouldn't be looking for a fourth word (which is what a first input of 3 indicates). If the current call is able to add a letter to the solution, you may need to make two separate recursive calls: o First, you should make a call that attempts to expand the current word in the solution, making it one letter longer. o Then, if the first recursive call does not succeed in finding a solution and if the current word in the solution is a full word of at least three letters, you should make a second recursive call that moves on to the next word in the solution. For example, let's say that the call this. solverB (0, 3, 2) adds the letter e to position 3 of the first word in the solution, giving us the string "time" as that first word. o First, we would make the call this. solveRB (0, 4, 2) to see if we can expand "time" into a longer word. o Then, if the first call returns false, we would check if "time" is a full word of at least 3 letters. Because it is, we would make the call this.solveRB (1, 0, 2) to move onto the second word in the solution (the one in position 1 of the words array). Note that we also use a 0 for the second input of this call, since the call will be focused on the first letter in that new word. Note that you should only make a second recursive call if the first call returns false and the current word is a full word of at least three letters. Other notes: Make sure that you use the addLetter () and remove Letter () methods when updating the state of the puzzle. In addition, take advantage of the other helper methods that we have provided - including the methods in the Dictionary object given by the class constant dictionary. File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J Dictionary.java X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J Dictionary.java > ... 13 import java.util.*; 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ge 2 4 20 Restricted Mode public class Dictionary { // key = a prefix or full word // value = false if the key is a prefix // true if the key is a full word private HashMap contents; * constructor for a Dictionary object that can be used to test if a * string is either a word or a prefix of a word in a collection of words public Dictionary() { this.contents = new HashMap (); } /* * constructor for a Dictionary object that is built using from a text file * with the specified file name. In the text file, the words should appear * one word per line. public Dictionary (String fileName) { this(); try { Dictionary.java - Visual Studio Code Learn More Scanner f = new Scanner(new File(fileName)); while (f.hasNextLine()) { String word = f.nextLine(); this.add(word); Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O BERA T RAPOHAP 8 : [PTIRI FYRIR L'ANIMA {Java Q File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J Dictionary.java X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J Dictionary.java > ... 40 Chis.add(word); 41 } 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 Restricted Mode 2 490 } f.close(); } catch (FileNotFoundException e) { throw new IllegalStateException("could not process file of words"); /* * add - adds the specified word and all of its prefixes to the Dictionary */ private void add(String word) { String prefix = ""; for (int i = 0; i < word.length(); i++) { prefix += word.charAt(i); if (! this.contents.contains Key (prefix)) { this.contents.put(prefix, false); * } Dictionary.java - Visual Studio Code Learn More } // true indicates a full word this.contents.put(prefix, true); hasString - returns true if the specified string s is either a word * or a prefix of a word in the Dictionary, and false otherwise 0A0 Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O BERA ANTHUR VEGA 8 : [PTID: PILTE LUMINE {Java Q File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J Dictionary.java X C: > Users > ben > OneDrive > Desktop > part2 > problem7 J Dictionary.java > ... 64 65 66 67 68 69 70 71 2 4 20 273747576 7 78 79 88 77 80 81 82 83 84 85 86 87 88 89 90 91 Restricted Mode } */ public boolean hasString(String s) { if (s == null || s.equals("")) { return false; } * hasString - returns true if the specified string s is either a word or a prefix of a word in the Dictionary, and false otherwise } } else { return this. contents. contains Key (s.toLowerCase()); * has FullWord - returns true if the specified string s is a "full word" * and false otherwise */ public boolean hasFullWord (String s) { if (s == null || s.equals("")) { return false; Dictionary.java - Visual Studio Code * (i.e., a word that can stand on its own) in the Dictionary, } else { } Learn More A 0 s = s.toLowerCase(); return (this.contents.containsKey(s) && this.contents.get(s)); Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O BERA ANTHUR VEGA 8 : [PTID: PILTE LUMINE {Java Q File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... 9 o ge 2 4 20 PENANGGAGGANG 27 NM & M 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 Restricted Mode import java.util.*; public class LetterSquare { public static final int MOST_WORDS = 10; public static final String WORDS_FILE = "word_list.txt"; public static final Dictionary dictionary = new Dictionary (WORDS_FILE); LetterSquare.java - Visual Studio Code // The sides of the puzzle, given as four strings of length 3. private String[] sides; // The words in the solution. private String[] words; Learn More // The individual letters in the puzzle. // Each element of this array is a single-character string. private String[] letters; public LetterSquare (String[] sides) { if (sides == null || sides.length != 4) { throw new IllegalArgumentException ( * Constructor for a puzzle with the specified sides, where each * side is a string containing the 3 letters from one side of the square. */ 0 A 1 "parameter must be an array of 4 strings"); Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O POURTEETA www. LEZ. "FONEN wwwww com STEZ {Java Xx: 8 ANCONA *** Q File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... 37 this.sides = sides; 38 this.letters = new String[12]; 39 int letterNum = 0; 40 for (int i = 0; i < sides.length; i++) { 41 if (sides[i] == null || sides[i].length() != 3) { 42 throw new IllegalArgumentException ( 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Restricted Mode O 2 4 28 } } } O 0 A 1 } this.words = new String [MOST_WORDS]; for (int i = 0; i < this.words.length; i++) { this.words[i] = ""; LetterSquare.java - Visual Studio Code "invalid side string: " + sides[i]); for (int j = 0; j < 3; j++) { this.letters [letterNum] this.sides[i].substring(j, j+1); letterNum++; f Learn More * Returns a string that shows the letters of the puzzle in "square" form. * For example, if the sides are {"cat", "dog", "fry", "pie"}, it will * return a string that when printed looks like this: * cat * d Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O POURTEETA *NODA.CO V www. Pom EMIX. "FONEN wwwww {Java STEZ 8 : ANCONA aras, v *** Q File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... 64 * O 65 66 67 68 69 70 71 2 4 20 2737475 76 7 8 79 88 81 82 83 77 78 80 84 85 86 87 88 89 90 91 Restricted Mode * * pie public String toString() { String s = ; r y // top of the square (i.e., sides[0]) for (int i = 0; i < 3; i++) { S += " u } s += " "; } // left and right sides (sides[1] and sides [2]) for (int i = 0; i < 3; i++) { + this.sides[0].charAt(i); s += this.sides [1].charAt(i); S += " s += " "; } 0 A 1 // bottom of the square (i.e., sides[3]) for (int i = 0; i < 3; i++) { s += " "; return s; " + this.sides [2].charAt(i); s += " " + this.sides [3].charAt(i); LetterSquare.java - Visual Studio Code Learn More Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O *NODA.CO V ELEMET. "FONSIL RACON wwwww {Java STEZ 8 : aras, po *** Q File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 o ge 11 117 118 119 Restricted Mode * /* * lastLetter - returns a single-character string containing * the last letter in the specified word * */ private static String lastLetter (String word) { return word.substring(word.length() - 1); * * LetterSquare.java - Visual Studio Code assumes that word is a String with at least one character /* * removeLast - returns the string that is formed by removing * the last character of the specified word Learn More */ private static String removeLast(String word) { return word.substring(0, word.length() - 1); assumes that word is a String with at least one character /* * addLetter - adds the specified letter as the next letter * in the word at position wordNum in the solution * and also updates the solnString accordingly */ private void addLetter(String letter, int wordNum) { this.words [wordNum] += letter; 0 A 1 Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O *NODA.CO www. ELEMER. "FOLL wwwww comm RANDOM STEZ {Java 8 : arvas, va *** Q File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... PEU in the word at position woranum in the solucion 116 * and also updates the solnString accordingly 117 ge 118 119 120 121 122 123 124 125 126 127 private void addLetter(String letter, int wordNum) { this.words [wordNum] += letter; } private void remove Letter (int wordNum) { this.words [wordNum] /* * removeLetter - removes the specified letter from the end of * the word at position wordNum in the solution * and also updates the solnString accordingly */ 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 } 143 Restricted Mode 0 A 1 } = LetterSquare.java - Visual Studio Code */ private boolean alreadyUsed(String word) { for (String w: this.words) { } /* * alreadyUsed - returns true if the specified word is already * one of the words in the solution, and false otherwise. if (w.equals (word)) { return true; } return false; Learn More this.removeLast(this.words [wordNum]); Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O www. www.m ELEME "FONT wwwww 8 : ANCONA STEZ {Java VALMVW aras, po *** Q File Edit Selection View Go Run Terminal Help LetterSquare.java - Visual Studio Code Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage Learn More J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... 143 144 145 146 147 148 149 150 151 152 153 2 490 ge 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 /* * onSameSide - returns true if the single-character strings * letter1 and letter2 come from the same side of the puzzle, * and false otherwise */ private boolean onSameSide (String letter1, String letter2) { for (String side : this.sides) { if (side.contains (letter1) && side.contains (letter2)) { return true; } } } return false; /* * allLettersUsed - returns true if all of the letters in the puzzle * are currently being used in the solution to the puzzle, * and false otherwise */ private boolean allLetters Used() { for (String letter: this.letters) { boolean anyWord Has Letter = false; Restricted Mode 0 A 1 for (String w: this.words) { if (w.contains (letter)) { anyWord Has Letter = true; Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O LEZ. "FONSAL com wwwww RANDOMI STEZ {Java 8 : VALMW... aras, po *** Q File Edit Selection View Go Run Terminal Help LetterSquare.java - Visual Studio Code Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage Learn More J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... 171 break; 172 173 174 175 2 4 28 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 Restricted Mode /* * } * * } * } if (!anyWordHasLetter) { return false; } } return true; */ private void printSolution (int wordNum) { for (int i = 0; i File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... 198 Since this is a private helper method, we assume that only appropriate values will be passed in. 199 4 2.8 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 Restricted Mode } * LetterSquare.java - Visual Studio Code private boolean isValid (String letter, int wordNum, int charNum) { /* Replace this line with your implementation of the method. */ return false; } Learn More * In particular, we assume that letter is one of the letters of the puzzle. */ /* * solveRB - the key recursive backtracking method. * Handles the process of adding one letter to the word at position * wordNum as part of a solution with at most maxWords words. * Returns true if a solution has been found, and false otherwise. * * Since this is a private helper method, we assume that only * appropriate values will be passed in. */ private boolean solveRB (int wordNum, int charNum, int maxWords) { /* Replace this line with your implementation of the method. */ return false; public void solve() { 0 A 1 /* * solve - the method that the client calls to solve the puzzle. * Serves as a wrapper method for solveRB (), which it repeatedly calls * with a gradually increasing limit for the number of words in the solution. */ Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O LEZ. "FONEN wwwww com RACON STEZ {Java 8 : aras, po *** Q File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage Learn More J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... 226 public void solve() { 227 int maxWords = 1; 228 229 230 231 232 233 234 235 ge 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 } while (maxWords File Edit Selection View Go Run Terminal Help Restricted Mode is intended for safe code browsing. Trust this window to enable all features. Manage J LetterSquare.java 1 X C: > Users > ben > OneDrive > Desktop > part2 > problem7 > J LetterSquare.java > ... 250 System.out.print(prompts[i]); 251 252 253 254 255 256 257 258 259 } 2.8 } } sides[i] = console.nextLine(); LetterSquare puzzle = new LetterSquare (sides); System.out.println("Here is the puzzle:"); System.out.println(puzzle); puzzle.solve(); Restricted Mode 0 A 1 LetterSquare.java - Visual Studio Code Learn More Ln 1, Col 1 090 08 Spaces: 4 UTF-8 CRLF T O LEZ. "FONEN wwwww com STEZ {Java 8 : ANCONA aras, po *** Q