Recently I came over an algorithmic problem dealing with arranging blocks of different sizes on a row composed of multiple cells.
One constraint that was specified on the problem was to separate two blocks having the same colour with at least one blank space between them.
To make the problem statement easier to grasp I’ll add some visual examples :
– one row with 5 cells capacity containing one block of 3 cells
0 spaces | block 3 cells | 2 spaces
1 space | block 3 cells | 1 space
2 spaces | block 3 cells | 0 spaces
– one row with 5 cells capacity containing two blocks – first having 2 cells and the second having 1 cell
As it can be seen from the visual representations above, the problem is about finding the combinations of blank cell lengths under which the blocks can be arranged on the row.
in the first example we have to find the combinations under which for the two possible locations (before and after the block) white spaces can be filled :
– 0 2
– 1 1
– 2 0
The count of white spaces to be filled is given by count(row cells) – sum(block cells).
The Java code for solving this problem is attached below :
public class Puzzles {
public void sumSubsets(int target, int elementIndex, int[] partial, List solutions) {
int partialSum = 0;
for (int i = 0;i<elementIndex;i++){
partialSum+=partial[i];
}
if (partialSum <= target) {
if (partial.length == elementIndex + 1) {
partial[partial.length - 1] = (target - partialSum);
solutions.add(Arrays.copyOf(partial, partial.length));
} else {
for (int i = 0; i 0) continue;
partial[elementIndex] = i;
sumSubsets(target, elementIndex+1, partial, solutions);
}
}
}
}
@Test
public void testSumSubsets() {
List solutions = new ArrayList();
Puzzles puzzles = new Puzzles();
puzzles.sumSubsets(2, 0, new int[2], solutions);
for (int[] solution : solutions) {
for (int e : solution) {
System.out.print(e + " ");
}
System.out.println();
}
}
}
This is just a tiny piece of algorithmics that can be used for solving the Puzzles problem described here :
After successfully solving the problem, your algorithm will be able to solve puzzles like the following :
The implementation for the problem can be found here :
A developer's blog 