CSC236 Data Structures - Recursive Backtracking

Recursive Backtracking

All Possible Dice Rolls

Suppose we want to write a method that will print all possible rolls of k dice.

DiceRoll(2)          DiceRoll(3)
-----------          -----------

[1,1]                [1,1,1]
[1,2]                [1,1,2]
[1,3]                [1,1,3]
[1,4]                [1,1,4]
[1,5]                [1,1,5]
[1,6]                [1,1,6]
[2,1]                [1,2,1]
[2,2]                [1,2,2]
[2,3]                [1,2,3]
  .                     .
  .                     .
  .                     .
[6,4]                [6,6,4]
[6,5]                [6,6,5]
[6,6]                [6,6,6]

This is something like the following:

   for (each possible first die value):
      for (each possible second die value):
         for (each possible third die value):
            print...

This is called depth first search and is often implemented with recursion. It is used frequently in games, like anagrams, word jumbles, and sudoku, for generating permutations, and for navigating a maze. The general idea is:

   explore(choices) {
      if there are no choices
         stop
      else
         make a choice C
         explore remaining choices (recursively)
         undo C if necessary (backtrack)
   }

Solution: All Possible Dice Values

// DiceRoll
//
// prompt for the number of dice
// print all possible rolls for this number of dice
import java.util.Scanner;
import java.util.ArrayList;

public class DiceRoll {
	public static void main(String[] args) {
		Scanner keybd = new Scanner(System.in);
		int numdice;

// prompt for the number of dice then call method to print
		System.out.print("enter the number of dice: ");
		numdice = keybd.nextInt();
		diceRolls(numdice);

	}

// prints all possible outcomes of rolling the given number of six-sided
// dice in [#, #, #] format. each possible outcome is added to an ArrayList
// the toString method of ArrayList is used to generate output
// this method starts the recursion
	public static void diceRolls(int dice) {
		ArrayList chosen = new ArrayList();
		diceRolls(dice, chosen);
	}

// private recursive helper to implement diceRolls logic
	private static void diceRolls(int dice,	ArrayList chosen) {

		// base case: we have a roll for each die so print them
		if (dice == 0) {
			System.out.println(chosen);
		}
		else {
			for (int i = 1; i <= 6; i++) {
				// add current number as roll for current die
				chosen.add(i);
				// recursive call to get rolls for the rest of the dice
				diceRolls(dice - 1, chosen);
				// remove this number so next time through loop we can
				// choose the next number as the roll for this die
				chosen.remove(chosen.size() - 1);
			}
		}
	}
}

To understand how this method works, trace a few steps of it using 3 for the number of dice.

In this problem, every possible solution explored through backtracking is part of the result. In many problems, however, only some of the possible solutions meet the problem requirements. That means that after each solution is generated, it is tested to see if it meets the requirements. If it does, then it becomes part of the result. If not, the program moves on to the next solution.

Dice Rolls That Add To a Given Number

Suppose we want to print all dice rolls that add up to a given number, for example, we want all rolls of 3 dice that add up to 7. To compute this solution we need to generate all rolls of 3 dice, check how much each roll adds up to, and print only those that add up to 7. We need to add a parm for the sum so that we know what value to check for when we add up the numbers in the roll.

In the previous problem we printed every roll. Look at that code and think about what needs to be changed to only print the rolls that add up to the given sum.

How to Approach a Backtracking Problem

Here are the things you need to think about when solving a backtracking problem:

What are the "choices" in this problem?
How do I tell when there are no more choices? This is the "base case". What actions need to be taken when there are no more choices?
How do I "make" a choice? Do I need to create additional variables to remember the choices I've made? Do I need to modify the values of existing variables?
How do I move on to the other choices? Do I need to backtrack from the current choice? When I backtrack is there anything I need to undo? Any variables that I need to change?