What is Brute Force Modeling?

Brute Force Modeling is a technique used to solve problems by tabulating results in hopes of finding a pattern by induction. The pattern or formula is then normally used as the basis for solving the problem thru iteration or recursion.

Let's take the Josephus Problem, where he (Josephus) and 40 other soldiers decided to choose mass suicide over capture by arranging themselves in a circle and killing the kth person in the circle. The problem of Josephus is where to sit in the circle such that he is the last to die (or escape).

This problem can be easily solved in programming thru a Circular Linked List.

• Initialize the Circular Linked List from 1 to N, where N is the number of soldiers + Josephus.
• Every kth node in the list will be deleted.
• The last remaining node is where Josephus should be seated.

The program in C++ below shows how this is implemented the way the problem is described:

#define N 41
#define K 3

struct Node
{
    int n;
    Node* next;
};

int josephusCList(int n, int k)
{
    Node* u, * t;
    int i, l;

    // Initialize 
    t = new Node; t->next = t; t->n = 1; u = t;
    
    for (i = 2; i <= n; i++)
    {
        t->next = new Node;
        t->next->n = i; t->next->next = u; t = t->next;
    }

    // At this point head = t->next
    while (t != t->next)
    {
        for (i = 1; i < k; i++) t = t->next;
        u = t->next; t->next = u->next;
        delete u;
    }

    l = t->n;
    delete t;

    return  l;
}

The solution above has a Time and Space Complexity of O(N). But we may be able to do better if we can find a pattern thru Brute Force Modeling.

Tabulating the results of our program for every N from 1 to 10 and K from 1 to 10 gives us the following results:

N/K  1  2  3  4  5  6  7  8  9 10
  1  1  1  1  1  1  1  1  1  1  1
  2  2  1  2  1  2  1  2  1  2  1
  3  3  3  2  2  1  1  3  3  2  2
  4  4  1  1  2  2  3  2  3  3  4
  5  5  3  4  1  2  4  4  1  2  4
  6  6  5  1  5  1  4  5  3  5  2
  7  7  7  4  2  6  3  5  4  7  5
  8  8  1  7  6  3  1  4  4  8  7
  9  9  3  1  1  8  7  2  3  8  8
 10 10  5  4  5  3  3  9  1  7  8
 

The following program in C++ generates the table representation above:

int main()
{
    int k, n;

    std::cout << std::setw(3) << "N/K";
    for (k = 1; k <= 10; k++)
        std::cout << std::setw(3) << std::right << k;
    std::cout << "\n";

    for (n = 1; n <= 10; n++)
    {
        std::cout << std::setw(3) << std::right << n;
        for (k = 1; k <= 10; k++)
            std::cout << std::setw(3) << std::right << josephusCList(n, k);

        std::cout << "\n";
    }

    return 0;
}

The Time Complexity for the Brute Force Model is O(N²), where N = K. But time and space complexity shouldn't matter much in this undertaking because we only need the result for visualization purposes!

Although this article is about generating and tabulating data, we must also give justice to the pattern we can find by using simple observation and induction.

By observation, we can write a Recurrence Relation that describes f (n, k) sequence from f (n₁, k), f (n₂, k), ..., to f (n₁₀, k). Recurrence Relation is an equation that describes each element as a function of the preceding ones.

• Given, the definition of the recurrence relation, let's observe the function f (n, k) using the initial values n = 1, k = 2, or simply f (1, 2).

  The result of f (1, 2), or for any values of k always equal to 1, thus we can say f (1, k) = 1.
   

• At glance we can see, f (2, 2) = f (1, k) + 2 % 2; However, our formula needs some modification as 2 % 2 results to 0, but the result should wrap around. So, our workaround is to deduct 1 from k, then add it back after performing the modulo function: ( f (1, 2) + 2 - 1 ) % 2 + 1

  We can generalize our observation of f (n, k) to ( f (n - 1, k) + k - 1 ) % 2 + 1

The following is the recursive implementation of Josephus Problem, let's call it josephusRecursive() function.

int josephusRecursive(int n, int k)
{
    return n == 1 ? 1 : (k + josephusRecursive(n - 1, k) - 1) % n + 1;
}
 

This recursive implementation has a Time Complexity of O(N) and Space Complexity of O(1). The reader might be amused to try and find an iterative solution (a bottom-up approach), with the same Time and Space Complexity to solve the problem.

If you need another example of how Brute Force Modeling can help you solve problems, visit my solution to Lattice Paths - Part 2 (Using Brute Force Modeling and Iteration) here.