Solved

Recursive Backtracking

Posted on 2006-11-29
41
675 Views
Last Modified: 2010-05-18
Hi,

I want to be able to search a 2d array, but want to do it recursively and using some sort of backtracking algorithm...

For example..
I have an array: arr[][]
I want go through the entire array (it will have a user defined fixed length), and find out which slots are empty and which are not...

Please try and keep the code simple and comment it. Ive looked at examples here and couldn't understand them thoroughly...

Thanks :)
0
Comment
Question by:vrameen
  • 21
  • 15
  • 2
  • +1
41 Comments
 
LVL 14

Expert Comment

by:hoomanv
ID: 18038606
Visit ( Array arr ) {
    for each element in arr {
        if ( element is of type Array )
            Visit ( (Array) element )
        else
            Print ( element )
    }
}
0
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18038641
Why recursive and on what do you want to backtrack?
Two simple loops will do the whole trick..

Since you want to "go through the entire array", I do not see any use for recursion or backtracking.
Simple code would be:

for(int i=0;i<arr.length;i++)
    for(int j=0;j<arr[i].length;j++)
        //check is empty on array element: arr[i][j]

Mark
0
 

Author Comment

by:vrameen
ID: 18182647
@girionis

Neither answer addressed the question...

@adslmark

This is for a timetabling system. The backtracking algorithm must attempt every different combination. Backtracking has to be done recursively. Thus the two for loops doesn't satisfy the problem..

Thanks.
0
 
LVL 14

Expert Comment

by:hoomanv
ID: 18182688
every different combination ? can you show us an example ?
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18412763
The code ADSLMark posted will "attempt every different combination" although it is not recursive.

Why is being recursive required? Homework?

Programmers tend to love recursion; however, it is almost always the worst way to accomplish the task.

//////////////////////////////////////////////

String[][] aryPrint = new String[2][0];

aryPrint[0] = new String[]{"1st","2nd","3rd"};
aryPrint[1] = new String[]{"4th","5th"};

for (int i = 0; i < aryPrint.length; i++)
    for (int j = 0; j < aryPrint[i].length; j++)
        System.out.println(aryPrint[i][j]);


///////////////////////////////////////

The above code will print:
1st
2nd
3rd
4th
5th
0
 

Author Comment

by:vrameen
ID: 18793637
The positioning of the elements can change at anytime, thus a backtracking algorithm is needed to try different solutions of different combinations in a tree like structure..
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18793697
The code I posted on jan 27 will look at every element in the 2d array; however, it isn't recursive.

Recursion isn't required to do what you want. Recursion should be avoided unless required. The double for loop requires far less resources.

If you had an array of different depths, that 'might' require recursion, but that isn't the case here.
0
 

Author Comment

by:vrameen
ID: 18793874
Really, I am 100% sure recursive backtracking is required. So I think we should go back on topic rather than debating what my requirement is..
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18793935
If you were 100% sure, you'd know how to write it. You're incorrect. Recursion is not need to transverse a fixed dimensional array. Assuming you wanted to transverse it with recursion, below is how. This is the same logic as hoomanv posted in pseudo. For a fixed dimensional (depth) array. Nested for loops are easier to understand and run faster.

public static void yourMethod (Object[] array)
{
  for (int i = 0; i < array.length; i++)
  {
    if (array[i] instanceof Object[]) yourMethod((Object[])array[i]);
    else if (array[i] == null) System.out.println("This pointer is null.");
  }
}
0
 

Author Comment

by:vrameen
ID: 18796934
I spoke to my professor at University about this. His main area of research is Algorithms and Data structures.. He said recursive backtracking is necessary..

I spoke to another lecturer that does research in automatas etc. and he also said recursive backtracking is necessary..

So once again, I am 100% sure, i want recursive backtracking. I appreciate your help modsiw, but like I mentioned before.. I have requested help on this topic, and would like assistance in this topic. Thank you for the suggestion and attempt to point me in the direction you think is right, but that is not what the question asked..

If anybody can help with the question rather than keep telling me what you *think* I need, then it would be most appreciated..

Thank you
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18797307
The code in my last comment is recursion.

Either something is being miscommunicated, or your proffesssors are wrong. For a fixed 2d Array. The following two constructs will transverse the array in the same way.

public static void yourMethod (Object[] array)
{
  for (int i = 0; i < array.length; i++)
  {
    if (array[i] instanceof Object[]) yourMethod((Object[])array[i]);
    else if (array[i] == null) System.out.println("This pointer is null.");
  }
}

//------------------------------------------------------

