Page 1 of 1

A Look at Backtracking Rate Topic: -----

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10595
  • View blog
  • Posts: 39,246
  • Joined: 27-December 08

Posted 03 December 2011 - 02:58 PM

This tutorial will focus on a technique called backtracking. When implementing backtracking algorithms, recursion is generally used, so I strongly recommend checking out my tutorial Data Structures: Recursion, Stacks, and Trees if you need to brush up on your recursion.

The idea behind backtracking is to attempt a possible solution, then as the name implies, backtrack and try another if that path doesn't pan out. Backtracking is applicable to problems like the Knight's Tour, N-Queens, and maze solving problems.

Now let's look more specifically at the general algorithm for backtracking:
-Pick a starting point
-While the problem isn't solved
       -For each path from the starting point
             -Set that as the starting point and recurse
             -If it returns true, then return true
       -Undo the current move (since none of the options panned out)
       -Return false



Notice how the algorithm returns whether or not the attempt panned out. If it didn't, then move onto the next one. If none of the possible attempts from the given point worked out, then undo the current move and return false. It is important to undo the current move so as to return the state of the program before attempting the given path.

Let's examine backtracking in action with the Knight's Tour Problem. The idea behind the Knight's Tour problem is for a Knight to start on one space on an m x n grid, and visit each space exactly once. A Knight is limited in its movements to either two rows and one column, or one row and two columns. This is where the backtracking comes in. If the Knight reaches a dead end, then it is important to backtrack and try another avenue. For pedagogic value, I have printed the grid in the method so the various steps can be more visually illustrated. Note that this is a basic, brute force version simply for illustrating the concept of backtracking.
import java.awt.Point;

/**
 * @author Michael Levet
 * @date 12/3/2011
 * 
 * This class sets up a grid to execute the Knight's Tour problem.
 * Given a grid of size m x n and a single Knight at point (x,y), the
 * Knight attempts to visit each space on the grid exactly once. 
 ***/
class KnightsTour{

    private boolean[][] grid;
    private int count, spaces;
    
    //the possible moves for the Knight
    private static final Point[] MOVES = new Point[]{
        new Point(-2, -1),
        new Point(-2, 1),
        new Point(2, -1),
        new Point(2, 1),
        new Point(-1, -2),
        new Point(-1, 2),
        new Point(1, -2),
        new Point(1, 2)
    };
    
    /**
     * @param rows The number of rows
     * @param cols The number of columns
     ***/
    public KnightsTour(int rows, int cols){
        grid = new boolean[rows][cols];
        spaces = rows * cols;
        count = 0;
    }
    
    /**
     * @param row The current row of the Knight
     * @param col The current column of the Knight
     * @return boolean: true if the Knight visits all of the 
     *                  spaces on the grid, false otherwise
     * 
     * This method starts with the current space for the Knight.
     * From there, it flags the current space as occupied and increments
     * the counter for the number of occupied spaces. The unvisited
     * spaces are visited individually in a depth-first manner in 
     * an attempt to determine if the path will lead to a solution. If 
     * it does, true is returned. If not, the current move is undone, the counter
     * is decremented, and false is returned.
     *
     ***/
    public boolean tourFrom(int row, int col){
        
        grid[row][col] = true;
        count++;
        
        if(count == spaces)
            return true;
        
        for(Point p:MOVES){
            int nextRow = row + p.x;
            int nextCol = col + p.y;
            
            if(nextRow < 0 || nextRow >= grid.length)
                continue;
            
            else if(nextCol < 0 || nextCol >= grid.length)
                continue;
            
            else if(grid[nextRow][nextCol])
                continue;
            
            if(tourFrom(row+p.x, col+p.y))
                return true;
        }
        
        printGrid();
        grid[row][col] = false;
        count--;
        return false;
    }
    
    private void printGrid(){
        System.out.println("Count: " + count);
        for(boolean[] rows:grid){
            for(boolean b:rows){
                System.out.print((b) ? "T":"F");
            }            
            System.out.println();
        }
        System.out.println("\n");
    }
    
    public static void main(String[] args){
        KnightsTour tour = new KnightsTour(5,5);
        tour.tourFrom(0, 0);
        tour.printGrid();
    }
    
   
}



Is This A Good Question/Topic? 4
  • +

Replies To: A Look at Backtracking

#2 b.szabolcs  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 5
  • Joined: 04-February 12

Posted 12 February 2012 - 12:50 PM

Thanks for this tutorial!

For those who want to compile it, there's a typo at this method (that capital B should be a lower case b ) :
private void printGrid(){
        System.out.println("Count: " + count);
        for(boolean[] rows:grid){
            for(boolean b:rows){
                System.out.print((B)/> ? "T":"F");
            }            
            System.out.println();
        }
        System.out.println("\n");
    }


Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10595
  • View blog
  • Posts: 39,246
  • Joined: 27-December 08

Posted 12 February 2012 - 02:00 PM

It's a known forum bug, not a typo. :)
Was This Post Helpful? 0
  • +
  • -

#4 b.szabolcs  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 5
  • Joined: 04-February 12

Posted 12 February 2012 - 03:44 PM

View Postmacosxnerd101, on 12 February 2012 - 02:00 PM, said:

It's a known forum bug, not a typo. :)


Sorry, it was quite obvious anyways. I'm a newbie here!! :D
Was This Post Helpful? 0
  • +
  • -

#5 pallopammy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 27-April 14

Posted 27 April 2014 - 12:59 AM

What if some board and knight position have no solution and we want to display a message specifying so.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10595
  • View blog
  • Posts: 39,246
  • Joined: 27-December 08

Posted 27 April 2014 - 10:38 AM

The Knight's Tour problem is also the Hamiltonian Circuit problem. There are lots of theorems with regards to the existence of a Hamiltonian Circuit in a graph. Check out Dirac's Theorem and Ore's Theorem. You should be able to figure out before trying to move the knight whether or not there is a solution using said theorems.
Was This Post Helpful? 0
  • +
  • -

#7 ekaknr  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 06-August 14

Posted 07 September 2014 - 03:05 AM

I'm using this concept of backtracking (awt point to move about) in my project. is it alright if I post my recursive function here ? can you help point out where I'm going wrong ? I've tried for a couple of days and still cannot find out my mistake.

Best regards,
ekaknr
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10595
  • View blog
  • Posts: 39,246
  • Joined: 27-December 08

Posted 07 September 2014 - 08:45 AM

You should post for help in the general Java forum, not on this tutorial.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1