----------------------------------- Shah-Cuber Thu Jun 25, 2009 5:56 pm Short Tutorial: Backtracking With Recursion ----------------------------------- Backtracking With Recursion Obviously, out of summer boredom, there is nothing better than to make a tutorial on a random topic ... oh well, enjoy! Several problems can be solved by combining recursion with backtracking. To begin understanding what it really is, think of a maze for example. When a dead end is reached we backtrack to the last place where there was a choice in paths to take, and take the other path (assuming there were only two possibilities). If this turns out also to be a dead end, we backtrack to the previous point where there was a choice. This is a specific example of a general recursive approach to solving problems that involve searching through a space for an entity that satisfies a certain property. For traversing a maze, the space is the set of sequences of moves that can be made (drawn from turn left, turn right, move ahead without hitting a wall), and the property to satisfy is "start at the entry and arrive at the exit". The requirements for a recursive solution are met in these ways. .The problem is made smaller by taking one step in the space - by making one move. .The base case occurs when the property has been fully satisfied and we arrive at the exit. .The partial results are combined by putting the steps together in a way that is appropriate (perhaps printing them, or returning them as a list to some other program). Backtracking is an essential problem solving tool for programs where there is not enough local information to know for certain how to progress toward the desired goal. Unlike, for example, merge sorting (or any other sorting algorithm), where it is known that sorting, and merging will make progress toward the desired result, a backtracking program for searching a solution space tries one way forward: it takes a legal step that extends the partial result obtained so far and does not invalidate the property that must be satisfied. It then makes a recursive call to look for a continuation of the partial result it has just extended. Because the continuation may not exist, however, the search for it may fail. This occurs if the program tries a step forward that is taking it down a dead end street (the example of searching through a maze is a good one to keep in mind here). When a failure to find a continuation is reported, the program tries another legal step if it has one available to it, and looks for a continuation from that point. If all of the possible legal steps that it can try results in failed attempts to find a continuation, then the program must report a failure itself. This result is reported to the program that invoked it, which then, in turn, may have to try another legal step or report failure to its caller. Now that this concept has been explained, I will introduce a problem that I have done between yesterday and today, that is a very good problem to explore for programmers (some of you may have already heard of this). So, another example of backtracking with recursion is the classic problem of placing 8 Queens on a chess board of 8x8 squares in such a way that no queen threatens another (threat which returns value true if a square is threatened by a queen in another column. The method outputBoard provides the solutions and procedures a simpler representation of the board. This program searches for one solution. A variant (amongst many) would be to search for all solutions, which i will leave up to you (hint: there are 92 solutions). Explore ... ----------------------------------- DtY Fri Jun 26, 2009 12:28 am RE:Short Tutorial: Backtracking With Recursion ----------------------------------- Pretty cool tutorial, I went through it, and wanted to see if I could rewrite it without looking at your code. If anyone is interested, here it is in C: #include #include #include #include //Checks if the queen can go there //Looks at the row, colum, and diagonals bool canGoHere(bool* board, int size, int row, int col) { int i; int irow, icol; for (irow=0; irow Thanks for your contribution :D ----------------------------------- Shah-Cuber Fri Jun 26, 2009 9:52 am Re: Short Tutorial: Backtracking With Recursion ----------------------------------- Another tip, you may have realized that when placing n queens on an nxn chessboard, solutions exist only for n = 1 or n ≥ 4, so there is no solution for a 2x2 chess board, or a 3x3 chess board ... ----------------------------------- Shah-Cuber Fri Jun 26, 2009 3:56 pm Re: Short Tutorial: Backtracking With Recursion ----------------------------------- Alternative problems like this, amongst many, may include: Bishops problem: Similar to Queens problem, except it's with bishop notation. http://mathworld.wolfram.com/BishopsProblem.html Kings problem: Determining how many nonattacking kings can be placed on an nxn chessboard. http://mathworld.wolfram.com/KingsProblem.html Knights problem: Determining how many nonattacking knights can be placed on an nxn chessboard. http://mathworld.wolfram.com/KnightsProblem.html Rooks problem: ... you get the picture ... http://mathworld.wolfram.com/RooksProblem.html You may even combine some of these concepts, to make a new problem, and see what happens ... ----------------------------------- Kharybdis Fri Jun 26, 2009 4:28 pm RE:Short Tutorial: Backtracking With Recursion ----------------------------------- hmm.. chess problems are fun. ----------------------------------- Shah-Cuber Fri Jun 26, 2009 4:51 pm Re: Short Tutorial: Backtracking With Recursion ----------------------------------- OHHH, solution for a 30x30 chessboard, hmmm, reminds me of flea circus from Project Euler =P [code] Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . [/code] ----------------------------------- Shah-Cuber Sat Jun 27, 2009 7:35 pm Re: Short Tutorial: Backtracking With Recursion ----------------------------------- Ohhh, just found a nice problem on SPOJ, related to this ... http://www.spoj.pl/problems/QKP/ I'm on it :D ----------------------------------- Analysis Mode Sat Jun 27, 2009 10:37 pm Re: Short Tutorial: Backtracking With Recursion ----------------------------------- here's a more difficult one http://www.spoj.pl/problems/QUEEN/ ----------------------------------- Shah-Cuber Mon Jun 29, 2009 1:48 pm Re: Short Tutorial: Backtracking With Recursion ----------------------------------- Oh nice find Analysis Mode, i'll start on that too :D thx ----------------------------------- andersbranderud Tue Sep 08, 2009 9:06 am RE:Short Tutorial: Backtracking With Recursion ----------------------------------- Find your tutorial via google. Thanks for the tutorial! ----------- Anders Branderud bloganders.blogspot.com ----------------------------------- Shah-Cuber Tue Sep 08, 2009 12:25 pm Re: Short Tutorial: Backtracking With Recursion ----------------------------------- No problem :) ----------------------------------- dumisan Sun Jan 09, 2011 8:11 am Re: Short Tutorial: Backtracking With Recursion ----------------------------------- I'd like to add here a version of nqueen problem solution useing backtracking that gives all the posible solutions, each solution as a permutation but is not useing recursion(kinda not likeing it) so something like (1 5 8 6 3 7 2 4) means that on the first row the queens is placed in the first position, on the second row the queen is on th 5th position so on .. [CODE] public class nquens { public static void main(String args[]) { System.out.println("give n"); java.util.Scanner in = new java.util.Scanner(System.in); int n = in.nextInt(); in.close(); if((n==2)||(n==3)) System.out.println("The problem have no solutions"); else { int sp = 1; int[] x = new int[n]; int k = 0; x[0] = 0; while (k >= 0) { x[k] = x[k] + 1; if (x[k] > n) { k = k - 1; } else { sp = 1; for (int i = 0; i