Advertisement
Hydron

Version 2

Apr 18th, 2022
982
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.87 KB | None | 0 0
  1. from typing import List
  2. from typing import Set
  3.  
  4. from sqlalchemy import true
  5.  
  6. def f(cnt: List[int], s: Set[int], pos: int, res_matrix: List[int], n: int) -> bool:
  7.     if pos >= n*n:
  8.         for i in range(0, n):
  9.             dif_row = 0
  10.             for j in range(0, n):
  11.                 if (j % 2 == 0):
  12.                     dif_row += res_matrix[i*n+j]
  13.                 else:
  14.                     dif_row -= res_matrix[i*n+j]
  15.             if dif_row % 11 != 0:
  16.                 return False
  17.         for j in range(0, n):
  18.             dif_col = 0
  19.             for i in range(0, n):
  20.                 if (i%2 == 0):
  21.                     dif_col += res_matrix[i*n+j]
  22.                 else:
  23.                     dif_col -= res_matrix[i*n+j]
  24.             if dif_col % 11 != 0:
  25.                 return False
  26.         for i in range(0, n):
  27.             for j in range(0, n):
  28.                 print(res_matrix[i*n+j], end=' ')
  29.             print()
  30.         return True
  31.     else:
  32.         if (pos+1) % n == 0:
  33.             dif = 0
  34.             for j in range(1, n):
  35.                 if j%2 == 0:
  36.                     dif += res_matrix[pos - j]
  37.                 else:
  38.                     dif -= res_matrix[pos - j]
  39.             if (-dif) in s:
  40.                 cnt[-dif] -= 1
  41.                 if cnt[-dif] == 0:
  42.                     s.remove(-dif)
  43.                 res_matrix[pos] = -dif
  44.                 if f(cnt, s,  pos+1, res_matrix, n) == True:
  45.                     return True
  46.                 cnt[-dif] += 1
  47.                 if cnt[-dif] == 1:
  48.                     s.add(-dif)
  49.         else:
  50.             if n*n - pos <= n:
  51.                 dif = 0
  52.                 for j in range(1, n):
  53.                     if j%2 == 0:
  54.                         dif += res_matrix[pos - n*j]
  55.                     else:
  56.                         dif -= res_matrix[pos - n*j]
  57.                 if (-dif) in s:
  58.                     cnt[-dif] -= 1
  59.                     if cnt[-dif] == 0:
  60.                         s.remove(-dif)
  61.                     res_matrix[pos] = -dif
  62.                     if f(cnt, s,  pos+1, res_matrix, n) == True:
  63.                         return True
  64.                     cnt[-dif] += 1
  65.                     if cnt[-dif] == 1:
  66.                         s.add(-dif)
  67.             else:
  68.                 for i in s:
  69.                     res_matrix[pos] = i
  70.                     cnt[i] -= 1
  71.                     if cnt[i] == 0:
  72.                         s.remove(i)
  73.                     if f(cnt, s, pos+1, res_matrix, n):
  74.                             return True
  75.                     cnt[i] += 1
  76.                     if cnt[i] == 1:
  77.                         s.add(i)
  78.         return False
  79.  
  80. n = int(input())
  81. a = list(map(int, input().split()))
  82.  
  83. cnt = [0] * 10
  84. s = set()
  85. for i in a:
  86.     if cnt[i] == 0:
  87.         s.add(i)
  88.     cnt[i] += 1
  89.  
  90. if not f(cnt, s, 0, [0]*(n*n), n):
  91.     print("Opps, looks like it's impossible :(")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement