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(); } }