thingy

from copy import deepcopy

def interlacing(r1, r2):
  l1 = [v for v in r1 if v not in r2]
  l2 = [v for v in r2 if v not in r1]
  k = len(l1)
  if k<=1:
    return k
  if all(l1[i]<l2[i] for i in range(k)):
    if all(l1[i+1]>l2[i] for i in range(k-1)):
      return k
  if all(l2[i]<l1[i] for i in range(k)):
    if all(l2[i+1]>l1[i] for i in range(k-1)):
      return k
  return -1

def possible_xM(left, xM = [0 for _ in range(10)], pos = 1):
  if pos == 9:
    xM[pos] = left
    s = sum(xM)
    q = sum(x*x for x in xM) - s*s/9
    if q == 2:
      yield xM[:]
  elif pos < 9:
    for i in range(min(left,9)+1):
      xM[pos] = i
      yield from possible_xM(left-i, xM, pos+1)

def gen_helper(M, xM, past_inter3 = False, row = 1):
  Mr0 = M[row-1][0]
  Mr1 = M[row-1][1]
  for a in range(1,10):
    if xM[a] == 0:
      continue
    for b in range(max(a,Mr0)+1,10):
      if xM[b] == 0:
        continue
      for c in range(max(b,Mr1)+1,10):
        if xM[c] == 0:
          continue

        this_row = [a,b,c]

        inter3 = past_inter3
        i = 0
        for r in range(1,row):
          i = interlacing(M[r], this_row)
          if i == -1:
            break
          if i == 3:
            inter3 = True
        if i == -1:
          continue

        xM[a] -= 1
        xM[b] -= 1
        xM[c] -= 1
        M[row] = this_row

        if row == len(M)-1:
          if inter3:
            yield deepcopy(M[1:])
        elif row < len(M)-1:
          yield from gen_helper(M, xM, inter3,row+1)

        xM[a] += 1
        xM[b] += 1
        xM[c] += 1


def generate(m):
  validM = []
  M = [[0,0,0] for _ in range(m+1)]
  for xM in possible_xM(3*m):
    for R in gen_helper(M, xM):
      validM.append(R)
  return validM


all_valid_matrices = generate(5)