for (int i = 0; i < aryPrint.length; i++)
    for (int j = 0; j < aryPrint[i].length; j++)
        System.out.println(aryPrint[i][j]);
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18797316
http://en.wikipedia.org/wiki/Backtracking

Backtracking is used in combinatorial mathmatics. It's strength over evaluating full combinations, is that if the 'buisness logic' dictates the current branch is impossible, it can skip large chunks of combinations.

This advantage is greatly reduced since your depth is very small (2). Secondly, you are looking for emply slots (presumably at the terminating nodes). Backtracking will not improve this sort of combinatorial search.
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18797327
"The backtracking algorithm must attempt every different combination."

This is exactly what a backtracking algorith is designed to prevent.
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18797333
Suppose you know someones password is all letters, not case sensative, and that no letter is used twice.

When considering that combinations AA and everything longer than 3 letters that starts with AA can not be legal, so it is disregarded.

Using backtracking to genereate the combinations, you will solve the password in 26! - n! / 2 time where n is the length of the password. Using starting combinations, you will solve it in 26^n / 2 time.



Your problem does not illustrate the advantage a backtracking algorithm could give you.
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18797341
err, n in the first example is 25 minus the lenght of the password
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18797349
26 even
0
 

Author Comment

by:vrameen
ID: 18799497
The problem I am trying to solve is the timetabling problem. It requires recursive backtracking. I'm sure you'll agree that when it comes to a CSP, recursive backtracking is needed..
0
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18799517
Sure.

Could you give us a precise description of what you want to achieve?
Also post any code you already got thus far...

Thank you!
Mark
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18800055
"I'm sure you'll agree that when it comes to a CSP, recursive backtracking is needed."

Not always.

Backtracking is one of many tricks often used to solve a constraint satisfaction problem faster than brute force combinations. It doesn't always make sense to use it. Backtracking doesn't necessarily have to be implemented with recursion either; however, it is the most common implementation.


Given the general problem of finding a value in the last dimension of an even depth array:
I believe backtracking is undesirable. Since you have to independently consider the last node on each branch to determine if it is a solution, there is no gain. Due to the overhead of recursion, it makes backtracking worse than straight combinations using a for loop. If you want to solve this in the fastest manner, recursion is not the way to go.

Given the general problem of finding a value in the last dimension of an varying depth array:
Something more dynamic is required to transverse the entire array-tree-structure. Backtracking would preform this kind of transversal, and simple nesting of for loops can not. This should still be taken with a grain of salt, since you are still unable to use short circuiting in the backtracking.

Presuming you want to use recursive backtracking in spite of this to transverse your array-tree-structure, there are pseudo and java code in this thread giving that example. Once again, that code is posted below, this time using tail recursion. Tail recursion can be unrolled by the JVM to run faster.


recursiveBacktracking (Object[] array)
{
  for(int i = 0, ii = array.length; i < ii; i++)
  {
    if(!array[i] instanceof Object[]) System.out.println(array[i]);
    else recursiveBacktracking (array[i]);
  }
}

PS:
A few real world examples:

Backtracking w/ short circuiting makes evaluating boolean expressions faster.
(true || (true && false && true)) will only consider 1 of 4 total statements in the 2 expressions. Assuming you add enough parentheses you can have a very deep tree structure of boolean expressions. If each statement was a determined by a call to a time consuming method, then the backtrackting w/ short circuiting will have a large pay off.

Regular expressions also make use of recursive backtracking to work efficiently.
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18800143
Please understand that I'm not trying to dodge your question. The question was answered in pseudo in the first reply by hoomanv. It was answered in java w/ an example of how it visits "every different example" in my first comment.

Both hoomanv and myself have given you the algorithm you have asked for. These solutions solve the problem by "do[ing] it recursively and using some sort of backtracking algorithm."

If the code posted by hoomanv and myself aren't what you explicitly asked for, then we have failed to communicate about what you are looking for. Perhaps a more in depth explanation is needed.



In my opinion, I believe that it also important to note that backtracking isn't wise in your situation. Presumably, one would be interested in the fasted solution for the problem at hand, as well as, the "niftiest".
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 3

Expert Comment

by:modsiw
ID: 18800151
It may also be worth noting that ADSLMarks's solution of the two for loops (below) is technically backtracking although it isn't recursive. Simple short circuiting could be introduced into this construct with breaks and escape variables.



for(int i=0;i<arr.length;i++)
    for(int j=0;j<arr[i].length;j++)
        //check is empty on array element: arr[i][j]
0
 

