import pygame from datetime import date import time from time import strftime class TangramSolver: SCREEN_SIZE = SCREEN_WIDTH,SCREEN_HEIGHT = 800, 480 CELL_SIDE = 80 # Color constants. BLACK = 0, 0, 0 WHITE = 255, 255, 255 DARK_PURPLE = 200, 0, 200 def __init__(self): self.pieces = ( [], [[1, 0, 0], [1, 0, 0], [1, 1, 1]], [[2, 2, 2, 2, 2]], [[3, 0], [3, 0], [3, 0], [3, 3]], [[4, 4, 4], [0, 4, 0], [0, 4, 0]], [[5, 5, 5], [5, 0, 5]], [[6, 0], [6, 6], [6, 6]], [[7, 7, 0], [0, 7, 7], [0, 7, 0]], [[8, 0], [8, 8], [0, 8], [0, 8]], [[9, 0], [9, 0], [9, 9], [9, 0]], [[10, 10, 0], [0, 10, 0], [0, 10, 10]] ) self.text_map = ( " ", "V", "I", "L", "T", "U", "P", "F", "N", "Y", "Z", "+" ) self.color_map = ( (0,0,0), (255, 128, 255), (245, 123, 245), (235, 118, 235), (225, 113, 225), (215, 108, 215), (205, 103, 205), (195, 98, 195), (185, 93, 185), (175, 88, 175), (165, 83, 165) ) self.board = [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 11]] self.calendar = [["JAN", "FEB", "MAR", "APR", "1", "2", "3", "MON", "TUE"], ["MAY", "4", "5", "6", "7", "8", "9", "WED", ""], ["JUN", "10", "11", "12", "13", "31", "15", "THU", ""], ["JUL", "16", "17", "18", "19", "20", "21", "FRI", "SAT"], ["AUG", "22", "23", "24", "25", "26", "27", "", "SUN"], ["SEP", "OCT", "NOV", "DEC", "28", "29", "30", "14", ""]] self.piece_positions = self.gen_piece_positions(self.pieces) self.iterations = 0 self.solutions = [] self.terminate = False self.next_solution = True # Calendar positions. self.num_rows = len(self.calendar) self.num_cols = len(self.calendar[0]) self.x_offset = (self.SCREEN_WIDTH - self.num_cols * self.CELL_SIDE)/2 - 1 self.y_offset = (self.SCREEN_HEIGHT - self.num_rows * self.CELL_SIDE)/2 # Time window positions. self.x_time_off = self.x_offset+self.CELL_SIDE*(self.num_cols-1)+self.x_offset/2+6 self.y_time_off = self.y_offset+self.CELL_SIDE*(self.num_rows-1)+(self.CELL_SIDE/2+self.y_offset)/2+6 self.time_width = self.CELL_SIDE self.time_height = self.CELL_SIDE/2 # Font to use. CALENDAR_CELL_FONT_SIZE = 35 pygame.font.init() self.calendar_cell_font = pygame.font.SysFont('arialbold', CALENDAR_CELL_FONT_SIZE) # Dump the board passed to the console. def dump_board(self, board): for row in board: out_row = [] for cell in row: out_row.append(self.text_map[cell]) print(" ".join(out_row)) print() # Draw the calendar background. def display_calendar(self, screen): # Clear the screen. screen.fill(self.WHITE) # Draw the border. pygame.draw.rect(screen, self.BLACK, (0, 0, self.x_offset, self.SCREEN_HEIGHT)) pygame.draw.rect(screen, self.BLACK, (self.SCREEN_WIDTH-self.x_offset, 0, self.x_offset+1, self.SCREEN_HEIGHT)) pygame.draw.rect(screen, self.BLACK, (0, 0, self.SCREEN_WIDTH, self.y_offset)) pygame.draw.rect(screen, self.BLACK, (0, self.SCREEN_HEIGHT-self.y_offset, self.SCREEN_WIDTH, self.y_offset)) pygame.draw.rect(screen, self.BLACK, (self.SCREEN_WIDTH-self.CELL_SIDE-self.x_offset, self.SCREEN_HEIGHT-self.CELL_SIDE-self.y_offset, self.CELL_SIDE, self.CELL_SIDE)) # Draw the labels. for r in range(self.num_rows): for c in range(self.num_cols): cell_text = self.calendar_cell_font.render(self.calendar[r][c], True, self.BLACK, self.WHITE) cell_text_rect = cell_text.get_rect() cell_text_width = cell_text_rect[2] cell_text_height = cell_text_rect[3] cell_text_x_offset = c*self.CELL_SIDE+(self.CELL_SIDE-cell_text_width)/2+self.x_offset cell_text_y_offset = r*self.CELL_SIDE+(self.CELL_SIDE-cell_text_height)/2+self.y_offset screen.blit(cell_text, (cell_text_x_offset, cell_text_y_offset)) # Draw the tangram pieces and time. def display_pieces(self, screen, board): for r in range(self.num_rows): # Fill in the piece colors. for c in range(self.num_cols): cell_x_offset = c*self.CELL_SIDE+self.x_offset cell_y_offset = r*self.CELL_SIDE+self.y_offset cell_value = board[r][c] # Fill in the tangram piece with the appropriate color. if cell_value > 0 and cell_value < 11: pygame.draw.rect(screen, self.color_map[cell_value], (cell_x_offset, cell_y_offset, self.CELL_SIDE, self.CELL_SIDE)) # Outline the pieces. for c in range(self.num_cols): cell_x_offset = c*self.CELL_SIDE+self.x_offset cell_y_offset = r*self.CELL_SIDE+self.y_offset cell_value = board[r][c] # Outline the tangram pieces. if r == self.num_rows-1 and c == self.num_cols-1: continue if r == 0 or cell_value != board[r-1][c]: pygame.draw.line(screen, self.BLACK, (cell_x_offset, cell_y_offset), (cell_x_offset+self.CELL_SIDE, cell_y_offset), width=2) if r == self.num_rows-1 or cell_value != board[r+1][c]: pygame.draw.line(screen, self.BLACK, (cell_x_offset, cell_y_offset+self.CELL_SIDE), (cell_x_offset+self.CELL_SIDE, cell_y_offset+self.CELL_SIDE), width=2) if c == 0 or cell_value != board[r][c-1]: pygame.draw.line(screen, self.BLACK, (cell_x_offset, cell_y_offset), (cell_x_offset, cell_y_offset+self.CELL_SIDE), width=2) if c == self.num_cols-1 or cell_value != board[r][c+1]: pygame.draw.line(screen, self.BLACK, (cell_x_offset+self.CELL_SIDE, cell_y_offset), (cell_x_offset+self.CELL_SIDE, cell_y_offset+self.CELL_SIDE), width=2) # Show time too. self.display_time(screen) # Display the current time. def display_time(self, screen): # Add the current time. pygame.draw.rect(screen, self.WHITE, (self.x_time_off, self.y_time_off, self.time_width, self.time_height)) pygame.draw.rect(screen, self.BLACK, (self.x_time_off, self.y_time_off, self.time_width, self.time_height), width=2) string_time = strftime("%I:%M") time_text = self.calendar_cell_font.render(string_time, True, self.BLACK, self.WHITE) time_text_rect = time_text.get_rect() time_text_width = time_text_rect[2] time_text_height = time_text_rect[3] time_text_x_offset = (self.time_width-time_text_width)/2 time_text_y_offset = (self.time_height-time_text_height)/2 screen.blit(time_text, (self.x_time_off+time_text_x_offset, self.y_time_off+time_text_y_offset)) @staticmethod def rotate_piece(piece): return [list(row[::-1]) for row in zip(*piece)] def get_rotations(self, piece): unique_rotations = [piece] for _ in range(3): piece = self.rotate_piece(piece) if piece not in unique_rotations: unique_rotations.append(piece) return unique_rotations, len(unique_rotations) @staticmethod def reflect_piece_x(piece): return piece[::-1] @staticmethod def reflect_piece_y(piece): return [row[::-1] for row in piece] def get_all_positions(self, piece): positions, _ = self.get_rotations(piece) if piece == self.pieces[7]: #Only the F can be reflected. for pos in positions: y_reflect = self.reflect_piece_y(pos) x_reflect = self.reflect_piece_x(pos) if y_reflect not in positions: positions.append(y_reflect) if x_reflect not in positions: positions.append(x_reflect) return positions def gen_piece_positions(self, pieces): piece_positions = [] for piece in pieces[1:]: piece_positions.append(self.get_all_positions(piece)) return piece_positions @staticmethod def legal_islands(board): # use bfs to find number of distinct islands board = [[elem for elem in row] for row in board] board_height = len(board) board_width = len(board[0]) island_cells = [] def island_bfs(row, col): cell_queue = [(row, col)] while cell_queue: row, col = cell_queue.pop() if board[row][col] != 0: continue island_cells.append((row, col)) board[row][col] = "#" for row_offset, col_offset in [(1, 0), (-1, 0), (0, 1), (0, -1)]: temp_row = row + row_offset temp_col = col + col_offset if 0 <= temp_row < board_height and 0 <= temp_col < board_width and board[temp_row][temp_col] == 0: cell_queue.append((temp_row, temp_col)) for row in range(board_height): for col in range(board_width): if board[row][col] == 0: island_bfs(row, col) island_size = len(island_cells) if island_size % 5 != 0: return False island_cells = [] return True def add_piece(self, board, piece, start_row, start_col, check_islands=True): piece_width = len(piece[0]) piece_height = len(piece) legal_move = True if (start_row + piece_height > len(board)) or (start_col + piece_width > len(board[0])): legal_move = False return board, legal_move changed_squares = [] for i, row in enumerate(piece): for j, val in enumerate(row): # only add filled spaces, never take away if val: # don't overwrite existing pieces on the board if board[start_row + i][start_col + j]: legal_move = False return board, legal_move else: changed_squares.append((start_row + i, start_col + j, val)) new_board = [[val for val in row] for row in board] for changed_row, changed_col, val in changed_squares: new_board[changed_row][changed_col] = val # check if the move created any illegal islands if check_islands and (not self.legal_islands(new_board)): legal_move = False return board, legal_move return new_board, legal_move def get_legal_squares(self, board, piece, check_islands=True): legal_moves = [] for row in range(len(board)): for col in range(len(board[0])): _, legal_move = self.add_piece(board, piece, row, col, check_islands) if legal_move: legal_moves.append((row, col)) return legal_moves def solve_board(self, screen, board, pieces): self.iterations += 1 if self.terminate: return # WIN condition is whole board is covered in pieces. if all([all(row) for row in board]): self.solutions.append(board) print(f"Solutions: {len(self.solutions):,}") print(f"Iterations: {self.iterations:,}\n") #self.dump_board(board) self.display_pieces(screen, board) pygame.display.flip() #if len(self.solutions) == 3: # self.terminate = True return else: piece_positions = pieces[0] for position in piece_positions: legal_squares = self.get_legal_squares(board, position) for row, col in legal_squares: self.solve_board(screen, self.add_piece(board, position, row, col)[0], pieces[1:]) def run(self): # Initialize the PyGame environment. pygame.init() # Screen constants. infoObject = pygame.display.Info() if infoObject.current_w == 800 and infoObject.current_h == 480: SCREEN_ATTRIBUTES = pygame.NOFRAME+pygame.FULLSCREEN else: SCREEN_ATTRIBUTES = 0 # Set to full screen for a Raspberry Pi 7" display. screen = pygame.display.set_mode(self.SCREEN_SIZE, SCREEN_ATTRIBUTES) pygame.display.set_caption('Calendar Puzzle') # Hide the mouse. pygame.mouse.set_visible(False) current_day = "33" current_solution = 0 while True: # Setup the date in the calendar. today = date.today() day = today.strftime("%d").lstrip("0") if day != current_day: current_day = day weekday = today.strftime("%a").upper() month = today.strftime("%b").upper() date_parts = [day, weekday, month] for r in range(self.num_rows): for c in range(self.num_cols): cal_value = self.calendar[r][c] if cal_value in date_parts: self.board[r][c] = 11 else: self.board[r][c] = 0 self.board[self.num_rows-1][self.num_cols-1] = 11 self.solutions.clear() current_solution = 0 # Show the blank calendar. self.display_calendar(screen) # Show the unsolved calendar. pygame.display.flip() # Solve the puzzle showing each solution. self.solve_board(screen, self.board, self.piece_positions) #print("Solved!\n") # Show the next solution. if self.next_solution: self.display_pieces(screen, self.solutions[current_solution]) current_solution = (current_solution + 1) % len(self.solutions) else: self.display_time(screen) # Update the screen. pygame.display.flip() # Snooze. time.sleep(5) # Check for touch. for event in pygame.event.get(): if event.type == pygame.MOUSEBUTTONDOWN: self.next_solution = not self.next_solution time.sleep(1) elif event.type == pygame.quit: return elif event.type == pygame.KEYDOWN and event.key == pygame.K_ESCAPE: pygame.quit() return if __name__ == "__main__": TangramSolver().run()