fork download
copy 
  1. '''
  2. 0401 PA05
  3. 21800279 Seonyeong Park
  4. Polyomino Puzzle: To find a solution of puzzle for given polyominos
  5. '''
  6. import numpy as np
  7. import math
  8. import copy
  9.  
  10. #input
  11. n = int(input())
  12. blocks = []
  13. count = 0
  14. for i in range(n):
  15.     h,w = [int(x) for x in input().split()]
  16.     blocks.append([(h,w)])
  17.     for j in range(h):
  18.         line = [int(x) for x in input().split()]
  19.         for b in line:
  20.             if b == 1:
  21.                 count+=1
  22.         blocks[i].append(line)
  23.  
  24. def check(c):
  25.     s = math.sqrt(c)
  26.     if s == int(s):
  27.         for block in blocks:
  28.             for line in block[0]:
  29.                 if line > s:
  30.                     return False
  31.         return int(s)
  32.     return False
  33.  
  34. def puzzle(num,ans,row,col):
  35.     b = blocks[num]
  36.     h,w = b[0]
  37.     res = copy.deepcopy(ans)
  38.     for i in range(h):
  39.         for j in range(w):
  40.             if b[i+1][j] == 1:
  41.                 if ans[row+i][col+j] == 0:
  42.                     res[row+i][col+j] = num+1
  43.                 else:
  44.                     return False
  45.     for i in range(side):
  46.         for j in range(side):
  47.             if res[i][j] == 0:
  48.                 return [res, i, j]
  49.     return [res, i, j]
  50.  
  51. def polyomino(pro,ans,num=0,row=0,col=0,put=[],turn=0):
  52.     if len(put) == n:
  53.         return ans
  54.     if turn == n:
  55.         return False
  56.     if num == n: num -= n 
  57.     block = blocks[num]
  58.     if num in put:
  59.         if num == put[-1]:
  60.             ans, row, col = copy.deepcopy(pro[len(put)-1])
  61.             if num == turn:
  62.                 turn +=1
  63.             return polyomino(pro[:-1], ans, num+1,row,col,put[:-1],turn)
  64.         else:
  65.             return polyomino(pro,ans,num+1,row,col,put,turn)
  66.     h,w = block[0]
  67.     if row+h > side:
  68.         return polyomino(pro,ans,num+1,row,col,put,turn)
  69.     else:
  70.         start = 0 if col+1-w <= 0 else col+1-w
  71.         result = puzzle(num,ans,row,start)
  72.         while result == False and start+w < side  :
  73.             start += 1
  74.             result = puzzle(num,ans,row,start)
  75.         if result == False:
  76.             return polyomino(pro,ans,num+1,row,col,put,turn)
  77.         else:
  78.             put.append(num)
  79.             pro.append(result)
  80.             ans, row, col = result
  81.             return polyomino(pro,ans, num+1,row,col,put,turn)
  82.  
  83. #---------------------------------------------------------------------------------#    
  84. side = check(count)        #the side of the panel
  85. if side == False:
  86.     print("No solution possible")
  87. else:
  88.     process = []
  89.     answer = np.zeros([side,side], dtype="i").tolist()
  90.     process.append([copy.deepcopy(answer),0,0])
  91.     answer = polyomino(process,answer)
  92.     if answer == False:
  93.         print("No solution possible")
  94.     else:
  95.         for line in answer:
  96.             print(' '.join(map(str, line)))
  97.  
Success #stdin #stdout 0.2s 27064KB
comments (?)
stdin
copy 
5
2 4
1 1 0 0
1 1 1 1 
2 4
1 0 0 0
1 1 1 1
1 2
1 1
3 3
0 0 1
1 1 1
0 0 1
2 5
1 1 0 0 1
0 1 1 1 1
stdout
copy 
5 5 3 3 5
2 5 5 5 5
2 2 2 2 4
1 1 4 4 4
1 1 1 1 4
https://ideone.com/23CBjy
language:
Python 3 nbc (python 3.7.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!