Backtracking algorithms

Backtracking algorithms are used to search a solution in a constructive manner. These algorithms builds the solution sequentially and weed out any in-feasible partial solutions. If you visualize the search space in the form of tree or a vector (v1,..., vn) then a backtracking algorithm will search the tree from root down in a depth first search manner and if the partial solution is in-feasible it will stop the search in that branch and search another branch of the tree. In another words if the backtracking algorithm is building a solution vector and so far has a solution vector (v1, v2). It will find the next possible element/node say v3 to add to the solution vector. Then the new solution vector will be (v1,v2,v3). It will check if this partial vector can lead to a feasible solution or not. If not the algorithm will construct another partial vector (v1,v2,v3') and keep it unless it finds one or no solution. If yes then it will go one level deep and construct the solution vector (v1, v2, v3, v4) and so on. At every step it checks if the vector is complete and has a feasible solution or not.

Backtracking algorithms can be used to solve problems like Queens problem, Knights tour, sudoku etc where we build a solution in a sequential and constructive manner.

Knight's Tour Problem

 In a Knight's tour problem one has to find a possible tour for a knight on a chessboard such that the tour covers all the squares on the chessboard. This can be easily solved by using backtracking. Here is  a JAVA implementation for a solution for  the Knight's tour problem.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;


public class KnightsTour {

 // Size of the chessboard
 private static final int MAX_X = 5;
 private static final int MAX_Y = 5;
 
 public static void main(String[] args) {
  KnightsTour kTour = new KnightsTour();
  // starting point for the Knight
  Point start = kTour.new Point(0,0);
  Set tour = new LinkedHashSet();
  tour.add(start);

  kTour.createTour(tour, start);
 }
 
 private class Point {
  int x;
  int y;
  public Point(int x, int y) {
   this.x = x;
   this.y = y;
  }
  @Override
  public int hashCode() {
   final int prime = 31;
   int result = 1;
   result = prime * result;
   result = prime * result + x;
   result = prime * result + y;
   return result;
  }
  @Override
  public boolean equals(Object obj) {
   if (this == obj)
    return true;
   if (obj == null)
    return false;
   if (getClass() != obj.getClass())
    return false;
   Point other = (Point) obj;
   if (x != other.x)
    return false;
   if (y != other.y)
    return false;
   return true;
  }
 }
 
 /**Checks if the knight has covered all the squares
  * @param tour
  * @return
  */
 private boolean isTourComplete(Set tour) {
  for (int i =0; i < MAX_X; i++) {
   for (int j = 0; j < MAX_Y; j++) {
    Point point = new Point(i,j);
    if (!tour.contains(point)) {
     return false;
    }
   }
  }
  return true;
 }
 

 /** Returns a list of all possible next moves.
  * @param lastMove
  * @return
  */
 private List getNextMoves(Point lastMove) {
  List moves = new ArrayList();
  int[] diffx = {-2, -2, -1, -1, 1, 1, 2, 2};
  int[] diffy = {-1, 1, -2, 2, -2, 2, -1, 1};
  for (int i = 0; i< diffx.length; i++) {
   int px = lastMove.x + diffx[i];
   int py = lastMove.y + diffy[i];
   if (px >= 0 && px < MAX_X && py >=0 && py < MAX_Y) {
    Point newMove = new Point(px, py);
    moves.add(newMove);
   }
  }
  return moves;
 }
 
 /**Checks if the knight has already visited this square. LinkedHashSet 
  * makes this search in constant time.
  * @param tour
  * @param move
  * @return
  */
 private boolean isValidMove(Set tour, Point move) {
  return !tour.contains(move);
 }
 
 /**Print the complete tour.
  * @param tour
  */
 private void printTour(Set tour) {
  Iterator itr = tour.iterator();
  while (itr.hasNext()) {
   Point move = itr.next();
   System.out.println(move.x + ", " + move.y);
  }  
 }
 
 /**Creates a tour recursively by backtracking.
  * @param tour
  * @param lastMove
  * @return
  */
 private boolean createTour(Set tour, Point lastMove) {
  if (isTourComplete(tour)) {
   printTour(tour);
   System.out.println();
   System.out.println();
   return true;
  }

  List nextMoves = getNextMoves(lastMove);
  for (Point move : nextMoves) {
   if (isValidMove(tour, move)) {
    Set newTour = new LinkedHashSet();
    newTour.addAll(tour);
    newTour.add(move);
    boolean hasSolution = createTour(newTour, move);
    
    if(hasSolution) {
     // Exiting here only prints one solution.
     // If all possible solution are required
     // comment out the following statement.
     System.exit(0);
    }
   }
  }
  return false;
 }
}