backtrack_q.py

xs = [
  [0, 0, 1, 0, []],
  [0, 2, 2, 0, []],
  [0, 5, 1, 0, []],
  [1, 3, 2, 0, []],
  [1, 6, 2, 0, []],
  [2, 0, 3, 0, []],
  [2, 2, 2, 0, []],
  [2, 4, 2, 0, []],
  [3, 1, 1, 0, []],
  [3, 3, 3, 0, []],
  [4, 4, 5, 0, []],
  [4, 6, 2, 0, []],
  [5, 0, 2, 0, []],
  [5, 3, 2, 0, []],
  [6, 1, 1, 0, []],
  [6, 4, 4, 0, []],
  [6, 6, 1, 0, []]
]

def find_pairs(xs):
  n = len(xs)
  for i in range(n):
    xi, yi, _, _, ni = xs[i]
    for j in range(i + 1, n):
      xj, yj, _, _, nj = xs[j]
      if xi == xj:
        ya = min(yi, yj)
        yb = max(yi, yj)
        if all(x != xi or y < ya or yb < y for k, (x, y, _, _, _) in enumerate(xs) if k != i and k != j):
          ni.append(j)
          nj.append(i)
      elif yi == yj:
        xa = min(xi, xj)
        xb = max(xi, xj)
        if all(y != yi or x < xa or xb < x for k, (x, y, _, _, _) in enumerate(xs) if k != i and k != j):
          ni.append(j)
          nj.append(i)

_edges = {}

def edges(i, j, n):
  k = (min(i, j), max(i, j))
  _edges[k] = _edges.get(k, 0) + n

def is_fully_connected(edges, Z):
  visited = set()
  pending = {edges[0][0]}
  while pending:
    z = pending.pop()
    if z not in visited:
      visited.add(z)
      for a, b in edges:
        if a == z:
          pending.add(b)
        elif b == z:
          pending.add(a)
  return len(visited) == Z

def find_solution(xs, k):
  if k == len(xs):
    if all(a == b for (_, _, a, b, _) in xs):
      graph = [k for k, v in _edges.items() if v > 0]
      if is_fully_connected(graph, len(xs)):
        print("== solution found ==")
        for n in [(k, v) for k, v in _edges.items() if v > 0]:
          print(n)
  else:
    pendingEdges = xs[k][2] - xs[k][3]
    find_solution_distribute(xs, k, xs[k][4], 0, pendingEdges)

def find_solution_distribute(xs, k, v, j, n):
  J = xs[v[j]]
  if j == len(v) - 1:
    if J[2] - J[3] >= n:
      J[3] += n
      xs[k][3] += n
      edges(k, v[j], n)
      find_solution(xs, k + 1)
      J[3] -= n
      xs[k][3] -= n
      edges(k, v[j], -n)
  else:
    for t in range(min(n, J[2] - J[3]) + 1):
      J[3] += t
      xs[k][3] += t
      edges(k, v[j], t)
      find_solution_distribute(xs, k, v, j + 1, n - t)
      J[3] -= t
      xs[k][3] -= t
      edges(k, v[j], -t)

find_pairs(xs)
find_solution(xs, 0)

#   == solution found ==
#   ((0, 5), 1)
#   ((1, 2), 1)
#   ((1, 6), 1)
#   ((3, 4), 1)
#   ((3, 9), 1)
#   ((4, 11), 1)
#   ((5, 6), 1)
#   ((5, 12), 1)
#   ((7, 10), 2)
#   ((8, 9), 1)
#   ((9, 13), 1)
#   ((10, 11), 1)
#   ((10, 15), 2)
#   ((12, 13), 1)
#   ((14, 15), 1)
#   ((15, 16), 1)