java backtracking help

[ngk]

i'm working on a program that takes in courses and it's prerequisites and outputs the total number of solutions a student could take, like the number of legal sequences...

i'm having a little trouble in my backtracking method....basically i have a hashmap with the course as the key and the prerequisites as a linked list for the value. now in this class i have another hashmap that's the courses and initially they have a value of false (Boolean) i also made an array of the course numbers for indexing ease.... if you input just 3 courses with no prerequisites it works fine, i.e. 6 legal sequences. if i input "100" and "200 100" it works fine, 1 legal sequence.

i have a test set of data that ends up with 711 outcomes instead of the 3 that it should:
350 200
100
200 100
500 350 400
300 200
400 300

so here's my code...i was wondering if anyone could point anything out....

import java.util.*;
/**
 * @author Eric Isley
 *
 */
public class Courses {
    private int n,solutionCount,key,temp,course,x;
    private boolean current;
    private HashMap theMap,taken;
    private LinkedList tempList;
    private int[] courses;
    private Object[] tempArray;
    
    public Courses(int nIn, HashMap mapIn) {
        n = nIn;
        theMap = mapIn;
        taken = new HashMap(n);
        courses = new int[n];
        solutionCount = 0;
        findSolutions();
    }
    
    private void findSolutions() {
        // set all taken values to false to begin
        Set tempSet = theMap.keySet();
        Iterator iter = tempSet.iterator();
        while(iter.hasNext()){
            taken.put(iter.next(),new Boolean(false));
        }     
        // put course numbers into an array
        tempArray = tempSet.toArray();
        solve(1);
    }
    
    private void solve(int k) {
        for(int i=k;i<=n;i++){
            x = ((Integer)tempArray[i-1]).intValue();
            if(checkPos(x)){
                taken.remove(new Integer(x));
                taken.put(new Integer(x),new Boolean(true));
                if(k == n-1)
                    solutionCount++;
                else
                    solve(k+1);
                taken.remove(new Integer(x));
                taken.put(new Integer(x),new Boolean(false));                
            } // end if
        } // end for
    } // end solve()
    
    private boolean checkPos(int x) {
        tempList = (LinkedList)theMap.get(new Integer(x));
        for(int i=0;i<tempList.size();i++) {
            temp = ((Integer)tempList.remove()).intValue();
            current = ((Boolean)taken.get(new Integer (temp))).booleanValue();
            if(current == false)
                return false;
        } // end for
        return true;
    } // end checkPos

    // returns the count
    public int getCount(){
        return solutionCount;
    }
}

 

[Nemezer]

I'll point you out to tuProlog. This type of program would be well done in that language. Then again you may very well be a sane person, in that case you shouldn't click on that link

Bearing that, I've looked at your code for a while, and though I have not found the "bug", I did find one small bug.

temp = ((Integer)tempList.remove()).intValue();
// Should probably be 
temp = ((Integer)tempList.get(i)).intValue();

At the very least, I think that is a bug. Now, before I go in futher into the debuging part, you mentioned that with your earlier set of data, there were 3 possible answers and not 711. Could you tell me what those 3 answers should be? Because, unless I'm understanding it wrong, there is only one possibility to get the course #350. That is, if you take the course #100 and the #200, then you could take #350. Could you explain to me the other two possibilities plz.

 

[ngk]

yeah i put the get in there...instead of the remove...

well for that sample data....there are 3 total ways to get through the courses....not necessarily to class #350...

i changed a few things around but i think the main problem is in that checking method....it's only checking the linked list for prerequisites, it doesn't check to make sure if that actual class has been taken...so i need to put that in there somehow...

 

[Nemezer]

well for that sample data....there are 3 total ways to get through the courses....not necessarily to class #350...

Could you tell me what are the three possibilities? I haven't quite figured it out yet. I'm sure if you would enumerate them I could be of a greater help.

 

[HorsePunchKid]

Bearing that, I've looked at your code for a while, and though I have not found the "bug", I did find one small bug.

temp = ((Integer)tempList.remove()).intValue();
// Should probably be 
temp = ((Integer)tempList.get(i)).intValue();

This is somewhat off-topic, but generics and autoboxing (among other things) could vastly simplify your code. This is somewhat out of context, but the portion Nemezer noted would become something like this:

List<Integer> tempList=new LinkedList<Integer>;
int temp=tempList.get(i);

Also, you could turn this:

Set tempSet = theMap.keySet();
        Iterator iter = tempSet.iterator();
        while(iter.hasNext()){
            taken.put(iter.next(),new Boolean(false));
        }

...into this:

Map<Integer,Boolean> theMap=new HashMap<Integer,Boolean>();
for(int course : theMap.keySet())
    taken.put(course, false);

Much more legible, I hope. It would probably also help us help you with your code if you avoided uninformative variable names like x, n, and theMap.

 

[ngk]

yeah i put in generics today once i updated my eclipse so it could handle it......i have it most of the way working but the 6 course input comes out to 1, instead of 3....smaller sets work fine and i have to turn it in so thanks anyways....