Backtracking — Interview Problem

Many computer science problems have a solution which needs to be searched in a solution space. For some of these problems, the solution is made of many sub solutions. For eg. to find a way to place 8 queens on an 8x8 chessboard such that no queen threatens each other, the solution will comprise of finding one safe position each for all the eight queens. This problem can be approached by safely placing one queen at a time on the chessboard. You can visualize this solution space as a tree where each level represents all the positions one of the queens can take. There will be total 8 levels (one for each queen) plus root node. And each node till leaf nodes will have eight children. The solution will be all path from the root to a leaf node in which queen’s position do not threaten each other.

Backtracking algorithms are used to search the solution space in a constructive manner. These algorithms build the solution sequentially and weed out any in-feasible partial solutions. Therefore the algorithm will determine whether it should consider remaining part of the path from the root to a leaf or should it move on to the next path. In general as mentioned before you can 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 path and search another path of the tree. In another word, 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 without visiting them twice. 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;
 }
}