Matrices with gapless partial sums of permuted integer rows

Month: May, 2014

Labyrinth elaborated

Let’s still muse a bit about the labyrinth the algorithm faces. In this post’s illustrations, green points are as before mandatory, given by the current state of affairs. Black points are possible partial sums without respect to permutations. Cyan point fillings are partial sums appearing to pass the enforced restrictions. As red circles as before point to partial sums which must be reached on that particular row, it is good, that there is no red point without cyan filling. The next good thing is: Only on rows with red circles there are black points without cyan filling left – the restrictions do work, but there are still too few restrictions to be efficient.

Z = 10, restrictions applied

Z = 10, partial sums with restrictions applied

Z = 22, partial sums with restrictions applied

Z = 22, partial sums with restrictions applied

Z = 30, partial sums with restrictions applied

Z = 30, partial sums with restrictions applied

Of course one has to balance between the costs of uneducated searches vs. the costs of strict restriction computations …



Guidance through the labyrinth

The search algorithm takes that continuation which has  no obvious flaw and the most continuation possibilities for the next step. If no continuation can be found, it stores the constellation in order to never take it again  and steps back to take there another continuation which has not yet failed.  This works fine for lower numbers of rows (Z < 20) but fails to be operative for higher numbers of rows (Z > 20).


The point lies in the decision about a flaw of a continuation: On each row one  has the remaining, not yet used numbers and can build all possible partial sums on top of the already distributed numbers. The union of all partial sums from all rows must contain all still missing partial sums in the Z x 2 (Z – 1) matrix. But on each row only one permutation of unused numbers can be realized in the end. How to determine it? One looks for partial sums which appear on exactly one row, they constrain the variety of possible permutations. In the pictures the red points mark a partial sum which appears on exactly one row. The green points mark the maximal partial sum on a row. The black points are all possible partial sums without the need to be consistent with a single permutation. The ordinate shows the row number, the abscissa shows the partial sums. For Z = 10 one sees a picture like


showing 6 constraints on 10 rows, enough to complete the search rather fast, in a few thousand steps. For Z = 22 it looks a bit worse


there are only 3 constraints on 22 rows and in the case of 30 rows one has for example


only 5 constraints which let the algorithm run for millions of steps without finding the right way.

So one has to find more constraints in order to find examples of matrices with row numbers bigger than 20.