BacktrackingSlide 2Solving a mazeColoring a mapSolving a puzzleBacktracking (animation)Terminology ITerminology IIReal and virtual treesThe backtracking algorithmFull example: Map coloringData structuresCreating the mapSetting the initial colorsThe main programThe backtracking methodChecking if a color can be usedPrinting the resultsRecapThe EndBacktracking2BacktrackingSuppose you have to make a series of decisi ons, among various choices, whereYou don’t have enough information to know what to chooseEach decision leads to a new set of choicesSome sequence of choices (possibly more than one) may be a solution to your problemBacktracking is a methodical way of trying out various sequences of decisions, until you find one that “works”3Solving a mazeGiven a maze, find a path from start to finishAt each intersection, you have to decide between three or fewer choices:Go straightGo leftGo rightYou don’t have enough information to choose correctlyEach choice leads to another set of choicesOne or more sequences of choices may (or may not) lead to a solutionMany types of maze problem can be solved with backtracking4Coloring a mapYou wish to color a map withnot more than four colorsred, yellow, green, blueAdjacent countries must be indifferent colorsYou don’t have enough information to choose colorsEach choice leads to another set of choicesOne or more sequences of choices may (or may not) lead to a solutionMany coloring problems can be solved with backtracking5Solving a puzzleIn this puzzle, all holes but oneare filled with white pegsYou can jump over one pegwith anotherJumped pegs are removedThe object is to remove allbut the last pegYou don’t have enough information to jump correctlyEach choice leads to another set of choicesOne or more sequences of choices may (or may not) lead to a solutionMany kinds of puzzle can be solved with backtracking6Backtracking (animation)start ??dead enddead end??dead enddead end?success!dead end7Terminology IThere are three kinds of nodes:A tree is composed of nodesThe (one) root nodeInternal nodesLeaf nodesBacktracki ng can be thought of as searching a tree for a particular “goal” leaf node8Terminology IIEach non-leaf node in a tree is a parent of one or more other nodes (its children)Each node in the tree, other than the root, has exactly one parentparentchildrenparentchildrenUsually, however, we draw our trees downward, with the root at the top9Real and virtual treesThere is a type of data structure called a treeBut we are not using it hereIf we diagram the sequence of choices we make, the diagram looks like a treeIn fact, we did just this a couple of slides agoOur backtracking algorithm “sweeps out a tree” in “problem space”10The backtracking algorithmBacktracking is really quite simple--we “explore” each node, as follows:To “explore” node N: 1. If N is a goal node, return “success” 2. If N is a leaf node, return “failure” 3. For each child C of N, 3.1. Explore C 3.1.1. If C was successful, return “success” 4. Return “failure”11Full example: Map coloringThe Four Color Theorem states that any map on a plane can be colored with no more than four colors, so that no two countries with a common border are the same colorFor most maps, finding a legal coloring is easyFor some maps, it can be fairly difficult to find a legal coloringWe will develop a complete Java program to solve this problem12Data structuresWe need a data structure that is easy to work with, and supports:Setting a color for each countryFor each country, finding all adjacent countriesWe can do this with two arraysAn array of “colors”, where countryColor[i] is the color of the ith countryA ragged array of adjacent countries, where map[i][j] is the jth country adjacent to country iExample: map[5][3]==8 means the 3th country adjacent to country 5 is country 813Creating the map0 142365int map[][];void createMap() { map = new int[7][]; map[0] = new int[] { 1, 4, 2, 5 }; map[1] = new int[] { 0, 4, 6, 5 }; map[2] = new int[] { 0, 4, 3, 6, 5 }; map[3] = new int[] { 2, 4, 6 }; map[4] = new int[] { 0, 1, 6, 3, 2 }; map[5] = new int[] { 2, 6, 1, 0 }; map[6] = new int[] { 2, 3, 4, 1, 5 };}14Setting the initial colorsstatic final int NONE = 0;static final int RED = 1;static final int YELLOW = 2;static final int GREEN = 3;static final int BLUE = 4;int mapColors[] = { NONE, NONE, NONE, NONE, NONE, NONE, NONE };15The main program (The name of the enclosing class is ColoredMap) public static void main(String args[]) { ColoredMap m = new ColoredMap(); m.createMap(); boolean result = m.explore(0, RED); System.out.println(result); m.printMap(); }16The backtracking method boolean explore(int country, int color) { if (country >= map.length) return true; if (okToColor(country, color)) { mapColors[country] = color; for (int i = RED; i <= BLUE; i++) { if (explore(country + 1, i)) return true; } } return false; }17Checking if a color can be used boolean okToColor(int country, int color) { for (int i = 0; i < map[country].length; i++) { int ithAdjCountry = map[country][i]; if (mapColors[ithAdjCountry] == color) { return false; } } return true; }18Printing the results void printMap() { for (int i = 0; i < mapColors.length; i++) { System.out.print("map[" + i + "] is "); switch (mapColors[i]) { case NONE: System.out.println("none"); break; case RED: System.out.println("red"); break; case YELLOW: System.out.println("yellow"); break; case GREEN: System.out.println("green"); break; case BLUE: System.out.println("blue"); break; } }}19RecapWe went through all the countries recursively, starting with country zeroAt each country we had to decide a colorIt had to be different from all adjacent countriesIf we could not find a legal color, we reported failureIf we could find a color, we used it and recurred with the next countryIf we ran out of countries (colored them all), we reported successWhen we returned from the topmost call, we were done20The
View Full Document