All of these problems have to be solved using iterative brute-force algorithms.
Solution should be using for loops:
• for (i=0..N) { . . . }
• for each subset of items { . . . }
• for each permutation of items { . . . }
• etc.
## Problem 1.
The most isolated point: given a set of points on a plane, find a point that is
the furthest from its closest neighbor.
```cpp
// given some std::vector<Point> points
size_t furthest = std::string::npos;
float furthest = 0.f;
for (size_t i = 0; i < points.length; i++) {
const Point& p1 = points[i];
float shortest_distance = std::numeric_limits<f32>::max();
for (size_t j = 0; j < points.length; j++) {
if (i == j) continue;
const Point& p2 = points[j];
Vector2 p1_to_p2 = p2 - p1;
float distance = std::sqrt(p1_to_p2.x * p1_to_p2.x + p1_to_p2.x * p1_to_p2.y);
if (distance < closest_neighbor) {
closest_neighbor = distance;
}
}
if (closest_neighbor < shortest_distance) {
shortest_distance = closest_neighbor;
}
}
```
## Problem 2.
*The knapsack problem*: Given a set of items with weights and values, and
a maximum weight capacity, find the combination of items that maximizes
the total value without exceeding the weight capacity. A more crimial way of
putting it: a thief is trying to maximize the value of items they can steal without
exceeding the weight they can carry. Items cannot be split, they are either taken
or not taken.
## Problem 3.
The satisfiability problem: given boolean formula, determine if there is an
assignment of truth values to the variables that makes it true. Example: `A && ~B` can be made true by setting A to true and B to false. But `A && ~A` can
never be made true.
Another example of unsatisfiable formula is `(A || B) && (~A && ~B)`.
For some formula F(x1, x2, ..., xn), for each permutation of the inputs x1,x2,... evaluate with F and if it is every true, then the formula is can be true.
```
foreach ( inputs_array in allPermutationsOfInputs ) {
if (formula(inputs_array) == true) {
return true;
}
}
return false;
```
## Problem 4.
The [[Magic Square]] problem: given an [[Integer]] $n$, construct an $n\times n$ [[../../../Math/Matrix|Matrix]]
filled with distinct integers from $1$ to $n^2$ such that the sum of the integers in
each row, each column, and both main diagonals are the same.
>[!example]
Examples of
magic squares:
>$
>\begin{align}
> n=3, \sum = 15&: \mat{8&1&6\\3&5&7} \\
> n=4, \sum = 34&: \mat{16&2&3&13\\5&11&10&8\\9&7&6&12\\4&14&15&1} \\
>\end{align}$
iterate through every permutation of matrix M_n\*n until one matches the magic square predicate.
```
foreach (x in permutationsOfNxNMatrices) {
if isMagicSquare(x) {
return true;
}
}
return false
```