#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    1
    Rep Power
    0

    Help with recursive backtracking


    So, I'm implementing a recursive method that searches a 4x4 Boggle board and finds all valid words. I have this helper method to facilitate searching. Boardmarks is the collection of visited/unvisited spaces, Location is simple (row,col) object, and wordpath is a StringBuffer used to build a word as it searches the board.

    Code:
    private void searchHelper(BoardMarks m, Location loc, WordPath wp) {
        int row = loc.getRow();
        int col = loc.getCol();
        int nRC = 3;
        LinkedList<Location> templist = new LinkedList<Location>();
    
        //base case: no neighbors
        //add neighbors to list and check if list is empty
        for (Location loc1: m.getNeighbors(loc)) {
            templist.add(loc1);
        }
    
        //has no neighbors
        //check if wordpath is a word. If it is, add to list, go back
        //if not, go back
        if (templist.isEmpty()) {
            if(words.isWord(wp.toString())) {
                foundWords.add(wp.toString());
                return;
            }
            //remove last letter, return
            wp.pop();
            return;
        }
    
        //mark as visited
        m.mark(loc);
        //add to wordPath
        wp.push(board.getValue(loc));
        //check if it is a word
        if(words.isWord(wp.toString()) == true) {
            //if the word has not been found and is 3 or more chars
            if((!foundWords.contains(wp.toString())) && wp.toString().length() >= 3 ) {
                //add word
                foundWords.add(wp.toString());
            }
        }
    
        //recurse through neighbors
        for (Location loc2: m.getNeighbors(loc)) {
            searchHelper(m, loc2, wp);
        }
    
        //searched all neighbors
        //clear boardmarks/wordPath
        marks = new BoardMarks();
        wPath = new WordPath();
        //go to next location
        //reached final space in board (3,3)
        if ((row + 1) > nRC) {
            if((col + 1) > nRC) {
                //done
                return;
            }
        }
        //haven't reached end of column
        else if ((col + 1) < nRC) {
            //continue through column
            searchHelper(marks, new Location(row, col + 1), wPath);
        }
        //otherwise, keep going through column
        else {
            searchHelper(marks, new Location(row + 1, 0), wPath);
        }
    
    }
    Trying to test it with a small word list, I end up getting a StackOverflowError, so I think there is a problem with my recursive calls? I've tried stepping through with the debugger to see what is going on, but it is getting very time consuming. Just want to see if anything stands out to anybody, because it is not for me. I've unit tested all of my other classes and they work perfectly before I started writing the searcher class.
  2. #2
  3. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,699
    Rep Power
    347
    Can you post a small, simple program that compiles, executes and shows the problem.

    I use println statements to show the program's progress and the values of variables as it executes.

IMN logo majestic logo threadwatch logo seochat tools logo