Solving Jane Street’s Puzzles (Day 3)
Last time, we worked through the Hooks puzzle, exploring many interesting and logical ideas. This week we will continue this series with Tile and Trouble puzzle.
Again, for readers who are encountering this series for the first time, my purpose is to solve each and every Jane Street’s Puzzles. My code will be published on my GitHub.
✨Please give me a 👏 if you are interested in my sharing, leave a comment 💬 to share your views/thoughts. ✨
Tile and Trouble
The puzzle was publised at this link.
Add square tiles to the 12-by-12 grid so that the total points in each row and each column matches the corresponding value outside the grid.
- A tile can have any side length (e.g., 1-by-1, 2-by-2, 3-by-3, etc.)
- Every cell within an n-by-n tile is worth n points.
- Tiles may not overlap. Not every cell in the 12-by-12 grid needs to be inside one of the tiles.
- For your answer, submit the product of the areas of each contiguous empty space in the solved grid (along with any other comments you want to provide)
Break down the problem
This puzzle involves adding square tiles to a 12x12 grid so that the total points in each row and each column match the given border values.
In the example, the total points:
- In the first row, it is: 1 + 1 + 2 + 2 + 1 + 1 = 8
- In the first column, it is: 1 + 2 + 2 + 1 + 3 + 3 + 3 = 15
Three important requirements
- The tile can have different sizes, such as 1-by-1, 2-by-2, 3-by-3, etc., and the values in each cell within a tile are the same.
- Each cell within an n-by-n tile is worth n points.
- Tiles cannot overlap. It means that not every cell in the 12-by-12 grid is found inside other tiles.
Submission
Find the product of the areas of empty spaces.
According to the instance, there are 5 empty spaces in the 12x12 grid. Each 1x1 grid equals to 1 unit area. Thus, we have
- 3 units,
- 2 L-shaped tiles (triominoes): one equals to 4 units, another is 2 units
- The area would be 4 * 2 * 1 * 1 * 1 = 8
Before solving the problem, for those who have not heard about the z3 API in Python, they can refer to the previous part at this link. For this challenge, we will learn about Implies in z3. If you already know about this, you can skip that part and move directly to the solution.
Implies in z3
Implies is a Boolean operator supported by z3 in Python. It requires two boolean expressions and returns a boolean expression that represents the logical implication of the two inputs.
In formal logic, the implication (->) is a binary connective that produces a False value only if its first operand is True and its second operand is False. The truth table for implication is as follows:
Here’s how you can use Implies in Python with z3:
In this example, we will define the logic for A, and B values. Using Implies function to verify the logical implication.
from z3 import *
# Create a Z3 solver instance
solver = Solver()
# Define boolean variables
A = Bool('A')
B = Bool('B')
# Iterate through all possible combinations of A and B
all_cases = []
for a_val in [True, False]:
for b_val in [True, False]:
# Set the values for A and B
a_implies_b_formula = Implies(BoolVal(a_val), BoolVal(b_val))
# Add the implication to the solver
solver.push()
solver.add(a_implies_b_formula)
# Check if A implies B is satisfied
if solver.check() == sat:
model = solver.model()
all_cases.append((a_val, b_val, "Satisfiable"))
else:
all_cases.append((a_val, b_val, "Unsatisfiable"))
# Pop the added constraints
solver.pop()
# Print all cases
print("All cases (A, B, Satisfiability):")
for a_val, b_val, satisfiability in all_cases:
print(f"A = {a_val}, B = {b_val}, Satisfiability: {satisfiability}")The result is,
Solution
Import necessary modules and packages
import numpy as np
import time
import itertools
import seaborn as sns
import matplotlib.pyplot as plt
from IPython.display import Markdown
from z3 import *Set up a 12x12 matrix of integer variables
X = [[Int("s%d%d" % (i+1,j+1)) for j in range (size)] for i in range (size)]Add the numbers outside the grid
# The numbers outside the rows.
row_labels = [12,17,43,44,34,42,43,21,36,29,30,26]
# The numbers outside the columns.
col_labels = [30,35,45,43,41,28,25,29,25,38,18,20]Create a z3 solver
s = Solver()Create the size and the maximum value for the tiles
size = 12
nums = 6Now, let’s look at the numbers outside the grid. The biggest value is 45. Thus, if we have a 7-by-7 tile, the maximum total values for a row/column would be 7 x 7 = 49 (which is greater than 45). Hence, we only can fill a maximum 6-by-6 tile in the original 12x12 matrix. Therefore, we set nums = 6 which represents for the value of each cell ranging from 1 to 6.
Set up the constraints for the solver
As we mentioned, each cell only has a value from 1 to 6. Thus,
#Constraints
s += [And(X[i][j]>=0,X[i][j]<=nums) for j in range (size) for i in range(size)]Next, let’s sum the values in the columns and rows to get values equal to the corresponding given border values.
for n in range(size):
#Sum values in the row to get the value equal to the corresponding given border value.
s += Sum([X[n][j] for j in range(size)]) == row_labels[n]
#Sum values in the column to get the value equal to the corresponding given border value.
s += Sum([X[i][n] for i in range(size)]) == col_labels[n]Now, this is an important step to slice different tiles across our 12x12 matrix.
Take 2-by-2 tiles as an example. First of all, we create a loop to slice the n-by-n tiles using the itertools module in Python which implements a number of iterator. In this case, we apply Implies to check whether the value at the current cell is equal to the values at the adjacent cells. Using the result from that logical implication, we can continuously move the tiles along the rows and columns of the matrix.
Here is the code for moving 2-by-2 tiles.
#Now let make a loop to slice the n-by-n tiles in 12x12 grid.
nums = 2
for i,j in itertools.product(range(size),range(size)):
# Slice the 2-by-2 tiles
# Along rows
if i == 1 :
s += [Implies(X[i-1][j] == n,X[i][j] == n) for n in range(nums+1) if n > 1]
elif i > 1 :
s += [Implies(And(X[i-1][j] == n,X[i-2][j] != n),X[i][j] == n) for n in range(nums+1) if n > 1 ]
#Along columns
if j == 1 :
s += [Implies(X[i][j-1] == n,X[i][j] == n) for n in range(nums+1) if n > 1]
elif j > 1 :
s += [Implies(And(X[i][j-1] == n,X[i][j-2] != n),X[i][j] == n) for n in range(nums+1) if n > 1 ]Since we can have tiles with various lengths, ranging from 1-by-1 to 6-by-6, we will make the logical code as follows,
#Now let make a loop to slice the n-by-n tiles in 12x12 grid.
for i,j in itertools.product(range(size),range(size)):
# Slice the 2-by-2 tiles
# Along rows
if i == 1 :
s += [Implies(X[i-1][j] == n,X[i][j] == n) for n in range(nums+1) if n > 1]
elif i > 1 :
s += [Implies(And(X[i-1][j] == n,X[i-2][j] != n),X[i][j] == n) for n in range(nums+1) if n > 1 ]
#Along columns
if j == 1 :
s += [Implies(X[i][j-1] == n,X[i][j] == n) for n in range(nums+1) if n > 1]
elif j > 1 :
s += [Implies(And(X[i][j-1] == n,X[i][j-2] != n),X[i][j] == n) for n in range(nums+1) if n > 1 ]
# Slice the 3-by-3 tiles
# Along rows
if i == 2:
s += [Implies(And(X[i-1][j] == n,X[i-2][j] == n),X[i][j] == n) for n in range(nums+1) if n > 2 ]
elif i > 2 :
s += [Implies(And(X[i-1][j] == n,X[i-2][j] == n,X[i-3][j] != n),X[i][j] == n) for n in range(nums+1) if n > 2 ]
#Along columns
if j == 2:
s += [Implies(And(X[i][j-1] == n,X[i][j-2] == n),X[i][j] == n) for n in range(nums+1) if n > 2 ]
elif j > 2 :
s += [Implies(And(X[i][j-1] == n,X[i][j-2] == n,X[i][j-3] != n),X[i][j] == n) for n in range(nums+1) if n > 2 ]
# Slice the 4-by-4 tiles
# Along rows
if i == 3:
s += [Implies(And(X[i-1][j] == n,X[i-2][j] == n,X[i-3][j] == n),X[i][j] == n) for n in range(nums+1) if n > 3 ]
elif i > 3 :
s += [Implies(And(X[i-1][j] == n,X[i-2][j] == n,X[i-3][j] == n,X[i-4][j] != n),X[i][j] == n) for n in range(nums+1) if n > 3 ]
# Along columns
if j == 3:
s += [Implies(And(X[i][j-1] == n,X[i][j-2] == n,X[i][j-3] == n),X[i][j] == n) for n in range(nums+1) if n > 3 ]
elif j > 3 :
s += [Implies(And(X[i][j-1] == n,X[i][j-2] == n,X[i][j-3] == n, X[i][j-4] != n),X[i][j] == n) for n in range(nums+1) if n > 3 ]
# Slice the 5-by-5 tiles
# Along rows
if i == 4:
s += [Implies(And(X[i-1][j] == n,X[i-2][j] == n,X[i-3][j] == n,X[i-4][j] == n),X[i][j] == n) for n in range(nums+1) if n > 4 ]
elif i > 4 :
s += [Implies(And(X[i-1][j] == n,X[i-2][j] == n,X[i-3][j] == n,X[i-4][j] == n,X[i-5][j] != n),X[i][j] == n) for n in range(nums+1) if n > 4 ]
# Along columns
if j == 4:
s += [Implies(And(X[i][j-1] == n,X[i][j-2] == n,X[i][j-3] == n,X[i][j-4] == n),X[i][j] == n) for n in range(nums+1) if n > 4 ]
elif j > 4 :
s += [Implies(And(X[i][j-1] == n,X[i][j-2] == n,X[i][j-3] == n,X[i][j-4] == n,X[i][j-5] != n),X[i][j] == n) for n in range(nums+1) if n > 4 ]
# Slice the 6-by-6 tiles
# Along rows
if i == 5:
s += [Implies(And(X[i-1][j] == n,X[i-2][j] == n,X[i-3][j] == n,X[i-4][j] == n,X[i-5][j] == n),X[i][j] == n) for n in range(nums+1) if n > 5 ]
elif i > 5 :
s += [Implies(And(X[i-1][j] == n,X[i-2][j] == n,X[i-3][j] == n,X[i-4][j] == n,X[i-5][j] == n,X[i-6][j] != n),X[i][j] == n) for n in range(nums+1) if n > 5 ]
# Along columns
if j == 5:
s += [Implies(And(X[i][j-1] == n,X[i][j-2] == n ,X[i][j-3] == n,X[i][j-4] == n,X[i][j-5] == n),X[i][j] == n) for n in range(nums+1) if n > 5 ]
elif j > 5 :
s += [Implies(And(X[i][j-1] == n,X[i][j-2] == n,X[i][j-3] == n,X[i][j-4] == n, X[i][j-5] == n,X[i][j-6] != n),X[i][j] == n) for n in range(nums+1) if n > 5 ] Processing
Step 1: Filling the tiles
start = time.time()
if s.check() == sat:
print("Solved in {} seconds".format(time.time()-start))
m = s.model()
out = np.array([ [ m.evaluate(X[i][j]).as_long() for j in range(size) ] for i in range(size) ])
x = np.copy(out)
x = x.astype('int').astype('str')
x[x=="0"] = ""
fig,ax = plt.subplots(1,1,figsize=(5,5))
ax =sns.heatmap(out,annot=x,cbar=False,center=3,cmap="tab20_r",fmt="",linewidths=1,linecolor="grey",annot_kws={"size":14},
xticklabels=col_labels, yticklabels=row_labels)
ax.tick_params(left=False, bottom=False,labelleft=False, labelright=True)
plt.xticks(rotation=0,fontsize =12)
plt.yticks(rotation=0,fontsize =12)
plt.tight_layout()
plt.show()
else:
print("No solution in {} seconds".format(time.time()-start))The output is,
Step 2: Find the product of the areas of each contiguous empty space in the solved grid.
In order to count the number of zeros in each connected area containing zeros in a given array, you can use depth-first search (DFS) or breadth-first search (BFS) to traverse the areas and count the zeros in each area. Here’s a Python code that achieves this using DFS:
def dfs(grid, visited, row, col, count):
if (row < 0 or col < 0 or
row >= len(grid) or col >= len(grid[0]) or
visited[row][col] or grid[row][col] != 0):
return count
visited[row][col] = True
count += 1
# Check adjacent cells
count = dfs(grid, visited, row - 1, col, count)
count = dfs(grid, visited, row + 1, col, count)
count = dfs(grid, visited, row, col - 1, count)
count = dfs(grid, visited, row, col + 1, count)
return count
def count_zeros_in_areas(grid):
rows, cols = len(grid), len(grid[0])
visited = [[False for _ in range(cols)] for _ in range(rows)]
zero_counts = []
for i in range(rows):
for j in range(cols):
if grid[i][j] == 0 and not visited[i][j]:
zero_count = dfs(grid, visited, i, j, 0)
zero_counts.append(zero_count)
return zero_counts
# Count zeros in each connected area
zero_counts = count_zeros_in_areas(out)
# Calculate the product using numpy.prod
product = np.prod(zero_counts)
# Print the counts
print("Number of zeros in each connected area:")
for i, count in enumerate(zero_counts, start=1):
print(f"Area {i}: {count} zeros")
# Print the product
print("Product of the areas:", product)The result is,
Public solution
The best solution was published here.
Conclusion
Through this post, we have explored another interesting puzzle. Nonetheless, I know that you can find different approaches to solve this Tile and Trouble puzzle. Feel free to share your solution with readers here by commenting below this post.
Next week, we will dive into another challengle called Number Cross. This puzzle can be simply solved by writting it down and using your knowledge as playing a daily New York Times Crossword puzzle. However, I will address it by a bunch of logical operations and running the code to obtain the final result. See you all next time.
Note: Unless otherwise noted, all images are by the author.
Source code
https://github.com/Tayerquach/quant_puzzles
References
https://www.janestreet.com/puzzles/
