Combinatorial Problem: Finding N Combinations

As a first problem, Iet's use a very simple problem from combinatorics-- can you find all possible N combinations of items from a set?

In other words, given a set {1, 2, 3, 4, 5} and an N value of 3, we'd be looking for all combinations/subsets of length/size 3. In this case, they would be {1, 2, 3}, {1, 2, 4}, and so on.

Note that the ordering is not important in a combination. so {1, 2, 3} and {3, 2, 1} are considered the same thing.

Let's now look at the pseudo-code for this N-combination problem:

xxxxxxxxxx

routine: combos

input: set

output: display N combinations

assumption: position of the first item is zero and result set is empty at start

​

base case:

1. If all combinations starting with items in positions < (size-N) have been printed. Stop

​

recursive 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

Implementation of Combinatorial Solution

The diagram below shows how this pseudo code works for an input set {1, 2, 3, 4} and N=3.

Notice how the search tree is built from {} (empty set), to {1} to {1, 2} to {1, 2, 3}.

When {1, 2, 3} is found, the algorithm backtracks to {1, 2} to find all combinations starting with {1, 2}. Once that is finished the method backtracks to {1} to find other combinations starting with 1.

In this case, the entire search tree is not stored, but is instead built implicitly. Some paths, where the possibility of finding more combinations is not possible, are abandoned. The method is elegant and its C++ implementation is shown here.

Notice how in the base case 2 of the code, the exploration of combinations stops early on when the index of the set goes above a certain level. So in the tree above, the solutions {3} and {4} won't be explored. This is what makes the algorithm efficient.

xxxxxxxxxx

}

#include <iostream>

#include <vector>

#include <string>

​

using namespace std;

​

// helper: prints the vector

void 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 set

void 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

Combinatorial Problem With A Constraint: Finding N Combinations with Sum < S

Let's now add a constraint to our N combinations problem! The constraint is-- that all sets where sum < S (S being a given parameter) should be printed out.

All we need to do is modify the combosN code, so that all combinations whose sum exceeds S are not explored further, and other such combinations are not generated. Assuming the array is sorted, it becomes even more efficient.

We've illustrated backtracking via arrays to keep things simple. This technique would work really well for unordered linked lists, where random access to elements is not possible.

The tree below shows the abandoned paths {3, 10} and {5, 8}.

xxxxxxxxxx

// sum should be less than target of the argument.  Rest is the same as combosN function

void 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();

    }

}

Enumerating Paths Through a Square Grid

Our next combinatorial problem is that of printing all possible paths from a start location to a target location.

Suppose we have a rectangular grid with a robot placed at some starting cell. It then has to find all possible paths that lead to the target cell. The robot is only allowed to move up or to the right. Thus, the next state is generated by doing either an "up move" or a "right move".

Backtracking comes to our rescue again. Here is the pseudo-code that allows the enumeration of all paths through a square grid:

xxxxxxxxxx

routine: enumeratePaths

input: Grid m*n

output: Display all paths

assumption: result is empty to begin with

​

Base case 1:

1. If target is reached then print the path

Base case 2:

2. If left or right cell is outside the grid then stop

​

Recursive case:

1. Add the current cell to path

2. Invoke enumeratePaths to find all paths that are possible by doing an "up" move

3. Invoke enumeratePaths to find all paths that are possible by doing a "right" move

4. Remove the current cell from path

Square Grid Implementation

To see how the previous pseudo-code works, I have taken an example of a 3x3 grid and shown the left half of the tree. You can see that from each cell there are only two moves possible, i.e., up or right.

The leaf node represents the goal/target cell. Each branch of the tree represents a path. If the goal is found (base case 1), then the path is printed. If instead, base case 2 holds true (i.e., the cell is outside the grid), then the path is abandoned and the algorithm backtracks to find an alternate path.

Note: only a few backtrack moves are shown in the figure. However, after finding the goal cell, the system again backtracks to find other paths. This continues until all paths are exhaustively searched and enumerated.

The code attached is a simple C++ implementation of enumerating all paths through an m * n grid.

xxxxxxxxxx

// helper recursive routine

void 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 user

void enumeratePathsMain(int rows, int cols) {

  vector < int > path;

  enumeratePaths(rows, cols, path, 0, 0);

}

Find Path Through a Maze

We can extend the prior problem to find the path through the maze. You can think of this problem as the grid problem, but with an added constraint. The constraint is this-- that some cells of the maze are not accessible at all, so the robot cannot step into those cells.

Let's call these "inaccessible" cell pits, where the robot is forbidden to enter. The paths that go through these cells should then be abandoned earlier on in "the search". The pseudo-code thus remains the same with one additional base case, which is to stop if the cell is a forbidden cell.

xxxxxxxxxx

routine: enumerateMaze

input: Grid m * n

output: Display all paths

assumption: result is empty to begin with

​

Base case 1:

1. If target is reached then print the path

Base case 2:

2. If left or right cell is outside the maze then stop

Base case 3:

3. If the cell is a pit then stop

​

Recursive case:

1. Add the current cell to path

2. Invoke enumerateMaze to find all paths that are possible by doing an "up" move

3. Invoke enumerateMaze to find all paths that are possible by doing a "right" move

4. Remove the current cell from path

The figure below shows how paths are enumerated through a maze with pits. I have not shown all the backtracking moves, but the ones shown give a fairly good idea of how things are working. Basically, the algorithm backtracks to either a previous cell to find new paths, or backtracks from a pit to find new paths.

The C++ code attached is an implementation of enumerating all paths through a maze, which is represented as a binary 2D array. The main function that we can call is enumerateMazeMain and you can add a function to initialize the maze differently. The main recursive function translated from the above pseudo-code is the enumerateMaze function.

xxxxxxxxxx

// m.enumerateMazeMain();

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();

Solving Sudoku

The last example in this tutorial is coming up with a solution to one of my favorite combinatorial games-- Sudoku-- via backtracking!

Sudoku is a classic example of a problem with constraints, which can be solved via backtracking. It works like magic! To simplify the problem, let's use an easier version of the sudoku game.

We can model the game as an N * N grid, each cell having numbers from 1 .. N.

The rule is not to repeat the same number in a column or row. The initial sudoku board has numbers in some cells, and are empty for the rest. The goal of the game is to fill out the empty cells with numbers from 1 .. N, so that the constraints are satisfied. Let us now look at how backtracking can be used to solve a given Sudoku board.

xxxxxxxxxx

Routine: solve

Input: Sudoku board

Rule: No repetition of a number in the same row or column

Assumption: The initial board configuration is according to Sudoku rules

​

Base case:

1. If all empty places are filled return success

2. If all combinations are tried and the board is invalid, return false

​

Recursive case (returns success or failure):

1. Choose an empty cell

2. 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 valid, 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 2

3. return failure (no possible combination is possible)

Results

It's pretty awesome that we can actually find a solution to Sudoku via a simple backtracking routine. Let's see this routine in action on a simple 4 x 4 board as shown in the figure below. There are three empty cells. We can see that all combinations of numbers are tried.

Once an invalid board configuration is found, the entire branch is abandoned, backtracked, and a new solution is tried. The C++ implementation is provided. You can add your own public function to initialize the board differently.

xxxxxxxxxx

// s.print();

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) {