[알고리즘] Algorithms Study with JAVA - Backtracking

Introduction

To backtrack means going back to a previous step. Backtracking algorithm is applied to problems finding the solution step-by-step. For instance, we use backtracking algorithm for searching the path to a destination in a maze. On every direction taken carefully, algorithm judges whether this choice would lead to an escape. If a step taken currently is confirmed to be a part of the possible path, the algorithm keeps being in the process, otherwise it backtracks to a previous step. Then the algorithm considers other steps that satisfy the criteria in a same way. To simplify, there are two verification stages, the first of which checks a step's current state and the second of which diagnoses its adequacy to the problem as a whole.

Implementation

There are many applications of Backtracking algorithm, for instance, N Queen Problem, The Knight's tour problem, and so forth. However, these are more appropriate for programmers with advanced understanding and skills. Since purpose of this article is skimming basic principles of the algorithm, it seems to be more reasonable to study the other, less common but more initative "Finding an way out from a maze" problem. As a matter of fact, this is also one of the most well known usages of Backtracking algorithm as mentioned above. Its implementation may vary, but in this article the one with simplest structure would be used as an example. Below is a brief outline of how a solution to "Maze problem" is composed:

1. A matrix that stores information of a maze that indicates a starting point, a destination, blocked and possible paths.
2. A direction to which maze runner may take, represented by changes in coordinates.
3. A function that tracks and flags wherever the maze runner passes.

It is rather obvious here what data structure would be used and what value must be returned from the function. To clarify, 2-dimensional array must represent a matrix, an array element of which a pair of two vlaues, quantity changes in x and y coordinates, would be a direction. A function could either return updated matrix or nothing. Below is an actual code snippets written on the basis of this analysis:

import java.util.*;

public class RatInAMaze {

  public int[][] dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};
  public String[] dirStr = {"D", "U", "R", "L"};

  public static void printMaze(int[][] maze) {
    for (int i = 0; i < maze.length; i++) {
      for (int j = 0; j < maze[i].length; j++) {
        System.out.print(maze[i][j]);
      }
      System.out.println();
    }
  }

  public ArrayList<String> ratInAMaze(int[][] maze, int[][] solMaze, int yCoord, 
						int xCoord, String path, boolean ok) {
    int newYCoord = 0;
    int newXCoord = 0;

    if (!ok) {
      solMaze[yCoord][xCoord] = 1;
    }
    
    ArrayList<Integer> coords = new ArrayList<Integer>();
    ArrayList<String> paths = new ArrayList<String>();
    ArrayList<String> answers = new ArrayList<String>();
    ArrayList<String> tmp = new ArrayList<String>();

    if (maze[maze.length-1][maze[0].length-1] == 0) {
      return answers;
    }

    if (yCoord == maze.length-1 && xCoord == maze[yCoord].length-1) {
      solMaze[yCoord][xCoord] = 0;
      answers.add(path);
      return answers;
    }

    for (int i = 0; i < 4; i++) {
      if (yCoord + dir[i][0] < maze.length && xCoord + dir[i][1] < maze[yCoord].length 
					&& yCoord + dir[i][0] >= 0 && xCoord + dir[i][1] >= 0 
					&& solMaze[yCoord+dir[i][0]][xCoord+dir[i][1]] == 0) {
        if (maze[yCoord + dir[i][0]][xCoord + dir[i][1]] == 1) {
          if (!ok) {
            solMaze[yCoord+dir[i][0]][xCoord+dir[i][1]] = 1;
          }
          paths.add(dirStr[i]);
          coords.add(i);
          newYCoord = yCoord + dir[i][0];
          newXCoord = xCoord + dir[i][1];
        }
      }
    }

    if (coords.size() > 1) {
      for (int j = 0; j < coords.size(); j++) {
        path += paths.get(j);
        tmp = ratInAMaze(maze, solMaze, yCoord + dir[coords.get(j)][0],
        		xCoord + dir[coords.get(j)][1], path, true);
        if (!tmp.isEmpty()) {
          for (String str1 : tmp) answers.add(str1);
        }
        path = path.substring(0, path.length()-1);
      }
      solMaze[yCoord][xCoord] = 0;
    } else if (coords.size() > 0) {
      path += paths.get(0);
      tmp = ratInAMaze(maze, solMaze, yCoord + dir[coords.get(0)][0],
      			xCoord + dir[coords.get(0)][1], path, false);
      if (!tmp.isEmpty()) {
        for (String str2 : tmp) answers.add(str2);
      }
    }
    solMaze[yCoord][xCoord] = 0;
    return answers;
  }

  public static void main(String[] args) {
      RatInAMaze test = new RatInAMaze();

      ArrayList<String> result = new ArrayList<String>();
      int[][] testMaze = {{1, 1, 1, 1, 1},
                          {1, 0, 1, 0, 1},
                          {1, 0, 1, 0, 1},
                          {1, 1, 1, 1, 1}};

      int[][] resultMaze = new int[testMaze.length][testMaze[0].length];

      result = test.ratInAMaze(testMaze, resultMaze, 0, 0, "", false);

      if (result.isEmpty()) System.out.println(-1);
      else System.out.println(result);
  }
}

Method ratInAMaze() verifies every possible direction and adds to 'coords' arraylist coordinates' indices that are in accordance with dir[][] matrix. 'coords' thus would contain one or more elements at the point after very first for loop in method. Then method is branched depending on with which condition it fits. When there are more than one feasible steps forward, new for loop appears to loop through those possibilities.

 

This algorithm stores the track in a solution maze matrix only if there is one choice possible, not two or more. This prevents from unnecessary track to be formed, that is, two branches emerge simulataneously from one node. This is done by put 'true' or 'false' boolean value as a parameter to 'ratInAMaze' method.