1  import copy
  2  
  3  import visualizer
  4  import time
  5  
  6  
  7  class Board:
  8      SIZE = 56
  9  
 10      def __init__(self):
 11          self.grid = [[True for _ in range(Board.SIZE)] for _ in range(Board.SIZE)]  # grid[y][x] = True if unoccupied
 12          self.next_free = (0, 0)  # (x, y), the top leftmost free cell
 13          self.space = Board.SIZE * Board.SIZE  # free space on this board
 14  
 15  
 16      ''' Returns True if this piece fits at the top leftmost free space '''
 17      def does_fit(self, piece):
 18          # Ensure this piece fits within the bounds of the board
 19          if self.next_free[0] + piece[0] > Board.SIZE or self.next_free[1] + piece[1] > Board.SIZE:
 20              return False
 21  
 22          # Ensure each cell is free
 23          for w in range(piece[0]):
 24              for h in range(piece[1]):
 25                  if not self.grid[self.next_free[1] + h][self.next_free[0] + w]:
 26                      return False
 27  
 28          return True
 29  
 30  
 31      ''' Inserts this piece at the top leftmost free position
 32          Assumes this piece fits 
 33          Returns the top left of this inserted piece '''
 34      def insert(self, piece):
 35          position = copy.copy(self.next_free)
 36  
 37          # Fill in the cells occupied by this piece
 38          for x in range(piece[0]):
 39              for y in range(piece[1]):
 40                  self.grid[self.next_free[1] + y][self.next_free[0] + x] = False
 41  
 42          # Update top-leftmost free position
 43          updated = False
 44          for y in range(Board.SIZE):
 45              for x in range(Board.SIZE):
 46                  if not updated and self.grid[y][x]:
 47                      self.next_free = (x, y)
 48                      updated = True
 49  
 50  
 51          # Update remaining space
 52          self.space -= piece[0] * piece[1]
 53  
 54          return position
 55  
 56  
 57      ''' Return a copy of this board '''
 58      def copy(self):
 59          copied_board = Board()
 60          copied_board.grid = copy.deepcopy(self.grid)
 61          copied_board.next_free = copy.copy(self.next_free)
 62          copied_board.space = self.space
 63          return copied_board
 64  
 65  
 66  
 67  def get_solution(board, remaining, positions):
 68      visualizer.visualize(positions)
 69  
 70      if board.space == 0:
 71          return positions
 72  
 73      for piece in remaining:
 74          for isRotated in (False, True):
 75              rotated_piece = piece if not isRotated else (piece[1], piece[0])
 76              if board.does_fit(rotated_piece):
 77                  # insert piece into board, remove piece from remaining, append position
 78                  new_board = board.copy()
 79                  new_remaining = copy.deepcopy(remaining)
 80                  position = new_board.insert(rotated_piece)
 81                  new_remaining.remove(piece)
 82                  positions.append((rotated_piece, position))
 83  
 84                  # Get recursive solution
 85                  solution = get_solution(new_board, new_remaining, positions)
 86                  if solution:
 87                      return solution
 88  
 89                  # Revert unsuccessful position addition
 90                  positions.pop()
 91  
 92  
 93  
 94  ''' ======================= Run the Code ======================= '''
 95  visualizer = visualizer.Visualizer()
 96  
 97  all_pieces = [(28, 14), (21, 18), (21, 18), (21, 14), (21, 14), (32, 11), (32, 10), (28, 7), (28, 6), (17, 14), (14, 4), (10, 7)]
 98  board = Board()
 99  print(get_solution(board, all_pieces, []))
100  
101  time.sleep(25)