Anyone who enjoys doing puzzles will surely love starting their day with one and this one has the advantage of being different every day! It consists of a 7×7 grid where 12 cells contain the month and 31 cells contain the day, making up 43 cells in total.
Then there are 8 tiles that cover 41 cells, so after placing all them on the board, 2 cells stay visible. Ideally, they show today's month and day.
As much fun as it all is, sometimes you just get stuck, but luckily the computer is nearby, and it's just much faster when it comes to trial and error.
Solving the puzzle
There's certainly a more elegant solution, but with such a small puzzle, we can just use brute force by trying every possibility until we find a solution. The most intuitive way is to think of the board as an array, where 0 stands for free and 1 stands for occupied. This way we can define the available tiles as follows
import numpy as np
tiles = [
np.array([[1,1,1],[1,1,1]]),
np.array([[1,1,1],[1,1,0]]),
np.array([[1,1,1],[1,0,1]]),
np.array([[1,1,1],[1,0,0],[1,0,0]]),
np.array([[1,1],[1,0],[1,0],[1,0]]),
np.array([[1,0],[1,1],[1,0],[1,0]]),
np.array([[1,0],[1,0],[1,1],[0,1]]),
np.array([[1,1,0],[0,1,0],[0,1,1]])
]
Each tile can be rotated, flipped, and moved, and in the next step we compute every possible placement in a 7×7 array. In the end, we only keep the unique ones, but NumPy arrays are mutable objects and hence not hashable. That's why we have to get a little bit creative.
Each array consists of 49 digits that are either 0 or 1. Basically, it's just the binary representation of an integer. So each boardstate is uniquely represented by a number between 0 and $2^{49}-1=562949953421311$ and each of those numbers can in return be converted to an array.
placements = {}
for i, tile in enumerate(tiles):
grids = set()
for k in range(4):
rotated = np.rot90(tile,k)
for row in range(0,7-rotated.shape[0]+1):
for col in range(0,7-rotated.shape[1]+1):
grid = np.zeros((7, 7), dtype=int)
grid[row:row+rotated.shape[0], col:col+rotated.shape[1]] = rotated
grids.add(np.sum([d*2**i for i, d in enumerate(grid.flatten())]))
flipped = np.fliplr(rotated)
for row in range(0,7-flipped.shape[0]+1):
for col in range(0,7-flipped.shape[1]+1):
grid = np.zeros((7, 7), dtype=int)
grid[row:row+flipped.shape[0], col:col+flipped.shape[1]] = flipped
grids.add(np.sum([d*2**i for i, d in enumerate(grid.flatten())]))
placements[i] = list(grids)
Although the subsequent steps could also be done using arrays – we can compare if two arrays overlap with the & operator and simply add them together if they do not – it turns out, it is much faster to do the same with the integers. But before we can solve the puzzle, we also need a board to place the tiles on. It is represented by an array with the same shape, where we fill in the few empty tiles at the border and the two tiles that represent the current date
def create_puzzle(month,day):
months = {i: ((i-1)//6,(i-1)%6) for i in range(1,13)}
days = {i: ((i-1)//7+2,(i-1)%7) for i in range(1,32)}
puzzle = np.zeros((7,7),dtype=int)
puzzle[0:2,6] = 1
puzzle[6,3:] = 1
puzzle[months[month]] = 1
puzzle[days[day]] = 1
return np.sum([d*2**i for i, d in enumerate(puzzle.flatten())])
Now how does this work with integers? In Python, the bitwise AND operator & compares the bits of two integers. For example, the binary representation of 13 is 1101 and for 7 it is 0111. 13 & 7 returns 0101, or 5, which means the tiles represented by those two numbers overlap in cells 0 and 2 (our code is 0 indexed). If we compare 13 & 2 we get 0000, so these two do not overlap at all.
The code solves the puzzle through a recursive process where the function calls itself, each time adding one of the remaining tiles to the board. This continues until either all tiles are placed, or no remaining tile fits – in which case it steps back and tries a different placement for the previous tile.
def solve(boardstate,positions=None):
"""
Find a set of tile placements that covers the board.
Parameters
----------
boardstate : int
Integer where each binary digit represents one cell in an array
Returns
-------
dict[int, int] or None
Dictionary where the key is the id of the tile and the value is
the integer representation of the tile.
"""
if positions is None:
positions = {}
# we stop if all tiles are used in the positions
if len(positions) == len(placements):
return positions
# we use the first key that is not yet in positions
next_tile_id = [tile_id for tile_id in placements if tile_id not in positions][0]
for tile in placements[next_tile_id]:
# if the tiles does not overlap with the existing board we continue
if (boardstate & tile) == 0:
# we add it to positions and pass it to solve() again
result = solve(boardstate+tile, positions | {next_tile_id:tile})
# we stop as soon as a deeper call finds a full solution
if result:
return result
# if we come to the end, we did not find a solution in this branch
return None
In the end, we have a dictionary where each entry represents a tile, along with its orientation and position on the board. Okay, that's enough – here's why you're probably here: the solution for today.
