python - Possible ways to draw n diagonals in an mxm square such that they do not touch each other

Question

I'm trying to write the code to draw n diagonals in an m by m square such that they do not touch each other.

For example, for m=2 and n=3:

I tried to approach it by creating a list of pairs of points by generating the permutations and checking the solution before proceeding. Therefore, I have (m+1)*(m+1) points that create the cells of an m by m square.

def dist(a,b):
  return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**.5

def can_be_extended_to_solution(perm):
  i = len(perm) - 1
  for j in range(i):
    for k in range(2):
      for l in range(2):
        if dist(perm[i][k],perm[j][l]) == 0:
          return False
  return True


def diagonal(perm,n,m):
  if len(perm)==n:
    print(perm)
    return
    

  temp =[]
  for k in range(m):
    for i in range(m):
      if [k,i] not in perm:
        for j in [+1,-1]:
          if [k+j,i+j] not in perm and (k+j<m and i+j<m) and (0<k+j and 0<i+j):
            temp = [[k,i],[k+j,i+j]]
            perm.append(temp)

            if can_be_extended_to_solution(perm):
              diagonal(perm,n,m)
            perm.pop()
m=2
n=3

diagonal([],m+1,n)

The output:

The code works and I'm getting the expected result. However, it's very slow. I'm trying to learn to improve my coding skills and do it more efficiently. So, I'd appreciate it if someone reviews my code and tells me what I can do better and what mistakes I'm making. I see that I have many loops and that's the reason for the slow speed, but I can't figure out any other way to implement those loops or avoid them.

Answer 1

Unique Diagonals

An algorithmic map of the unique diagonals

Probably, the code can improve if you try using the algorithm based on this pattern. I am using 1 as positive diagonal, -1 as negative (slope=-45deg) diagonal.

My impression on the pattern is that based on the starting cell and neighbouring cells will get selected based on this.

I may update this answer with some code if possible. Does this help?
More inputs may help. let me know.

---