Kites on a zebra crossing: an algorithmic challenge

Forget Sudoku

A couple of moons ago I stumbled across an algorithmic puzzle which I want to share. It is not too simple s.t. an efficient solution can easily be seen but also not too complicated s.t. it is beyond hope of finding a solution in polynomial time – at least not yet or not for me.

So my effort in describing this problem can also be considered as a crowd sourcing attempt in finding a solution and I call you for contribution. The problem is an idealization of a real algorithmic problem I was dealing with but I stripped off some additional complications in order to improve it as a game play.

Let’s go in medias res quickly.

The basic setup is that of a directed acyclic graph which is layered or stratified as depicted in the diagram below.

The “kite on a zebra crossing” diagram

If we enumerate the stripes in ascending order,  a vertex of stripe `i` can be connected with one or more vertices in stripe `i+1`. There is a single vertex in the bottom stripe and the top stripe. Each path from the bottom vertex to the top vertex has the same length and each move upwards is as good as any other.

In order to create a challenge we complicate the situation. For a given positive number K we assign a possibly empty list of numbers with elements in {-K, -K+1, … ,K-1, K} – {0} with each vertex V in the kite. So for example we set `K = 2` and make the assignments

V[0].numlist = []
V[1].numlist = [-1, -2]
V[2].numlist = [-1, -1]
V[3].numlist = [-1]
V[4].numlist = [2]
V[5].numlist = [2]
V[6].numlist = [1]
V[7].numlist = [-2]
V[8].numlist = []

Number lists can assigned to paths of the kite as well. Let `Pt(i, j)` an arbitrary path from `V[i]` to `V[j]`. The number list of `Pt(i,j)` is the concatenation of the number list of its vertices. Examples for such paths and their associated number lists are

Pt(V[0], V[2], V[4], V[7], V[8]).numlist = [-1, -1, 2, -2]
Pt(V[0], V[1], V[4], V[6], V[8]).numlist = [-1, -2, 2, 1]

On number lists we define a reduction rule which states:

Remove adjacent numbers x, y in a number list if x+y = 0

In the number list `[-1, -2, 2, 1]` we can first remove -2 and 2 and get `[-1, 1]` which can be further reduced to `[]`. The number list `[-1, -1, 2, -2]` can be reduced to `[-1, -1]` but not any further.

We write

L1 => L2

if there is a sequence of reductions of the number list `L1` yielding `L2` and say that a complete path `Pt(V[0], V[N])` connecting the bottom with the top of the kite is valid iff  `Pt(V[0], V[N]).numlist =`> `[]`. The number list of a valid path can be reduced to the empty list.

Now the challenge

Assume that K is fixed and let the number N>=2 of kite vertices be variable. So we consider the set of all kites which are constrained by N vertices and this for arbitrary numbers N>=2. Is there an algorithm which can determine a valid path ( or detect its absence ) which is polynomial in N?

This entry was posted in Algorithms. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

*