i'm trying to write a program that basically solves a word puzzle and prints it out in a square. I want to come up with a sequence of English words in which each letter in the puzzle appears at least once. I have some parameters I want too.
Each word must be at least 3 letters long.
Adjacent letters must come from different sides of the square.
The last letter of one word of the sequence must match the first letter in the next word in the sequence.
My problem is with implementing functions, I need help writing two. isValid checks if a given letter would work as the next letter in the current word, the function has three parameters. 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.
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.
SolveRB has 3 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.
SolveRB I want to do recursive backtracking but with additional steps. In addition to a base case that checks if the puzzle has been solved, I want to make a second base case for calls in which wordNum is too big, given the value of maxWords.
If the current calling SolveRB adds another letter to the solution, I want to make two separate recursive calls:
I want make a call that attempts to expand the current word in the solution, making it one letter longer.
If the first recursive call does not find a solution then if the current word in the solution is a full word of at least three letters, I want to make a second recursive call that moves to the next word in the solution to the puzzle.
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);
// The sides of the puzzle, given as four strings of length 3.
private String[] sides;
// The individual letters in the puzzle.
// Each element of this array is a single-character string.
private String[] letters;
// The words in the solution.
private String[] words;
/*
* Constructor for a puzzle with the specified sides, where each
* side is a string containing the 3 letters from one side of the square.
*/
public LetterSquare(String[] sides) {
if (sides == null || sides.length != 4) {
throw new IllegalArgumentException(
"parameter must be an array of 4 strings");
}
this.sides = sides;
this.letters = new String[12];
int letterNum = 0;
for (int i = 0; i < sides.length; i++) {
if (sides[i] == null || sides[i].length() != 3) {
throw new IllegalArgumentException(
"invalid side string: " + sides[i]);
}
for (int j = 0; j < 3; j++) {
this.letters[letterNum] = this.sides[i].substring(j, j+1);
letterNum++;
}
}
this.words = new String[MOST_WORDS];
for (int i = 0; i < this.words.length; i++) {
this.words[i] = "";
}
}
/*
* 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:
* c a t
* d f
* o r
* g y
* p i e
*/
public String toString() {
String s = "";
// top of the square (i.e., sides[0])
for (int i = 0; i < 3; i++) {
s += " " + this.sides[0].charAt(i);
}
s += "\n";
// left and right sides (sides[1] and sides[2])
for (int i = 0; i < 3; i++) {
s += this.sides[1].charAt(i);
s += " " + this.sides[2].charAt(i);
s += "\n";
}
// bottom of the square (i.e., sides[3])
for (int i = 0; i < 3; i++) {
s += " " + this.sides[3].charAt(i);
}
s += "\n";
return s;
}
/*
* lastLetter - returns a single-character string containing
* the last letter in the specified word
*
* assumes that word is a String with at least one character
*/
private static String lastLetter(String word) {
return word.substring(word.length() - 1);
}
/*
* removeLast - returns the string that is formed by removing
* the last character of the specified word
*
* assumes that word is a String with at least one character
*/
private static String removeLast(String word) {
return word.substring(0, word.length() - 1);
}
/*
* 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;
}
/*
* removeLetter - removes the specified letter from the end of
* the word at position wordNum in the solution
* and also updates the solnString accordingly
*/
private void removeLetter(int wordNum) {
this.words[wordNum] = this.removeLast(this.words[wordNum]);
}
/*
* alreadyUsed - returns true if the specified word is already
* one of the words in the solution, and false otherwise.
*/
private boolean alreadyUsed(String word) {
for (String w : this.words) {
if (w.equals(word)) {
return true;
}
}
return false;
}
/*
* 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 allLettersUsed() {
for (String letter : this.letters) {
boolean anyWordHasLetter = false;
for (String w : this.words) {
if (w.contains(letter)) {
anyWordHasLetter = true;
break;
}
}
if (!anyWordHasLetter) {
return false;
}
}
return true;
}
/*
* printSolution - prints the words in the soln array from
* position 0 up to and including position wordNum
*/
private void printSolution(int wordNum) {
for (int i = 0; i <= wordNum; i++) {
System.out.println(this.words[i]);
}
}
/*
* isValid - returns true if the specified letter (a one-character string)
* is a valid choice for the letter in position charNum of the word at
* position wordNum in the soln, and false otherwise.
*
* Since this is a private helper method, we assume that only
* appropriate values will be passed in.
* In particular, we assume that letter is one of the letters of the puzzle.
*/
private boolean isValid(String letter, int wordNum, int charNum) {
/* Replace this line with your implementation of the method. */
return false;
}
/*
* 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;
}
/*
* 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.
*/
public void solve() {
int maxWords = 1;
while (maxWords <= MOST_WORDS) {
System.out.println("Looking for a solution of length "
+ maxWords + "...");
if (this.solveRB(0, 0, maxWords)) {
return;
}
maxWords++;
}
System.out.println("No solution found using up to "
+ MOST_WORDS + " words.");
}
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
/* get the sides of the square from the user */
String[] sides = new String[4];
String[] prompts = {"top side: ", "left side: ",
"right side: ", "bottom side: "};
for (int i = 0; i < 4; i++) {
System.out.print(prompts[i]);
sides[i] = console.nextLine();
}
LetterSquare puzzle = new LetterSquare(sides);
System.out.println("Here is the puzzle:");
System.out.println(puzzle);
puzzle.solve();
}
}