Recursive Backtracking For Combinatorial, Path Finding, and Sudoku Solver Algorithms

routine: combosinput: setoutput: display N combinationsassumption: position of the first item is zero and result set is empty at startbase case:1. If all combinations starting with items in positions < (size-N) have been printed. Stoprecursive case:Combos(set,result)1. Repeat for each items i in the set:    a. Put the item i in the result set    b. if the result set has N items, display it        else        recursively call combos with (the input set without item i) and (the result set)    c. Remove the item i from result set

#include <iostream>#include <vector>#include <string>using namespace std;// helper: prints the vectorvoid printVector(vector<int>& arr){    cout << "\n";    for (int i = 0; i < arr.size(); ++i)        cout << arr[i] << " ";    cout << "\n";}// helper function:// prints all possible combinations of N numbers from a setvoid combosN(vector<int>& set, int N, vector<int>& result, int ind){    // base case 1    if (ind >= set.size())        return;    // base case 2    if (result.size() == 0 && ind > set.size() - N)        return;    for (int i = ind; i < set.size(); ++i) {        result.push_back(set[i]);        if (result.size() == N)            printVector(result); // print the result and don't go further        else // recursive case            combosN(set, N, result, i + 1);        result.pop_back();    }}// To be called by user: all possible combinations of N numbers from a setvoid combosN(vector<int>& set, int N){    vector<int> result;    combosN(set, N, result, 0);}int main() {  vector<int> v = {1, 2, 3, 4};  combosN(v, 3);}

// sum should be less than target of the argument.  Rest is the same as combosN functionvoid combosNConstraint(vector<int>& arr, vector<int>& subsets, int ind, int target){    if (ind == arr.size())        return;    for (int i = ind; i < arr.size(); ++i) {        subsets.push_back(arr[i]);        // do a recursive call only if constraint is satisfied        if (sum(subsets) <= target) {            printVector(subsets);            combosNConstraint(arr, subsets, i + 1, target);        }        subsets.pop_back();    }}

routine: enumeratePathsinput: Grid m*noutput: Display all pathsassumption: result is empty to begin withBase case 1:1. If target is reached then print the pathBase case 2:2. If left or right cell is outside the grid then stopRecursive case:1. Add the current cell to path2. Invoke enumeratePaths to find all paths that are possible by doing an "up" move3. Invoke enumeratePaths to find all paths that are possible by doing a "right" move4. Remove the current cell from path

// helper recursive routinevoid enumeratePaths(int rows, int cols, vector < int > & path, int r, int c) {  path.push_back(c + cols * r);  // base case 1  if (r == rows - 1 && c == cols - 1) {    printVector(path);    return;  }  // base case 2  if (r >= rows) // out of bound. do nothing    return;  // base case 2  if (c >= cols) // out of bound. do nothing    return;  // row up  enumeratePaths(rows, cols, path, r + 1, c);  // backtrack  path.pop_back();  // column right  enumeratePaths(rows, cols, path, r, c + 1);  path.pop_back();}// to be called by uservoid enumeratePathsMain(int rows, int cols) {  vector < int > path;  enumeratePaths(rows, cols, path, 0, 0);}

routine: enumerateMazeinput: Grid m * noutput: Display all pathsassumption: result is empty to begin withBase case 1:1. If target is reached then print the pathBase case 2:2. If left or right cell is outside the maze then stopBase case 3:3. If the cell is a pit then stopRecursive case:1. Add the current cell to path2. Invoke enumerateMaze to find all paths that are possible by doing an "up" move3. Invoke enumerateMaze to find all paths that are possible by doing a "right" move4. Remove the current cell from path

