For k=3 (the generalized KTS problem), we can proceed as follows.

We need to be able to construct the first row in such a way that it guarantees that every pair appears exactly once. We start by assuming that the top-left cell is always [][0,0][1,0] (it is possible to show that any solution can be transformed into a solution in which this is true). The remaining triples will be of 4 types:

1) 3 even symbols

2) 2 even symbols and 1 odd symbol

3) 1 even symbol and 2 odd symbols

4) 3 odd symbols

We may assume that r is always even, and the modulus 3r+1 (for which I will write q) is always odd. Thus, the above example has r=2 and q=7. The next case of interest has r=4 and q=13. (Note that q is also the row count.) Each triple of type 1 (resp. type 4) contains 3 even-even (resp. odd-odd) pairs, while the triples of type 2 (resp. type 3) contain 1 even-even (resp. odd-odd) pair and 2 odd-even pairs. I'll write t1, t2, t3, t4 for the number of triples of each type. There must be 3qr/2 even-even (resp. odd-odd) pairs in all, therefore 3r/2 in each row, including the top row. Thus, 3t1 + t2 = 3t4 + t3 = 3r/2. Similarly, there must be q

^{2} = 3qr+q even-odd pairs in all, therefore 3r+1 in each row including the top row, one of which is in the leftmost triple. Thus, 2t2 + 2t3 = 3r, i.e. t2+t3 = 3r/2. We can derive from this that t1 + t2 + t3 + t4 = 2r, thus t1 + t4 = r/2. Note that t2 and t3 must always be multiples of 3. We can assign t1 arbitrarily to any number in the range 0..r/2, and from this we have t2 = 3(r/2 - t1), t4 = r/2 - t1, t3 = 3t1. It is slightly less confusing to let i be a value in the range 0..r/2, then [t1,t2,t3,t4] = [i,3(r/2-i),3i,r/2-i]. Since this gives the correct number of triples 2r+1 (including the triple on the left), this is a general solution.

If we always take i = r/2, then there will be r/2 triples of type 1 and 3r/2 triples of type t3, and none at all of types 2 or 4. In the r=4 case, writing E1..E12 for the 12 even symbols other than [0,0] and O1..O12 for the 12 odd symbols other than [1,0], we are looking for a top row of the form:

[][0,0][1,0] E1;E2;E3 E4;E5;E6 E7;O1;O12 E8;O2;O11 E9;O3;O10 E10;O4;O9 E11;O5;O8 E12;O6;O7

I'm going to test out one further assumption, namely that Ot = [1,t] for t=1..12, since this is the simplest way of generating all the odd-odd pairs.

Next, I note that 2 is a primitive root mod 13, and if I lay out the powers of 2 mod 13 in the following way:

I note that the differences of the set [1,3,9] are the set [±2,±6,±5], while the differences of the set [2,6,5] are the set [±4,±12,±10] = [±4,±1,±3], so if I use the symbols corresponding to these two sets for E1;E2;E3 and E4;E5;E6, I will get every pair exactly once. This means that the symbols [0,4], [0,12], [0,10], [0,8], [0,11], [0,7] must correspond in some order to E7..E12.

