• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 739
  • Last Modified:

Recursive Backtracking

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
vrameen
Asked:
vrameen
  • 21
  • 15
  • 2
  • +1
1 Solution
 
hoomanvCommented:
Visit ( Array arr ) {
    for each element in arr {
        if ( element is of type Array )
            Visit ( (Array) element )
        else
            Print ( element )
    }
}
0
 
ADSLMarkCommented:
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
 
vrameenAuthor Commented:
@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
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
hoomanvCommented:
every different combination ? can you show us an example ?
0
 
modsiwCommented:
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
 
vrameenAuthor Commented:
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
 
modsiwCommented:
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
 
vrameenAuthor Commented:
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
 
modsiwCommented:
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
 
vrameenAuthor Commented:
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
 
modsiwCommented:
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
 
modsiwCommented:
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
 
modsiwCommented:
"The backtracking algorithm must attempt every different combination."

This is exactly what a backtracking algorith is designed to prevent.
0
 
modsiwCommented:
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
 
modsiwCommented:
err, n in the first example is 25 minus the lenght of the password
0
 
modsiwCommented:
26 even
0
 
vrameenAuthor Commented:
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
 
ADSLMarkCommented:
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
 
modsiwCommented:
"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
 
modsiwCommented:
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
 
modsiwCommented:
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
 
vrameenAuthor Commented:
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
 
modsiwCommented:
The code for check entry would also be useful.
0
 
vrameenAuthor Commented:
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
 
modsiwCommented:
Thanks, I'll get back to you in a couple hours.
0
 
vrameenAuthor Commented:
To add, the allocate() method within the allocate() method should not have been their. I was just testing some concepts.
0
 
modsiwCommented:
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
 
vrameenAuthor Commented:
That is great help modsiw..

I'll try it out and get back to you!
0
 
vrameenAuthor Commented:
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
 
vrameenAuthor Commented:
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
 
modsiwCommented:
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
 
modsiwCommented:
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
 
modsiwCommented:
Have you read / do you understand the full peices of code I posted before?
0
 
vrameenAuthor Commented:
Some of it.. I see the recursion, but I don't understand where the backtracking occurs..
0
 
vrameenAuthor Commented:
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
 
modsiwCommented:
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
 
modsiwCommented:
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
 
vrameenAuthor Commented:
"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
 
modsiwCommented:
"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
 
vrameenAuthor Commented:
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

Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

  • 21
  • 15
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now