class mazeClass {    vector<vector<int> > maze;    void enumerateMaze(vector<int>& path, int r, int c)    {        path.push_back(c + maze.size() * r);        // base case 1        if (r == maze.size() - 1 && c == maze[0].size() - 1) {            printVector(path);            return;        }        // base case 2        if (r >= maze.size()) // out of bound. do nothing            return;        // base case 2        if (c >= maze.size()) // out of bound. do nothing            return;        // base case 3        if (!maze[r][c])            return;        // row up        enumerateMaze(path, r + 1, c);        // backtrack        path.pop_back();        // column right        enumerateMaze(path, r, c + 1);        path.pop_back();    }public:    // set up the maze.  Change arrmaze to define your own    void mazeInitialize()    {        int arrmaze[] = {            1,            1,            1,            1,            1,            0,            1,            1,            1,            0,            0,            1,            1,            1,            1,            1        };        vector<int> temp;        int ind = 0;        for (int i = 0; i < 4; i++) {            temp.clear();            for (int j = 0; j < 4; ++j) {                temp.push_back(arrmaze[ind]);                ind++;            }            maze.push_back(temp);        }    }    // main function to call from outside    void enumerateMazeMain()    {        vector<int> path;        if (maze.size() == 0)            mazeInitialize();        enumerateMaze(path, 0, 0);    }};// to call this function use:// mazeClass m;// m.enumerateMazeMain();

Routine: solveInput: Sudoku boardRule: No repetition of a number in the same row or columnAssumption: The initial board configuration is according to Sudoku rulesBase case:1. If all empty places are filled return success2. If all combinations are tried and the board is invalid, return falseRecursive case (returns success or failure):1. Choose an empty cell2. For each candidate number i in the range 1..N    a. Place the candidate i in the empty cell    b. Check if the board is valid with candidate i.        If the board is valide then        {   i. result = invoke the solve routine on the next empty cell            ii. If result is true then stop and return success        }        else            Continue with the next candidate as given in step 23. return failure (no possible combination is possible)

class sudoku {    vector<vector<int> > board;    void Initialize()    {        int arrBoard[] = {            2,            1,            3,            4,            1,            3,            -1,            2,            -1,            2,            -1,            3,            -1,            -1,            2,            1        };        vector<int> temp;        int ind = 0;        for (int i = 0; i < 4; i++) {            temp.clear();            for (int j = 0; j < 4; ++j) {                temp.push_back(arrBoard[ind]);                ind++;            }            board.push_back(temp);        }    }    // set (r,c) to (0,-1) when calling first time    // will search for the next empty slot row wise    bool findNextEmpty(int& r, int& c)    {        int initj = 0;        int initi = 0;        bool found = false;        // start searching from next position        if (c == board[0].size()) {            initi = r + 1;            c = 0;        }        for (int i = r; i < board.size() && !found; ++i) {            if (i == r)                initj = c + 1;            else                initj = 0;            for (int j = initj; j < board[i].size() && !found; ++j) {                if (board[i][j] == -1) {                    r = i;                    c = j;                    found = true;                }            }        }        return found;    }    // check if the number candidate valid at cell (r,c)    bool checkValid(int candidate, int r, int c)    {        bool valid = true;        // check column        for (int i = 0; i < board.size() && valid; ++i) {            if ((i != r) && (board[i][c] == candidate))                valid = false;        }        // check row        for (int j = 0; j < board[0].size() && valid; ++j) {            if ((j != c) && (board[r][j] == candidate))                valid = false;        }        return valid;    }    // recursive implementation    bool solve(int r, int c)    {        bool success = false;        // base case: no more empty slots        if (!findNextEmpty(r, c))            return true;        // nxn is size of board        int n = board.size();        for (int i = 1; i <= n; ++i) {            board[r][c] = i;            if (checkValid(i, r, c)) {                success = solve(r, c); // solve for next empty slot            }            if (success)                break;            else                board[r][c] = -1; // try the next candidate for same slot        }        return success;    }public:    void print()    {        for (int i = 0; i < board.size(); ++i) {            for (int j = 0; j < board[i].size(); ++j)                cout << board[i][j] << " ";            cout << "\n";        }        cout << "\n";    }public:    bool solve()    {        Initialize();        return solve(0, -1);    }};// how to use:// sudoku s;// s.solve();// s.print();

base case:1. If all combinations starting with items in positions < (size-N) have been printed. Stoprecursive case:Combos(set, result)1. Repeat for each items i in the set:    a. Put the item i in the result set    b. if the result set has N items, display it        else        recursively call combos with (the input set without item i) and (the result set)    c. Remove the item i from result set