Author Comment

by:vrameen
ID: 18819722
Thanks for the information modsiw..
Below is the method I have for doing for the allocation. It follows the same principle of two For loops. However, I want to use recursive backtracking here.. Any advice or suggestions on how backtracking can be implemented here?:

    public void allocate() {
 
        Assist ast = new Assist();
        int b=0;
     
        for (int j=0; j < days.length; j++) {
            for (int i=0; i<total_time; i++) {
                while(i < total_time) {
                    if (i == total_time) {
                        System.out.println("Reached end of day");
                        System.out.println(i);
                        j++;
                        System.out.println(j);
                        i=0;
                    } else if (ast.checkEntry(j, i) ==  true){
                        b = Assist.getRandNum(dbManage.list.size()-1);
                        try {
                            this.slots[j][i] = (String) dbManage.list.get(b);
                        } catch (Exception e) {
                       
                        }
                        i++;
                    } else {
                        allocate();
                    break;
                    }
                }
            }
        }
    }

the checkEntry() calls a method to check if they particular slot is free or not..
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18819831
The code for check entry would also be useful.
0
 

Author Comment

by:vrameen
ID: 18819925
Apologies..

Here is the code for checkentry:

  public boolean checkEntry(int a, int b) {
       
        if(TT.slots[a][b] == null) {
            return true;
        }
       
        return false;
    }
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18819934
Thanks, I'll get back to you in a couple hours.
0
 

Author Comment

by:vrameen
ID: 18819949
To add, the allocate() method within the allocate() method should not have been their. I was just testing some concepts.
0
 
LVL 3

Accepted Solution

by:
modsiw earned 500 total points
ID: 18820190
If this doesn't compile or has syntax errors, sorry. I'm in a conference at the moment and cant test.


    // Faster way without recursion. Basicly this is what yo already have but cleaner.
    // Your i and j is backwards from common form. Usually the outer most loop is i. The letters 'count up' as the loops get deeper.
    public void allocate() {
        Assist ast = new Assist();
        for (int j=0; j < days.length; j++) {
            for (int i=0; i<total_time; i++) {
                if (slots[j][i] == null){
                    try {
                        slots[j][i] = (String) dbManage.list.get(Assist.getRandNum(dbManage.list.size()-1));
                    } catch (Exception e) {
                    }
                }
            }
        }
    }








    // Below are the two methods to do this recursivly.
    // This is a method to jumpstart the recursion.
    // Inorder to do this with recursion, slots must be an Object[] (no other kind of array will work).
    public void allocateRecurse()
    {
        allocateRecurse(slots)
    }

    // This is the recursive method
    public void allocateRecurse(Object[] slots)
    {
        for (int i = 0; i < slots.length; i++) {
            if (slots[i] == null) {
                try {
                    slots[i] = (String) dbManage.list.get(Assist.getRandNum(dbManage.list.size()-1));
                }
            } else if (slots[i] instanceof Object[]) {
              allocateRecurse((Object[])slots[i]); // here is the recursive call.
            }
        }
    }
0
 

Author Comment

by:vrameen
ID: 18820496
That is great help modsiw..

I'll try it out and get back to you!
0
 

Author Comment

by:vrameen
ID: 18832418
Right, I have this code now:

    public void allocate(Object[] slots) {
 
        Assist ast = new Assist();
        int b=0;
     
        for (int j=0; j < days.length; j++) {
            for (int i=0; i<total_time; i++) {
                while(i < total_time) {
                    if (i == total_time) {
                        System.out.println("Reached end of day");
                        System.out.println(i);
                        j++;
                        System.out.println(j);
                        i=0;
                    } else if (ast.checkEntry(j, i) ==  true){
                        b = Assist.getRandNum(dbManage.list.size()-1);
                        try {
                            this.slots[j][i] = (String) dbManage.list.get(b);
                        } catch (Exception e) {
                       
                        }
                        i++;
                    } else {
                        allocate((Object[]) slots[i][j]);
                   
                    }
                }
            }
        }
    }

But I get the error:  Array Required, but java.lang.Object found
The error is for the line: allocate((Object[]) slots[i][j]);

Any ideas?
0
 

Author Comment

