Theory on Backtracking What is Backtracking

Backtracking is an algorithmic technique for solving problems recursively by:

Building a solution incrementally --- one piece/step at a time.
The algorithm must walk back the previous step during the solution building process
(Hence the name: backtracking)

Backtracking is a form of brute force search algorithm
However:

Backtracking algorithm in pseudo code

void Search( stepNum, currState, stepsToSol[] ) { if ( stepNum >= MAXSTEPS allowed ) return; // Dead end, try next branch if ( currState is a solution ) { print( currState ); // Print solution print( stepsToSol[ ] ); // Print steps to achieve solution if ( you only need 1 solution ) exit(0); else return; // Continue to find other solutions... } // Make a step and search further for ( every legal step S in currState ) { currState = applyStep(S, currState) add S to stepsToSol[] Search( stepNum+1, (new) currState, stepsToSol[] ); // Walk back the previous step when Search returns currState = removeStep(S, currState) remove S from stepsToSol[]; } // Loop back --> try next step S

Backtracking algorithm alternate version

void Search( stepNum, currState, stepsToSol[] ) { if ( stepNum >= MAXSTEPS allowed ) return; // Dead end, try next branch if ( currState is a solution ) { print( currState ); // Print solution print( stepsToSol[ ] ); // Print steps to achieve solution if ( you only need 1 solution ) exit(0); else return; // Continue to find other solutions... } // Make a step and search further for ( every legal step S in currState ) { newState = applyStep(S, currState) add S to stepsToSol[] Search( stepNum+1, newState, stepsToSol[] ); // Walk back the previous step when Search returns ~~currState = removeStep(S, currState)~~ remove S from stepsToSol[]; } // Loop back --> try next step S

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (1) AA --> AB (No match --> fail)

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward)

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB])

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (1) AA --> AB (No match --> fail)

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (2) AB --> BB (No match --> fail)

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward)

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB])

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward)

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB])

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (1) AA --> AB (No match --> fail)

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (2) AB --> BB (Match --> make step forward)

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (2) AB --> BB (Match --> make step forward) currState = BBB s=[2 1 BB, 3 1 AAB, 1 1 ABB, 2 1 BBB] Search( 4, BBB, [2 1 BB, 3 1 AAB, 1 1 ABB, 2 1 BBB])

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (2) AB --> BB (Match --> make step forward) currState = BBB s=[2 1 BB, 3 1 AAB, 1 1 ABB, 2 1 BBB] Search( 4, BBB, [2 1 BB, 3 1 AAB, 1 1 ABB, 2 1 BBB]) stepNum == S --> check if BBB is solution No ---> return

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (2) AB --> BB (Match --> make step forward) currState = BBB s=[2 1 BB, 3 1 AAB, 1 1 ABB, 2 1 BBB] ~~Search( 4, BBB, [2 1 BB, 3 1 AAB, 1 1 ABB, 2 1 BBB])~~ Walk back previous step

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (2) AB --> BB (Match --> make step forward) currState = ABB s=[2 1 BB, 3 1 AAB, 1 1 ABB] ~~Search( 4, BBB, [2 1 BB, 3 1 AAB, 1 1 ABB, 2 1 BBB])~~ Walk back previous step

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (2) AB --> BB (Match --> make step forward) currState = ABB s=[2 1 BB, 3 1 AAB, 1 1 ABB] ~~Search( 4, BBB, [2 1 BB, 3 1 AAB, 1 1 ABB, 2 1 BBB])~~ Walk back previous step Try next option !

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (3) B --> AA (Match --> make step forward)

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (3) B --> AA (Match --> make step forward) currState = AAAB s=[2 1 BB, 3 1 AAB, 1 1 ABB, 3 2 AAAB] Search( 4, AAAB, [2 1 BB, 3 1 AAB, 1 1 ABB, 3 2 AAAB])

Backtracking algorithm on the pattern generation problem

Sample input: (1) AA --> AB S = 4 (2) AB --> BB Init = AB (3) B --> AA Final = AAAB Search( 0, AB, [ ]) // stepNum = 0, currState = AB, stepsToSol = empty (2) AB --> BB (Match --> make step forward) currState = BB stepsToSol = [2 1 BB] Search( 1, BB, [2 1 BB]) (3) B --> AA (Match --> make step forward) currState = AAB stepsToSol = [2 1 BB, 3 1 AAB] Search( 2, AAB, [2 1 BB, 3 1 AAB]) (1) AA --> AB (Match --> make step forward) currState = ABB stepsToSol = [2 1 BB, 3 1 AAB, 1 1 ABB] Search( 3, ABB, [2 1 BB, 3 1 AAB, 1 1 ABB]) (3) B --> AA (Match --> make step forward) currState = AAAB s=[2 1 BB, 3 1 AAB, 1 1 ABB, 3 2 AAAB] Search( 4, AAAB, [2 1 BB, 3 1 AAB, 1 1 ABB, 3 2 AAAB]) stepNum == S ---> Check for solution AAAB == Final ! DONE

J5 solution Data representation

Data representation:

string src[3], dest[3]; // translation rules // src[0] --> dest[0] // src[1] --> dest[1] // src[2] --> dest[2] int S; // Stop length string Init, Final; // Initial and Final string vector<string> steps; // steps[0] = first step (e.g.: "2 1 BB") // steps[1] = 2nd step (e.g.: "3 1 AAB")

J5 solution Algorithm in pseudo code

Algorithm in pseudo code:

void Search(int nSteps, string currStr, vector steps) { if ( nSteps == S ) { if ( currStr == Final ) { print steps; exit; // Done, we only need to final one solution } else return; // Continue the search } for ( each re-write rule R: src-->dest ) do { for ( each position j = 0 ... currStr.size()-src.size()+1 ) { if ( src found at position j in currStr ) { Make step: src-->dest; Search( nSteps+1, newCurrStr, steps[] + (j+1 R newCurrStr ); Remove step: src-->dest; } } } }

J5 solution Algorithm in C++

Algorithm in C++: (CCC/2019/j5.cc)

void search(int nSteps, string currStr, vector steps) { if ( nSteps == S ) { if ( currStr == Final ) { // FOUND vector::iterator it; for (it=steps.begin(); it != steps.end(); it++) cout<< *it << endl; cout << endl; exit(0); // return; } else return; // No solution, go back and BACKTRACK } for ( int i = 0; i < 3; i++ ) //Apply each rule { for ( int j = 0; j < currStr.size()-src[i].size()+1; j++ ) { if ( currStr.substr(j, src[i].size()) == src[i] ) { // Walk forward 1 step // ** Instead of walk back currStr, I use a new state... string newStr = currStr.substr(0, j) + dest[i] + currStr.substr(j + src[i].size()); steps.push_back(to_string(i+1) + " " // They start counting at 1 + to_string(j+1) + " " + newStr); search(nSteps+1, newStr, steps); // Recurse and search further // Walk back the last step steps.pop_back(); // ** I only need to walk back "steps" } } } }