Zahlenteppiche

Matrices with gapless partial sums of permuted integer rows

Category: Labyrinth algorithm

Labyrinth restricted

The previous post described the restriction given by partial sums – depicted by red points – which appear on exactly one row. Looking at these pictures, one sees, that there must be done more: Because of the type of the matrix also the partial sums of one row have to avoid the mandatory (green) points of all other rows. For the time being this has been implemented for the upper – right hand side – mandatory points. This is visible by the fact, that no longer any cyan colored point is in the same vertical with a green point on the right hand side.

The former example for Z = 10 looks now as follows

Z = 10, partial sums with restrictions applied

Z = 10, partial sums with restrictions applied

whereas the former example for Z = 22 looks now so:

Z = 22, partial sums with restrictions applied

Z = 22, partial sums with restrictions applied

Interestingly, a red point on row 18 remains without cyan filling, which means that this point cannot be reached if the restrictions from green points on the right hand side are respected. By the way, the restriction implementation is for the sake of simplicity currently a bit too prohibitive.

Finally let’s also look at the Z = 30 example

Z = 30, partial sums with restrictions applied

Z = 30, partial sums with restrictions applied

What remains to do? On the left hand side there are still cyan points in the same vertical with green points. These restrictions must be implemented too.

So, progress is slow, but not zero.

Advertisements

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

Why?

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

psZ10

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

psZ22

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

psZ30

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.