Writing m7..m12 for the m-components of the symbols E7..E12, and with the other assumptions in place, the even-odd differences will be m7±1, m8±2, m9±3, m10±4, m11±5, m12±6, for some permutation m7..m12 of the residues [4,12,10,8,11,7]. If we can find a permutation such that the even-odd differences are a permutation of 1..12, then we will be done. (I don't know if this can be done other than by brute force.) If we change the order of the odd m-components slightly, we can produce the differences 4±1, 12±3, 10±9, 8±2, 11±6, 7±5, which constitute the set [5,3,2,9,6,1,10,6,4,5,12,2]: close -- 5, 6 and 2 appear twice, while 7, 11 and 8 do not appear at all.

The above choices are not as random as the might appear. The set [1,3,9] is the set of cube roots of 1 mod 13. Multiplying by 2, 4, 8 in turn gives the sets [2,6,5], [4,12,10] and [8,11,7]. The set [a,3a,9a] will always be one of these 4 sets. I wanted to arrange the differences in the preceding paragraph so that there would be one difference in each of the 4 sets, but instead I ended up with two copies of [2,6,5] and no copy of [8,11,7]. I think I can fix that: If I choose 4±5 as a seed, then the differences will be 9,12, one of which is in [1,3,9] and the other is in [4,12,10]. Extending this to the remaining values in the set [4,12,10] gives 4±5, 12±2, 10±6, so that the differences are [9,1,3] using the + sign, and [12,10,4] using the - sign. If I then double [4,12,10], I get [8,11,7], which together with [4,12,10] covers the residues m7..m12. Multiplying the whole thing by 2 then gives 8±10, 11±4, 7±12. This uses every required difference needed to generate the odd-odd pairs, and gives the differences [5,2,6] using the + sign, and [11,7,8] using the - sign. The full solution is then:

[][0,0][1,0] | [0,1][0,3][0,9] | [0,2][0,6][0,5] | [0,4][1,9][1,12] | [0,12][1,1][1,10] | [0,10][1,3][1,4] | [0,8][1,5][1,11] | [0,11][1,2][1,7] | [0,7][1,8][1,6] |

[][0,1][1,1] | [0,2][0,4][0,10] | [0,3][0,7][0,6] | [0,5][1,10][1,0] | [0,0][1,2][1,11] | [0,11][1,4][1,5] | [0,9][1,6][1,12] | [0,12][1,3][1,8] | [0,8][1,9][1,7] |

[][0,2][1,2] | [0,3][0,5][0,11] | [0,4][0,8][0,7] | [0,6][1,11][1,1] | [0,1][1,3][1,12] | [0,12][1,5][1,6] | [0,10][1,7][1,0] | [0,0][1,4][1,9] | [0,9][1,10][1,8] |

[][0,3][1,3] | [0,4][0,6][0,12] | [0,5][0,9][0,8] | [0,7][1,12][1,2] | [0,2][1,4][1,0] | [0,0][1,6][1,7] | [0,11][1,8][1,1] | [0,1][1,5][1,10] | [0,10][1,11][1,9] |

[][0,4][1,4] | [0,5][0,7][0,0] | [0,6][0,10][0,9] | [0,8][1,0][1,3] | [0,3][1,5][1,1] | [0,1][1,7][1,8] | [0,12][1,9][1,2] | [0,2][1,6][1,11] | [0,11][1,12][1,10] |

[][0,5][1,5] | [0,6][0,8][0,1] | [0,7][0,11][0,10] | [0,9][1,1][1,4] | [0,4][1,6][1,2] | [0,2][1,8][1,9] | [0,0][1,10][1,3] | [0,3][1,7][1,12] | [0,12][1,0][1,11] |

[][0,6][1,6] | [0,7][0,9][0,2] | [0,8][0,12][0,11] | [0,10][1,2][1,5] | [0,5][1,7][1,3] | [0,3][1,9][1,10] | [0,1][1,11][1,4] | [0,4][1,8][1,0] | [0,0][1,1][1,12] |

[][0,7][1,7] | [0,8][0,10][0,3] | [0,9][0,0][0,12] | [0,11][1,3][1,6] | [0,6][1,8][1,4] | [0,4][1,10][1,11] | [0,2][1,12][1,5] | [0,5][1,9][1,1] | [0,1][1,2][1,0] |

[][0,8][1,8] | [0,9][0,11][0,4] | [0,10][0,1][0,0] | [0,12][1,4][1,7] | [0,7][1,9][1,5] | [0,5][1,11][1,12] | [0,3][1,0][1,6] | [0,6][1,10][1,2] | [0,2][1,3][1,1] |

[][0,9][1,9] | [0,10][0,12][0,5] | [0,11][0,2][0,1] | [0,0][1,5][1,8] | [0,8][1,10][1,6] | [0,6][1,12][1,0] | [0,4][1,1][1,7] | [0,7][1,11][1,3] | [0,3][1,4][1,2] |

[][0,10][1,10] | [0,11][0,0][0,6] | [0,12][0,3][0,2] | [0,1][1,6][1,9] | [0,9][1,11][1,7] | [0,7][1,0][1,1] | [0,5][1,2][1,8] | [0,8][1,12][1,4] | [0,4][1,5][1,3] |

[][0,11][1,11] | [0,12][0,1][0,7] | [0,0][0,4][0,3] | [0,2][1,7][1,10] | [0,10][1,12][1,8] | [0,8][1,1][1,2] | [0,6][1,3][1,9] | [0,9][1,0][1,5] | [0,5][1,6][1,4] |

[][0,12][1,12] | [0,0][0,2][0,8] | [0,1][0,5][0,4] | [0,3][1,8][1,11] | [0,11][1,0][1,9] | [0,9][1,2][1,3] | [0,7][1,4][1,10] | [0,10][1,1][1,6] | [0,6][1,7][1,5] |

This gives us a CHM with [r,k] = [4,3]. I'll try to find a general solution next.