by:vrameen
ID: 18832429
Forgot to add a piece of code..
New code is:

  public void allocate(Object[] slots) {
 
        Assist ast = new Assist();
        int b=0;
     
        for (int j=0; j < days.length; j++) {
            for (int i=0; i<total_time; i++) {
                while(i < total_time) {
                    if (i == total_time) {
                        System.out.println("Reached end of day");
                        System.out.println(i);
                        j++;
                        System.out.println(j);
                        i=0;
                    } else if (ast.checkEntry(j, i) ==  true){
                        b = Assist.getRandNum(dbManage.list.size()-1);
                        try {
                            this.slots[j][i] = (String) dbManage.list.get(b);
                        } catch (Exception e) {
                       
                        }
                        i++;
                    } else if ((slots[i][j] instanceof Object[]) ) {
                        allocate((Object[]) slots[i][j]);
                   
                    }
                }
            }
        }
    }

But i get the same error for: ((slots[i][j] instanceof Object[]) )
and allocate((Object[]) slots[i][j]);

0
 
LVL 3

Expert Comment

by:modsiw
ID: 18833099
The element at slots[i][j] is not an instance of an object.

You don't need to loop and recurse.

Also, your i and j seem to be backwards, which will lead to an index out of bounds
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18833112
woops

"The element at slots[i][j] is not an instance of an object."

should have been

"The element at slots[i][j] is not an instance of an object array."
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18833120
Have you read / do you understand the full peices of code I posted before?
0
 

Author Comment

by:vrameen
ID: 18833499
Some of it.. I see the recursion, but I don't understand where the backtracking occurs..
0
 

Author Comment

by:vrameen
ID: 18838008
Ok..

I have worked on the problem a bit more, and believe I have a recursive backtracking algorithm. It seems to work as when it fails on a certain restriction, it successfully goes to the previous decision point and attempts again..

Here is the code:

   public void cAllocate (String mod) {
        int rn;
        int rns;
       
        rn = Assist.getRandNuma(total_time);
        rns = Assist.getRandNuma(5);
        Assist ast = new Assist();
              //  for (int i=0; i<5; i++) {
      //  slots[rns][rn] = "bug";
        if(ast.checkEntry(rns, rn)==true) {
            slots[rns][rn]=mod;
            System.out.println(rn);
           
       } else if (attempts == (total_time*20)) {
            System.out.println("ALL COMBINATIONS ATTEMPTED - ALLOCATION UNSUCCESSFUL FOR MODULE " + mod);
            System.out.println(attempts);
           
                       
        } else {
             attempts++;
            cAllocate(mod);
   
        }
       
         
    }

If anyone can have a look at that code and confirm if it is indeed backtracking recursively?
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18838189
It is looking at elements in the tree randomly, not transversing it. So, it isn't backtracking unless you use a very loose definition.

There is also a high danger that you will not visit each element.

By definition, it is recursive; however, you aren't using it the way recursion was designed. You've just made a very complicated loop.


0
 
LVL 3

Expert Comment

by:modsiw
ID: 18838214
I don't believe you have a firm grasp on how to use recursion / what it's susposed to do. I'd recommend the following reading:


http://en.wikipedia.org/wiki/Recursion

part 9 of: http://chortle.ccsu.edu/CS151/cs151java.html
0
 

Author Comment

by:vrameen
ID: 18838784
"You've just made a very complicated loop."

Well, isn't that the point of recursion? To loop?

I'm randomly assigning a lecture to random slot. Not necessarily randomly going through a tree. The recursion is making the tree..?
0
 
LVL 3

Expert Comment

by:modsiw
ID: 18838907
"Well, isn't that the point of recursion? To loop?" - No. Tutorials can explain it better than me. Use the google. The bottom line is, it's going to take reading.

Also, I'd suggest you look at the example of recursion I gave you earlier. mentally step though it (use paper and pencil). Look at the program flow.





        rn = Assist.getRandNuma(total_time);
        rns = Assist.getRandNuma(5);
This code is randomly selecting an element to test. It will likely check the same one many times and miss others completely.
0
 

Author Comment

by:vrameen
ID: 18838964
Hi Modisw,

The random part I know about. That was to test the code. In the real thing, it will only choose numbers that haven't been attempted yet..

I have actually looked through your code. Written it down and searched the internet & here for more backtracking problems with solutions...

The algorithm I posted is really simple, but visualising what it actually does looks like a tree structure as it continues further. The algorithm still needs to be improved to implement further constraint checking.

For classes which do not have any constraints, the sequential allocation posted originally is to be used as no constraints need to be matched. Plus CSP's require the backtracking, not those without a constraint..

Believe when I say I have spent countless hours trying to figure this out, and you can see when this was originally posted how long I've been trying to solve this problem..

An idea, any possibility of discussing this over live messenger or something? Don't hesitate to say no, I will completely understand :-)
0

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Suggested Solutions

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now