Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Recursion issues.

  1. #1
    Junior Member
    Join Date
    Apr 2011
    Posts
    2
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Recursion issues.

    I'm having some difficulty with a recursive method with backtracking. The program is supposed to simulate a Boggle type board, and given the entered word, search the board (as well as a dictionary) recursively to see if the word is on the board. Below are the pertinent methods, the first being the main method that prompts the user (nothing more than println statements atm), the second the method that searches the board. I didn't include the methods that search the dictionary file, as they are working properly. The boggle board is stored as a two dimensional array[r][c] of strings. The variable search is also a two dimensional array, but of boolean values. You help is greatly appreciated. Oh, and one final thing, the onBoard method is in a separate class from the main method. .java files are attached as .txt files at the end. Again, thanks for any help.

    public static void main(String[] args) {
    		Dictionary d = new Dictionary();
    		BoggleBoard b = new BoggleBoard();
    		Scanner key = new Scanner(System.in);
    		String word = "";
    		boolean testContinue = true;
    		boolean testOnBoard = false;
    		boolean testInDict = false;
    		int i = 0;
     
    		while (testContinue) {
    			b.printBoard();
    			System.out.println("Enter a word (enter \"asdf\" to quit): ");
    			word = key.nextLine();
    			if (word.equalsIgnoreCase("asdf")) testContinue = false;
    			else {
    				testInDict=d.wordSearch(word.toLowerCase());
     
    				while (!testOnBoard && testInDict && i < b.getSize()*b.getSize()) {
    					testOnBoard = b.onBoard(word);
    					i++;
    				}
     
    				System.out.println("inDict = " + testInDict);
    				System.out.println("onBoard = " + testOnBoard);
     
    				testOnBoard = false;
    				testInDict = false;
    			}
    		}
     
    public boolean onBoard(String word) {
    		for(int i = 0;i < size;i++){
    			for(int j = 0;j < size; j++)
    				searched[i][j] = false;
    		}
    		return onBoard(word,0,0,0);
     
    	}
     
    	private boolean onBoard(String word, int index, int r, int c) {
     
    		//check to see if [r,c] is on the board, and has not been searched
    		if (c >= 0 && c < size && r >= 0 && r<size && searched[r][c]==false){
    			searched[r][c] = true;
    			//check to see if the letter at [r,c] is the next letter in the word
    			if (board[r][c].equalsIgnoreCase(word.substring(index,index+1))) {
    				//return true if it is the last letter in the word
    				if (index == word.length()-1) {
    					return true;
    				}
    				//search each surrounding letter
    				else if (
    					(onBoard(word,index+1,r,c+1)) ||
    					(onBoard(word,index+1,r+1,c+1)) ||
    					(onBoard(word,index+1,r-1,c+1)) ||
    					(onBoard(word,index+1,r,c-1)) ||
    					(onBoard(word,index+1,r+1,c-1)) ||
    					(onBoard(word,index+1,r-1,c-1)) ||
    					(onBoard(word,index+1,r-1,c)) ||
    					(onBoard(word,index+1,r+1,c)) ) return true;
    			}
    			else {
    				searched[r][c] = false; 
    			}
    		}
    		return false;
    	}

    BoggleBoard.txtDictionary.txtBoggleMain.txt
    Last edited by ender16; April 30th, 2011 at 07:11 PM. Reason: Attached source files.


  2. #2
    Junior Member
    Join Date
    Apr 2011
    Posts
    2
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Recursion issues.

    I guess I probably should have mentioned what the problem is: the onBoard method fails to return true.

  3. #3
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,330
    Thanks
    181
    Thanked 829 Times in 772 Posts
    Blog Entries
    5

    Default Re: Recursion issues.

    The code you posted is not compilable, with variables in the method in question that are undefined. It would help to remove any excess details and post something compilable that reproduces your problem (eg, an SSCCE)

  4. The Following User Says Thank You to copeg For This Useful Post:

    ender16 (April 30th, 2011)

Similar Threads

  1. [SOLVED] Recursion help
    By Actinistia in forum Java Theory & Questions
    Replies: 3
    Last Post: March 21st, 2011, 12:26 PM
  2. Recursion
    By javapenguin in forum Algorithms & Recursion
    Replies: 12
    Last Post: October 18th, 2010, 03:42 PM
  3. recursion problem, please help
    By nil in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 18th, 2010, 12:59 PM
  4. Recursion Help
    By vmr in forum Algorithms & Recursion
    Replies: 3
    Last Post: April 1st, 2010, 11:27 PM
  5. Recursion help
    By rhoruns in forum Algorithms & Recursion
    Replies: 4
    Last Post: January 8th, 2010, 10:50 PM