Doofish Matrix -- Graph approach

I have tried using the Edge coloring of a complete graph.

This problem turns into one of the special cases ( The case [r=2] ) of Baranyai’s theorem.

As it can be proved that there’s no solution for odd (N > 1), this problem comes into “class one” graphs according to Vizing’s theorem . I have tried to implement it in O(N^2) but sadly didn’t succeed. Has anyone approached this problem using Graphs and came up with an efficient solution?

For example

consider N = 6

As we need 2N -1 groups

(i > j) --> (N-1)

(i = j) -- > 1

(i < j) --> (N-1)

and the (i < j) part of the matrix is

(1,2)(1,3)(1,4)(1,5)(1,6)

(2,3)(2,4)(2,5)(2,6)

(3,4)(3,5)(3,6)

(4,5)(4,6)

(5,6)

Consider a graph with 6 vertices and above 15 pairs as edges (complete graph ) we need to divide these 15 pairs into 5 (N -1) groups (coloring) such that all 6 numbers occur in each group.

5 - coloring

 (1,2) (3,4) (5,6)
 (1,3) (2,5) (4,6)
 (1,4) (2,6) (3,5)
 (1,5) (2,4) (3,6)
 (1,6) (2,3) (4,5)
3 Likes

I think you are looking for Round-Robin Tournaments.

3 Likes

exactly, this might be the author’s intention.

1 Like

Turned into an Ad Hoc :disappointed_relieved: