Guidance through the labyrinth

by Raumpfleger

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.

 

Advertisements