In [ ]:
"""
Jane Street Puzzle
March 2025: Hall of Mirrors 3
Twenty-eight solutions
By Kauri Beckmann
kauri.b@outlook.co.nz
22/03/2025
I take an iterative depth-first search approach to solving Hall of Mirrors 3.
Actually, I use two iterative DFS's.
Exploring at greater depths yields more solutions, at cost of time.
I find 28 unique solutions to the puzzle, with 22 unique answers.
Without rewriting the code, regrettably I have no way to prove I haven't missed any solutions.
Final solution runtime: apx 5 min
Before going any further, I just want to say to the Jane Street Puzzle Team,
The way you come up with this stuff, it blows my mind. You guys are awesome!
I'm not a developer, by any means. I'm just a structural engineer that likes solving complex puzzles.
This is by far the most challenging code piece I've ever written.
And writing it was a hell of a lot more fun than solving the puzzle by hand!
Overview:
The grid is defined as 12x12 list of lists
Border contains starting cells as specified by puzzle. All other cells initially blank.
The DFS starts at a user-specified border cell.
As the DFS moves, it writes mirror locations and light pathways to the grid
This is what effectively creates our DFS movement constraints
DFS movement is defined based on a number of factors:
Movement direction:
- Depending on starting position, or mirrors
Movement length:
- Factors of the starting cell, divided by previous move sizes
Invalid moves:
- We cannot move outside the grid (duh)
- We cannot end a movement on an existing "light pathway"
- We cannot move through an existing mirror
If at any point we reach the border, have we found a valid pathway?
Restriction of search depth
If we have to account for movements 1,1,1,1,1,3,1,1,1,1,1,1,1,3,2,1,1,1,1,1,1,1,1,1,1,2,5,1,1,1,1,1,1,1,1,2,5,1,1,1,1,1,1,1,1,1,1,1,1,1....
We would be here forever.
It's also unlikely, because pathways should generally be relatively efficient.
Thus I manually restrict search depth.
This DFS is repeated for each starting cell.
Possible positions expands as we add more cells, until the grids become more "filled" with constraints
We eventually converge on the final solutions (plural!)
The first DFS doesn't solve for unspecified starting cells.
But, there will always be at least one solution, given all specified starting cells are solved.
I use a second DFS to solve these cells.
There's a bunch more logic involved to solving the final cells that I won't go into here."
"""
print("""
Jane Street Puzzle
March 2025: Hall of Mirrors 3
Twenty-Eight Solutions
By Kauri Beckmann
kauri.b@outlook.co.nz
18/03/2025
""")
Jane Street Puzzle March 2025: Hall of Mirrors 3 Twenty-Eight Solutions By Kauri Beckmann kauri.b@outlook.co.nz 18/03/2025
In [29]:
"""
Grid initialization
Starting_grid is never modified
"""
starting_grid = [
['', '', '', 112, '', 48, 3087, 9, '', '', 1, ''],
['', '', '', '', '', '', '', '', '', '', '', ''],
['', '', '', '', '', '', '', '', '', '', '', 4],
['', '', '', '', '', '', '', '', '', '', '', 27],
[27, '', '', '', '', '', '', '', '', '', '', ''],
['', '', '', '', '', '', '', '', '', '', '', ''],
['', '', '', '', '', '', '', '', '', '', '', ''],
['', '', '', '', '', '', '', '', '', '', '', 16],
[12, '', '', '', '', '', '', '', '', '', '', ''],
[225, '', '', '', '', '', '', '', '', '', '', ''],
['', '', '', '', '', '', '', '', '', '', '', ''],
['', 2025, '', '', 12, 64, 5, '', 405, '', '', '']
]
grid_size = len(starting_grid) # Legacy variable, regrettably still used in a few places
def print_grid(grid):
"""Little function to print grids"""
cell_width = 4
for row in grid:
print(" | ".join(f"{str(cell):<{cell_width}}" for cell in row))
print("Hall of Mirrors 3: Starting grid")
print_grid(starting_grid)
Hall of Mirrors 3: Starting grid
| | | 112 | | 48 | 3087 | 9 | | | 1 |
| | | | | | | | | | |
| | | | | | | | | | | 4
| | | | | | | | | | | 27
27 | | | | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | | 16
12 | | | | | | | | | | |
225 | | | | | | | | | | |
| | | | | | | | | | |
| 2025 | | | 12 | 64 | 5 | | 405 | | |
In [30]:
"""This is the main display function"""
import matplotlib.pyplot as plt
def display_solutions(solutions):
"""
ChatGPT is good at is producing pretty plots.
"""
colors = [
"#ff7f0e", "#1f77b4", "#2ca02c", "#d62728", "#9467bd", "#8c564b", "#e377c2", "#7f7f7f",
"#bcbd22", "#17becf", "#f39c12", "#16a085", "#9b59b6", "#e74c3c", "#2ecc71", "#3498db",
"#f1c40f", "#8e44ad", "#c0392b", "#34495e"
]
color_index = 0
for grid, paths in solutions:
rows, cols = len(grid), len(grid[0])
fig, ax = plt.subplots(figsize=(cols * 0.6, rows * 0.6))
ax.set_xticks([])
ax.set_yticks([])
ax.set_frame_on(False)
ax.set_position([0, 0, 1, 1])
for i in range(1, rows):
ax.plot([0, cols], [i, i], "black", lw=1) # Horizontal lines
for j in range(1, cols): # Start from 1 to skip the outermost column
ax.plot([j, j], [0, rows], "black", lw=1) # Vertical lines
# Draw bold border around the interior grid (excluding outermost row/column)
ax.plot([0, cols], [1, 1], "black", lw=3) # Top border
ax.plot([0, cols], [rows - 1, rows - 1], "black", lw=3) # Bottom border
ax.plot([1, 1], [0, rows], "black", lw=3) # Left border
ax.plot([cols - 1, cols - 1], [0, rows], "black", lw=3) # Right border
# Annotate grid values, draw diagonals for "B" and "F", and place dots on borders
for i, row in enumerate(grid):
for j, cell in enumerate(row):
is_border = i == 0 or i == rows - 1 or j == 0 or j == cols - 1 # Border check
# Place a dot in the border cells (except the corners)
if is_border and not (i == 0 and j == 0) and not (i == 0 and j == cols - 1) and not (i == rows - 1 and j == 0) and not (i == rows - 1 and j == cols - 1):
ax.plot(j + 0.5, rows - i - 0.5, 'ko', markersize=5) # Large dot (black)
# Show only border values
if is_border and cell: # Show only border values
# Adjust position to place numbers outside the grid
if i == 0: # Top border
ax.text(j + 0.5, rows + 0.2, str(cell), ha="center", va="center")
elif i == rows - 1: # Bottom border
ax.text(j + 0.5, -0.2, str(cell), ha="center", va="center")
elif j == 0: # Left border
ax.text(-0.2, rows - i - 0.5, str(cell), ha="center", va="center")
elif j == cols - 1: # Right border
ax.text(cols + 0.2, rows - i - 0.5, str(cell), ha="center", va="center")
# Draw diagonals for "B" and "F"
if cell == "B":
ax.plot([j, j + 1], [rows - i, rows - i - 1], "r", lw=2) # Draw \ for "B"
elif cell == "F":
ax.plot([j, j + 1], [rows - i - 1, rows - i], "r", lw=2) # Draw / for "F"
# Draw paths with the next color in the list
for path in paths:
path_color = colors[color_index]
color_index = (color_index + 1) % len(colors) # Cycle through the colors
for k in range(len(path) - 1):
# Get the grid coordinates of two consecutive points in the path
p1 = path[k]
p2 = path[k + 1]
ax.plot([p1[1] + 0.5, p2[1] + 0.5], [rows - p1[0] - 0.5, rows - p2[0] - 0.5], path_color, lw=2) # Path line
plt.subplots_adjust(left=0, right=1, top=1, bottom=0) # Reduce whitespace
plt.show()
teaser_grid = [['', '', '', 112, '', 48, 3087, 9, '', '', 1, ''],['', '', '', '', '', '', 'o', '', '', '', '', ''],[2025, 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'B', '', 4],['', '', 'F', 'B', '', '', 'o', '', '', 'o', '', 27],[27, '', 'o', 'B', 'o', 'o', 'o', 'o', 'o', 'o', 'B', ''],['', '', 'o', '', '', '', 'o', '', '', 'o', 'o', ''],['', '', 'B', 'o', 'o', 'B', 'o', '', '', 'o', 'o', ''],['', '', '', '', '', 'B', 'F', 'o', 'o', 'F', 'o', 16],[12, '', '', '', '', '', 'o', '', '', '', 'o', ''],[225, '', '', '', '', '', 'o', '', '', '', 'o', ''],['', 'F', 'o', 'o', 'o', 'o', 'F', '', '', '', 'o', ''],['', 2025, '', '', 12, 64, 5, '', 405, '', 3087, '']]
teaser_path = [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)],[(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)]
teaser_solution = teaser_grid, teaser_path
print("Demonstration: display_solutions")
print("And yes, this is part of an actual solution. 3087's pathway can look like this. Beautiful!")
display_solutions([teaser_solution])
Demonstration: display_solutions And yes, this is part of an actual solution. 3087's pathway can look like this. Beautiful!
In [31]:
"""
These functions determine which moves are valid based on our starting cell value, and our direction of movement
"""
import math
def unique_factors_of(n):
"""
Returns all unique factors of `n` that are in the predefined `possible_factors` list.
"""
possible_factors = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
factors = set()
# Iterate only up to sqrt(n) to reduce unnecessary checks
for i in range(1, int(math.sqrt(n)) + 1):
if n % i == 0:
factors.add(int(i))
factors.add(int(n // i))
# Return only the factors that exist in possible_factors
return sorted([f for f in factors if f in possible_factors], reverse=True)
def find_possible_moves(current_value, directions):
"""
Tells you the possible moves you can make
Multiplies direction by unique_factors_of
"""
factors_list = unique_factors_of(current_value)
possible_moves = [(factor * directions[0], factor * directions[1]) for factor in factors_list]
return possible_moves
print("Demonstration: unique_factors_of_(3087)")
print(unique_factors_of(3087))
print("Demonstration: find_possible_moves(3087, (-1,0))")
print(find_possible_moves(3087, (-1,0)))
Demonstration: unique_factors_of_(3087) [9, 7, 3, 1] Demonstration: find_possible_moves(3087, (-1,0)) [(-9, 0), (-7, 0), (-3, 0), (-1, 0)]
In [32]:
"""
Various checks, generally to check whether we have made a valid move
"""
def check_move(grid, current_pos):
"""
Calls a couple of functions to determine whether our current position is valid.
Is the position within the grid? If not, invalid.
Is the position on an existing light pathway? If so, we wouldn't be able to place a mirror here, invalid.
Else return True
This function does not check if we have passed through an existing mirror. This will be handed seperately as it requires past moves to have occurred.
This function does not check if our position is on an existing mirror. This will be handled elsewhere as it determines direction.
This function does not check if our position is on a boundary. This will be handled elsewhere as it is an end condition for our DFS.
"""
if check_move_within_grid(current_pos) == False:
return False
if check_move_lightpathway_occupied(grid, current_pos) == True:
return False
return True
def check_move_within_grid(current_pos):
"""
Returns true if our current position is within the grid.
If not, we can't move here - invalid move
"""
row, col = current_pos
return (0 <= row < grid_size and 0 <= col < grid_size and
(row, col) not in [(0, 0), (0, grid_size - 1), (grid_size - 1, 0), (grid_size - 1, grid_size - 1)])
def check_move_lightpathway_occupied(grid, current_pos):
"""
Returns true if our current position is occupied by light pathway
If so, we can't place a mirror here - invalid move
"""
row, col = current_pos
return grid[row][col] == "o"
def check_move_on_border(current_pos):
"""
Returns true if current_pos is on the border
This is called a few times, as part of determining whether a valid solution has been found.
"""
row, col = current_pos
return row in (0, grid_size - 1) or col in (0, grid_size - 1)
def check_move_passes_through_mirror(grid, previous_pos, current_pos):
"""
Returns true if our pathway crosses an existing mirror
If our light path crosses an existing mirror, it isn't a valid move
Take our previous and current positions. If there is an F or B between them, we've crossed a mirror"
"""
x1, y1 = previous_pos
x2, y2 = current_pos
if x1 == x2: # If we're moving horizontally
y_range = range(min(y1, y2) + 1, max(y1, y2)) # Skip the first and last square
for y in y_range:
if grid[x1][y] in ("F", "B"): # Check for mirrors in between
return True
elif y1 == y2: # If we're moving vertically
x_range = range(min(x1, x2) + 1, max(x1, x2))
for x in x_range:
if grid[x][y1] in ("F", "B"):
return True
return False # No mirror encountered in the path
In [33]:
"""
Movement directions
Directions are just a tuple coordinate eg (1, 0)
"""
def start_direction(current_pos):
"""Starting condition: we can only move in one direction, perpendicular to the starting border"""
x, y = current_pos
if not check_move_on_border(current_pos): # Debug code, should always start on border
return ("start_direction error: start_pos not on border")
if x == 0: # Top border
return (1, 0) # Move down
if x == grid_size - 1: # Bottom border
return (-1, 0) # Move up
if y == 0: # Left border
return (0, 1) # Move right
if y == grid_size - 1: # Right border
return (0, -1) # Move left
# F / Forwards mirror (Forwardslash)
def mirror_F(direction):
"""
Defines how mirrors redirect our direction
Pretty straightforward (or straightbackward, ha ha ha ha )"
"""
return (-direction[1], -direction[0])
# B \ Backwards mirror (Backslash)
def mirror_B(direction):
return (direction[1], direction[0])
In [34]:
def place_light_path(grid, previous_pos, current_pos):
"""
This function places "o"s along the light travel pathway
Excluding start and end cells
Return an updated grid
An "o" defines a cell as a "light travel pathway"
No mirror may be placed on this cell anymore"
"""
x1, y1 = previous_pos
x2, y2 = current_pos
next_grid = [row[:] for row in grid] # Shallow copy of the grid (only rows)
if y1 == y2: # If moving horizontally
for x in range(min(x1, x2) + 1, max(x1, x2)): # Iterate across cells and place "o"
next_grid[x][y1] = "o"
elif x1 == x2: # If moving vertically
for y in range(min(y1, y2) + 1, max(y1, y2)):
next_grid[x1][y] = "o"
return next_grid
print("Demonstration: place_light_path")
demo_grid = [["", "3", "", ""],
["", "", "", ""],
["", "", "", ""],
["", "3", "", ""]
]
print("Demo grid, blank")
print_grid(demo_grid)
print("Say we move from (0, 1) (3, 1), ie from top to bottom")
print_grid(place_light_path(demo_grid, (0,1), (3,1)))
Demonstration: place_light_path
Demo grid, blank
| 3 | |
| | |
| | |
| 3 | |
Say we move from (0, 1) (3, 1), ie from top to bottom
| 3 | |
| o | |
| o | |
| 3 | |
In [35]:
def check_possible_moves_update_stack(current_grid, possible_moves, current_pos, current_value, path, path_instance, direction, start_pos, stack, solutions):
"""
This is one of the core functions.
It handles majority of the logic within the DFS.
Notable exception: Directional change is handled elsewhere.
If I did it again, I'd write the function really quite differently, but I'm not getting paid for this. It runs fast enough and it doesn't break.
At its core, this function takes the current grid, and possible moves.
It checks if possible moves are valid, checks if each move results in a solution, and updates our stack accordingly.
Logic process:
- Iterate through possible_moves.
- Determine position to check (check_pos)
- Call function check_move
- Call function check_move_passes_through_mirror
- If both valid
- Check if solution found. If so, save solution, move to next in stack
- Else, we have a valid position - DFS to continue from this position
- Call function place_light_path to save light pathway to grid
- Append to path
- Note, path is a legacy item that is not really used
- Its current purpose is that by checking len(path) we limit the depth of search, artificially restricting the number of 1-square moves
- Maximum path length will be set when calling the DFS. If exceeded, move to next in stack.
- Update search value (current_value, next_value)
- Calculate move_size
- Divide search value by move size
- eg: We are searching for a solution for search value 16. Valid factors of 16 are 1, 2, 4, 8.
We move (0, -8), move size 8. Search value becomes 16/8 = 2.
- Append to stack
- Stack contains:
- Current position (tuple coordinate)
- Path (list of tuple coordinates, sequence of moves leading to current position)
- Path instance (list of list of tuple coordinates, existing paths corresponding to current grid)
- Current grid (the grid, updated with mirrors and light pathways)
- Current search value (integer)
- Last direction of movement (tuple coordinate)
"""
x,y = start_pos
search_value = current_grid[x][y]
for move in possible_moves:
# Position to check:
check_pos = (current_pos[0] + move[0], current_pos[1] + move[1])
# Check whether the move is valid
if not check_move(current_grid, check_pos):
continue
if check_move_passes_through_mirror(current_grid, current_pos, check_pos):
continue
# Update our grid, path and search value
# I could probably move this later in the function, but
next_grid = place_light_path(current_grid, current_pos, check_pos)
next_path = path.copy()
next_path.append(check_pos)
move_size = abs(move[0]) if move[1] == 0 else abs(move[1])
next_value = current_value / move_size
# Check if solution is found
# If we aren't on our starting position
# If we are on border
# If boundary is blank or matches search value
# Solution found: Save grid and path as a solution
# Move to next item in stack
if not (current_pos == start_pos):
if(check_move_on_border(check_pos)):
if next_value == 1:
if current_grid[check_pos[0]][check_pos[1]] == search_value or current_grid[check_pos[0]][check_pos[1]] == "":
next_grid[check_pos[0]][check_pos[1]] = search_value
solutions.append([next_grid, path_instance + [next_path]])
# This print function doubles run time, suggest comment it out...
# Is really nice to see... though!
# print(f"Solution count: {len(solutions)}", end="\r", flush=True)
continue
# If we haven't already moved to the next position in stack... It is a valid move and not a solution
# Therefore append the position to the stack for future exploration
stack.append((check_pos, next_path, path_instance, next_grid, next_value, direction))
return stack
In [36]:
def dfs_iterative(starting_grids_and_paths, start_pos, max_path_length):
"""
The DFS takes three inputs:
- starting_grids_and_paths
- list of grids and paths
- ie, we can search multiple grids
- primary purpose of paths is to draw our solutions
- start_pos - tuple coordinate, user-defined, the border cell which we are starting our search from
- max_path_length - integer, user-defined, essentially limits search depth
- return solutions - list of grids, current_paths
Initialisation:
- Determine search_value based on start_pos
- Determine starting movement direction
- Create our stack, containing all starting_grids_and_paths
Note we start with the assumption that the current position is valid. Validity checks are performed before adding to stack.
Logic:
- While stack is not empty:
- Pop the last stack item
- Check if our path is too long (limits search depth. note inefficiency, should be handling before appending to stack)
- If mirror exists at current position:
- Change direction
- Determine which moves are possible based on our search_value
- Call function check_possible_moves_update_stack
- If no mirror:
- Place mirror F
- Change direction
- Determine which moves are possible based on our search_value
- Call function check_possible_moves_update_stack
- Repeat for mirror B
- Alternatively, if we are at our starting position
- Call function check_possible_moves_update_stack
"""
x,y = start_pos
search_value = starting_grid[x][y]
path = [(start_pos)]
starting_direction = (start_direction(start_pos))
stack = []
for grid_instance, path_instance in starting_grids_and_paths:
stack.append((start_pos, path, path_instance, grid_instance, search_value, starting_direction))
solutions = []
next_direction = []
while stack:
current_pos, path, path_instance, current_grid, current_value, direction = stack.pop()
x, y = current_pos
# Limits search depth
if len(path) > max_path_length:
continue
# Check for or place mirror
# Determine direction
# Call function to calculate possible moves
# Call function to update stack
# Check for a mirror
if current_grid[x][y] == "F":
next_direction = mirror_F(direction)
possible_moves = find_possible_moves(current_value, next_direction)
check_possible_moves_update_stack(current_grid, possible_moves, current_pos, current_value, path, path_instance, next_direction, start_pos, stack, solutions)
if current_grid[x][y] == "B":
next_direction = mirror_B(direction)
possible_moves = find_possible_moves(current_value, next_direction)
check_possible_moves_update_stack(current_grid, possible_moves, current_pos, current_value, path, path_instance, next_direction, start_pos, stack, solutions)
# If no mirror: Place one
if current_grid[x][y] == "":
current_grid[x][y] = "F"
next_direction = mirror_F(direction)
possible_moves = find_possible_moves(current_value, next_direction)
check_possible_moves_update_stack(current_grid, possible_moves, current_pos, current_value, path, path_instance, next_direction, start_pos, stack, solutions)
# Then place the other
current_grid[x][y] = "B"
next_direction = mirror_B(direction)
possible_moves = find_possible_moves(current_value, next_direction)
check_possible_moves_update_stack(current_grid, possible_moves, current_pos, current_value, path, path_instance, next_direction, start_pos, stack, solutions)
# Or we might be at our starting position, in which case we know our direction
if current_pos == start_pos:
possible_moves = find_possible_moves(current_value, direction)
next_direction = direction
check_possible_moves_update_stack(current_grid, possible_moves, current_pos, current_value, path, path_instance, next_direction, start_pos, stack, solutions)
return(solutions)
In [37]:
def process_new_steps():
"""
This function is what calls our DFS.
The purpose of this function is to allow me to process a number of steps, then later process further ones without recalculating previous steps.
It tracks the steps already processed, then processes new ones by calling our DFS.
Note there is a bug in the "solutions found", it does not print correctly. I have not bothered to resolve.
"""
global processed_steps
while processed_steps < len(steps):
start_pos, max_path_length = steps[processed_steps]
solutions.append(dfs_iterative(solutions[-1], start_pos, max_path_length))
print(f"Step count: {processed_steps} Solutions found: {len(solutions[-1])}", end="\n", flush=True)
processed_steps += 1 # Update processed count
In [38]:
def print_solutions(solutions):
"""
Prints solutions in a visually legible manner.
Note solutions must be a list of grids and coordinate paths.
"""
for i, (grid, paths) in enumerate(solutions):
print(f"Solution {i+1}:")
# Print grid
for row in grid:
print(" | ".join(str(cell).ljust(4) for cell in row))
# Print paths for this solution
print(f"Paths for Solution {i+1}: {paths}")
print("\n" + "-" * 50 + "\n")
In [39]:
"""EXAMPLE DFS PART 1
These examples are a demonstration of the depth first search.
Since the final solution takes a few minutes to run!
The first steps set out only the most obvious mirrors.
This creates additional constraints for future searches, reducing search complexity.
Actually finding the solution takes some more work
"""
print("EXAMPLE DFS PART 1")
print("")
import copy
steps = [ # ((start_pos), search depth)
((0, 10), 2), # Step 0: 1, search depth 2 (ie allows 1 mirror interaction. there is only one realistic solution for 1)
((11, 6), 2), # Step 1: 5, depth 2 (again only one realistic solution)
((2, 11), 3), # Step 2: 4, depth 3
((0, 7), 4), # Step 3: 9, depth 4
]
# Initialise with original grid and empty path list
grid = copy.deepcopy(starting_grid) # Prevent modification to starting_grid
solutions = [[[grid, []]]] # Note this is a list of list of lists of lists of f*cking lists!
processed_steps = 0 # Track how many steps have been processed
#print(solutions)
#print(solutions[-1])
process_new_steps()
print("")
print("We've found 8 solutions so far.")
print("Just printing the first solution for ya!")
print("")
print("I think it's really cool. The solution contains both grid and light pathway information, which was such a challenge to pull off!")
print("")
print_solutions([solutions[-1][0]])
display_solutions([solutions[-1][0]])
EXAMPLE DFS PART 1
Step count: 0 Solutions found: 1
Step count: 1 Solutions found: 1
Step count: 2 Solutions found: 2
Step count: 3 Solutions found: 8
We've found 8 solutions so far.
Just printing the first solution for ya!
I think it's really cool. The solution contains both grid and light pathway information, which was such a challenge to pull off!
Solution 1:
| | | 112 | | 48 | 3087 | 9 | | 4 | 1 |
| | | | | | | B | B | o | B | 1
| | | | | | | | o | B | o | 4
| | | | | | | | o | | | 27
27 | | | | | | | | B | o | o | 9
| | | | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | | 16
12 | | | | | | | | | | |
225 | | | | | | | | | | |
| | | | | | F | o | o | o | o | 5
| 2025 | | | 12 | 64 | 5 | | 405 | | |
Paths for Solution 1: [[(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(0, 7), (1, 7), (1, 8), (4, 8), (4, 11)]]
--------------------------------------------------
In [40]:
"""
EXAMPLE DFS PART 2
This time we simply append start position 16 to the list of steps, then execute the DFS
This was invaluable for testing purposes... not really used in the final solution
"""
print("EXAMPLE DFS PART 2")
print("")
steps.append(((7, 11), 4)) # Step 4: 16, depth 4 (uncertain on depth here - could definitely expand search depth)
process_new_steps() # Continues from the last solutions
print("")
print("Now we're at 33 possible solutions.")
print("Just printing the first solution for ya!")
print("")
print_solutions([solutions[-1][0]])
display_solutions([solutions[-1][0]])
EXAMPLE DFS PART 2
Step count: 4 Solutions found: 33
Now we're at 33 possible solutions.
Just printing the first solution for ya!
Solution 1:
| | | 112 | | 48 | 3087 | 9 | | | 1 |
| | | | | | | o | | | B | 1
| | | | | | | o | | | F | 4
| | | | | | | B | B | | o | 27
27 | | | | | | | | B | o | o | 9
| | | | | | | | | | o |
| | | | | | | | | | B | 4
| | | | | | | | | F | o | 16
12 | | | | | | | | | o | |
225 | | | | | | | F | o | F | |
| | | | | | F | o | o | o | o | 5
| 2025 | | | 12 | 64 | 5 | 16 | 405 | | |
Paths for Solution 1: [[(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 10), (6, 10), (6, 11)], [(0, 7), (3, 7), (3, 8), (4, 8), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)]]
--------------------------------------------------
In [41]:
"""EXAMPLE DFS PART 3
Runtime: 0.2 seconds
This time I provide you a somewhat optimized set of inputs that are sufficient to find two specific solutions.
In early steps we set out the most obvious mirrors.
This will reduce search depth later on. by creating additional constraints for our more complex pathways.
Notice, our solution isn't quite complete.
We're still missing some of the border cells.
For one solution, there's an empty internal cell.
We still need to calculate the answer(s)!
Next I'll introduce some new functions that help us achieve this.
"""
print("EXAMPLE DFS PART 3")
print("")
steps = [ # ((start_pos), search depth)
((0, 10), 2), # Step 0: 1, search depth 2 (ie allows 1 mirror interaction. there is only one realistic solution for 1)
((11, 6), 2), # Step 1: 5, depth 2 (again only one realistic solution)
((2, 11), 2), # Step 2: 4, depth 3
((0, 7), 4), # Step 3: 9, depth 4
((8, 0), 2), # Step 4 : 12 west
((7, 11), 4), # Step 5: 16
((3, 11), 3), # Step 6: 27 East
((11, 1), 6), # Step 7: 2025
((0, 6), 5), # Step 8: 3087
((4, 0), 7), # Step 9: 27 West
((9, 0), 8), # Step 10: 225
((11, 8), 8), # Step 11: 405
((0, 3), 4), # Step 12: 112
((11, 4), 2), # Step 13: 12 south
((11, 5), 6), # Step 14: 64
((0, 5), 8), # Step 15: 48
]
# Initialise with original grid and empty path list
grid = copy.deepcopy(starting_grid) # Prevent modification to starting_grid
solutions = [[[grid, []]]] # Note this is a list of list of lists of lists of f*cking lists!
processed_steps = 0 # Track how many steps have been processed
#print(solutions)
#print(solutions[-1])
process_new_steps()
print("")
print("Notice how our 'Solutions found' fluctuates, peaking at Step 7, 203 solutions.")
print(" This is because I've provided quite specific search depths.")
print(" In deeper searches, 'Solutions found' can easily fluctuate in the thousands - to hundred-thousands of solutions.")
print("")
print("Printing both solutions for ya!")
print("")
print("Check out 27 west and 48. Wacky pathways!")
print("Notice how the first solution has an empty internal cell.")
print(" What happens if we put a mirror there?")
print("")
display_solutions(solutions[-1])
EXAMPLE DFS PART 3 Step count: 0 Solutions found: 1 Step count: 1 Solutions found: 1 Step count: 2 Solutions found: 1 Step count: 3 Solutions found: 5 Step count: 4 Solutions found: 5 Step count: 5 Solutions found: 24 Step count: 6 Solutions found: 16 Step count: 7 Solutions found: 203 Step count: 8 Solutions found: 50 Step count: 9 Solutions found: 72 Step count: 10 Solutions found: 96 Step count: 11 Solutions found: 89 Step count: 12 Solutions found: 47 Step count: 13 Solutions found: 47 Step count: 14 Solutions found: 10 Step count: 15 Solutions found: 2 Notice how our 'Solutions found' fluctuates, peaking at Step 7, 203 solutions. This is because I've provided quite specific search depths. In deeper searches, 'Solutions found' can easily fluctuate in the thousands - to hundred-thousands of solutions. Printing both solutions for ya! Check out 27 west and 48. Wacky pathways! Notice how the first solution has an empty internal cell. What happens if we put a mirror there?
In [42]:
"""
Example continues soon...
We are not done with the functions yet.
I use a DFS to "finish" the solutions and calculate our answers.
As you can see, we're still missing some cells.
Each empty internal cell could be empty, or have a mirror. Whichever the case, we will find a valid answer.
Empty border cells need to be filled with their respective values.
And toughest of all, to calculate the final answer, the almighty calculate_sum_product_of_borders
"""
def draw_new_light_path(grid, path, current_pos):
"""
This function is applied to an empty border cell.
It follows our usual movement restrictions, until it reaches another empty border cell.
It tracks the move length between mirrors and borders etc.
And outputs our light path, and an updated grid.
It does not place mirrors. This is done elsewhere.
Frankly I'm tired of writing good comments within the code :)
"""
if grid[current_pos[0]][current_pos[1]] != "":
print("error: this function shouldn't be called. cell not empty.")
return
direction = start_direction(current_pos)
next_path = [current_pos]
next_pos = current_pos
move_size = 0
move_size_multiplier = 1
while True:
move_size += 1
next_pos = (next_pos[0] + direction[0], next_pos[1] + direction[1])
if not check_move_within_grid(next_pos):
print("error found outside of grid")
break
if check_move_on_border(next_pos) and grid[next_pos[0]][next_pos[1]] != "":
print("error found a border with value")
break
if grid[next_pos[0]][next_pos[1]] == "F":
direction = mirror_F(direction)
move_size_multiplier *= move_size
move_size = 0
next_path.append(next_pos)
if grid[next_pos[0]][next_pos[1]] == "B":
direction = mirror_B(direction)
move_size_multiplier *= move_size
move_size = 0
next_path.append(next_pos)
if check_move_on_border(next_pos) and grid[next_pos[0]][next_pos[1]] == "":
move_size_multiplier *= move_size
grid[current_pos[0]][current_pos[1]] = move_size_multiplier
grid[next_pos[0]][next_pos[1]] = move_size_multiplier
next_path.append(next_pos)
break
path.append(next_path)
return [grid, path]
def calculate_sum_product_of_borders(grid):
"""
This one's simple.
Requires all border cells to be filled.
Sums each border and multiplies together.
Since we shouldn't include original border cells, just start border sums as negative numbers summing original border cells
"""
rows, cols = len(grid), len(grid[0])
# Initialize sums for each border
sum_top = -(112 + 48 + 3087 + 9 + 1)
sum_bottom = -(2025 + 12 + 64 + 5 + 405)
sum_left = -(27 + 12 + 225)
sum_right = -(4 + 27 + 16)
# Sum the top border (excluding corners)
for i in range(1, cols - 1):
if grid[0][i] == "":
return False # If any cell in the top border is empty, return False
sum_top += grid[0][i]
# Sum the bottom border (excluding corners)
for i in range(1, cols - 1):
if grid[rows - 1][i] == "":
return False # If any cell in the bottom border is empty, return False
sum_bottom += grid[rows - 1][i]
# Sum the left border (excluding corners)
for i in range(1, rows - 1):
if grid[i][0] == "":
return False # If any cell in the left border is empty, return False
sum_left += grid[i][0]
# Sum the right border (excluding corners)
for i in range(1, rows - 1):
if grid[i][cols - 1] == "":
return False # If any cell in the right border is empty, return False
sum_right += grid[i][cols - 1]
# Calculate the product of the sums
sum_product = sum_top * sum_bottom * sum_left * sum_right
return sum_product
In [43]:
"""
And here's the next baddie.
What we need to achieve:
Iterate through unfinished solution grids
Iterate through internal cells
If internal cell is empty, we could place either mirror, or leave it empty.
We achieve this through use of a stack of solutions.
Now we have all our "finished" solution grids
We can now determine the corresponding light pathways
And corresponding border cell values
"""
def dfs_finish_the_solutions(solutions):
"""
We're doing another depth-first search, baby!
Iterate through solution grids
Iterate through internal cells
If internal cell empty, copy grid three times.
Place "F", "B", "o" in each of these grids
Add to stack of solution grids
If no internal cells empty:
Iterate through border cells
If border cell is empty
Determine light pathway
Add numbers to border
Add to final_solution_grids
Iterate through final solution grids
Calculate border sum
Calculate product_of_border sums
Append to list of final solutions
"""
#solutions_temp = []
final_solutions = []
answer = []
while solutions:
grid, path = solutions.pop()
rows, cols = len(grid), len(grid[0])
#solutions_temp.append([grid, path])
# If we have any empty cells - valid solutions would be F, B or empty.
# Iterate through all cells in grid. If empty cell, update to F, append to stack. Update to B, append to stack. Return cell to empty.
for j in range(1, rows - 1):
for k in range(1, cols - 1):
if grid[j][k] == "": # Check if the cell is empty
grid[j][k] = "F"
solutions.append([ [row[:] for row in grid], path ]) # Proper copy
grid[j][k] = "B"
solutions.append([ [row[:] for row in grid], path ]) # Proper copy
grid[j][k] = "o" # Revert back
# For the current solution with empty cells, we can now start calculating the remaining light pathways.
for i in range(1, cols - 1): # Top border
if grid[0][i] == "":
grid, path = draw_new_light_path(grid, path, (0, i))
for i in range(1, cols - 1):
if grid[rows - 1][i] == "":
grid, path = draw_new_light_path(grid, path, (rows - 1, i))
for i in range(1, rows - 1):
if grid[i][0] == "":
grid, path = draw_new_light_path(grid, path, (i, 0))
for i in range(1, rows - 1):
if grid[i][cols - 1] == "":
grid, path = draw_new_light_path(grid, path, (i, cols - 1))
answer.append(calculate_sum_product_of_borders(grid))
#final_solutions.append([grid, path, answer])
final_solutions.append([grid, path])
return final_solutions, answer
# Iterate over the border and look for an empty cell.
# If so, fill with a light path.
In [44]:
"""
EXAMPLE PART 4 FINAL
Now we run the new DFS to fill in the unknown cells, and...
Voila!
We now have four solutions, and corresponding answers.
Next I'll run you through the actual solution which finds 28 unique solutions.
"""
print("EXAMPLE PART 4 FINAL")
print("")
solutions_temp = copy.deepcopy(solutions[-1])
example_solutions, example_answers = dfs_finish_the_solutions(solutions_temp)
print(f"Number of answers found: ", len(example_answers))
print(f"Answers: ", example_answers)
print("")
print("Notice how we previously had two solutions, and now we have four.")
print(" This is because we considered placing a mirror in the empty cell of the first solution, creating three solutions from one.")
print("")
print("This is the end of the examples. Next I move on to the real solution.")
display_solutions(example_solutions)
print("End of example.")
EXAMPLE PART 4 FINAL Number of answers found: 4 Answers: [601931086080, 578609323776, 576363666480, 582246656016] Notice how we previously had two solutions, and now we have four. This is because we considered placing a mirror in the empty cell of the first solution, creating three solutions from one. This is the end of the examples. Next I move on to the real solution.
End of example.
In [45]:
"""
TWENTY-EIGHT SOLUTIONS: PART 1
Total Solution Runtime: 5 minutes
Part 1 Runtime: 2 minutes
I start by running at relatively low depths, generally based on intuition
I find a total of 6 valid solutions.
These probably aren't all the possible valid solutions, though.
In the next step I will improve run speed and search depth substantially, by adding further constraints to the grid.
"""
print("TWENTY-EIGHT SOLUTIONS: PART 1")
print("")
steps = [
((0, 10), 2), # Step: 1
((11, 6), 2), # Step: 5
((2, 11), 3), # Step: 4
((8, 0), 3), # Step: 12 west
((0, 7), 4), # Step: 9
((7, 11), 4), # Step: 16
((4, 0), 5), # 27 West
((3, 11), 5), # 27 East
((11, 1), 8), # Step: 2025
((0, 6), 9), # Step: 3087 # Main candidate to expand
((9, 0), 7), # Step: 225
((11, 8), 7), # 405
((0, 3), 7), # Step: 112
((11, 4), 6), # Step: 12 south
((11, 5), 9), # Step: 64
((0, 5), 8), # Step: 48
]
grid = copy.deepcopy(starting_grid) # Prevent modification to starting_grid
solutions = [[[grid, []]]] # Note this is a list of list of lists of lists of f*cking lists!
processed_steps = 0
process_new_steps()
print("")
print("Print and displaying one solution.")
print("")
print_solutions([solutions[-1][0]])
display_solutions([solutions[-1][0]])
TWENTY-EIGHT SOLUTIONS: PART 1
Step count: 0 Solutions found: 1
Step count: 1 Solutions found: 1
Step count: 2 Solutions found: 2
Step count: 3 Solutions found: 4
Step count: 4 Solutions found: 16
Step count: 5 Solutions found: 66
Step count: 6 Solutions found: 274
Step count: 7 Solutions found: 511
Step count: 8 Solutions found: 19189
Step count: 9 Solutions found: 3920
Step count: 10 Solutions found: 1085
Step count: 11 Solutions found: 114
Step count: 12 Solutions found: 45
Step count: 13 Solutions found: 41
Step count: 14 Solutions found: 30
Step count: 15 Solutions found: 6
Print and displaying one solution.
Solution 1:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
27 | o | o | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
| F | o | o | o | F | o | o | F | o | o | 27
27 | o | o | F | o | o | o | o | o | o | B | 9
112 | o | o | o | o | o | o | F | o | o | o | 64
| o | F | o | o | B | o | o | B | o | o | 27
48 | F | o | B | o | o | F | o | o | F | o | 16
12 | o | o | o | B | o | o | o | o | o | o |
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | 225 | | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 1: [[(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(4, 0), (4, 3), (1, 3), (1, 0)], [(3, 11), (3, 8), (6, 8), (6, 11)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (6, 5), (6, 2), (11, 2)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (5, 7), (5, 0)], [(11, 4), (8, 4), (8, 0)], [(11, 5), (9, 5), (9, 7), (5, 7), (5, 11)], [(0, 5), (3, 5), (3, 1), (7, 1), (7, 0)]]
--------------------------------------------------
In [46]:
"""
TWENTY-EIGHT SOLUTIONS: PART 2
Part 2 Runtime: 2 min
Might there be more solutions?
Based on patterns in the last set of solutions, I constrain the grid manually.
This allows us to search at a greater depth.
I now find 14 solutions.
"""
print("TWENTY-EIGHT SOLUTIONS: PART 2")
print("")
constrained_grid_1 = [
['', '', '', 112, '', 48, 3087, 9, 405, 4, 1, ''],
['', '', '', 'B', 'o', 'o', 'o', '', 'o', 'o', 'B', 1],
['', '', '', '', '', 'o', 'o', '', '', 'B', 'o', 4],
['', '', '', '', '', '', 'o', '', 'F', 'o', 'o', 27],
[27, 'o', 'o', '', '', '', 'o', '', 'o', '', '', ''],
['', '', '', '', '', '', 'o', '', 'o', '', '', ''],
['', '', '', '', '', '', 'o', '', 'B', 'o', 'o', 27],
['', '', '', '', '', '', '', '', '', '', 'o', 16],
[12, 'o', 'o', 'o', 'B', '', '', '', '', '', '', ''],
[225, '', '', '', 'o', 'F', 'o', '', '', '', '', ''],
['', '', '', '', 'o', 'o', 'F', 'o', 'o', 'o', 'o', 5],
['', 2025, '', '', 12, 64, 5, 16, 405, '', '', '']
]
print("constrained_grid")
print_grid(constrained_grid_1)
steps = [
((0, 7), 8), # Step: 9
((7, 11), 9), # Step: 16
((11, 1), 12), # Step: 2025
((0, 6), 12), # Step: 3087
((9, 0), 12), # Step: 225
((11, 8), 12), # 405
((0, 3), 12), # Step: 112
((11, 5), 10), # Step: 64
((4, 0), 12), # 27 West
((0, 5), 10), # Step: 48
# Note the following steps are already "solved" in the constraints.
# I include these steps in order to draw the light pathways on our solution grids.
((0, 10), 2), # Step: 1
((11, 6), 2), # Step: 5
((2, 11), 3), # Step: 4
((8, 0), 2), # Step: 12 west
((3, 11), 3), # 27 East
]
grid = copy.deepcopy(constrained_grid_1) # Prevent modification to constrained_grid
solutions = [[[grid, []]]]
processed_steps = 0
process_new_steps()
print("")
print("Printing all 14 solutions.")
print("")
print_solutions(solutions[-1])
TWENTY-EIGHT SOLUTIONS: PART 2
constrained_grid
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| | | B | o | o | o | | o | o | B | 1
| | | | | o | o | | | B | o | 4
| | | | | | o | | F | o | o | 27
27 | o | o | | | | o | | o | | |
| | | | | | o | | o | | |
| | | | | | o | | B | o | o | 27
| | | | | | | | | | o | 16
12 | o | o | o | B | | | | | | |
225 | | | | o | F | o | | | | |
| | | | o | o | F | o | o | o | o | 5
| 2025 | | | 12 | 64 | 5 | 16 | 405 | | |
Step count: 0 Solutions found: 5
Step count: 1 Solutions found: 302
Step count: 2 Solutions found: 47353
Step count: 3 Solutions found: 11829
Step count: 4 Solutions found: 4251
Step count: 5 Solutions found: 1200
Step count: 6 Solutions found: 265
Step count: 7 Solutions found: 46
Step count: 8 Solutions found: 35
Step count: 9 Solutions found: 14
Step count: 10 Solutions found: 14
Step count: 11 Solutions found: 14
Step count: 12 Solutions found: 14
Step count: 13 Solutions found: 14
Step count: 14 Solutions found: 14
Printing all 14 solutions.
Solution 1:
| | 48 | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| F | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
27 | B | F | B | o | F | o | o | F | o | o | 27
27 | o | o | F | o | o | o | o | o | o | B | 9
112 | o | o | o | o | o | o | F | o | o | o | 64
| B | F | o | o | B | o | o | B | o | o | 27
| | o | B | o | o | F | o | o | F | o | 16
12 | o | o | o | B | o | o | o | o | o | o |
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | 225 | | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 1: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (6, 5), (6, 2), (11, 2)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (5, 7), (5, 0)], [(11, 5), (9, 5), (9, 7), (5, 7), (5, 11)], [(4, 0), (4, 3), (3, 3), (3, 2), (6, 2), (6, 1), (3, 1), (3, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 1), (1, 1), (1, 2), (0, 2)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 2:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
48 | B | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
27 | B | F | B | o | F | o | o | F | o | o | 27
27 | o | o | F | o | o | o | o | o | o | B | 9
112 | o | o | o | o | o | o | F | o | o | o | 64
| B | F | o | o | B | o | o | B | o | o | 27
| | o | B | o | o | F | o | o | F | o | 16
12 | o | o | o | B | o | o | o | o | o | o |
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | 225 | | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 2: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (6, 5), (6, 2), (11, 2)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (5, 7), (5, 0)], [(11, 5), (9, 5), (9, 7), (5, 7), (5, 11)], [(4, 0), (4, 3), (3, 3), (3, 2), (6, 2), (6, 1), (3, 1), (3, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 1), (1, 1), (1, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 3:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
27 | o | o | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
| F | o | o | o | F | o | o | F | o | o | 27
27 | o | o | F | o | o | o | o | o | o | B | 9
112 | o | o | o | o | o | o | F | o | o | o | 64
| o | F | o | o | B | o | o | B | o | o | 27
48 | F | o | B | o | o | F | o | o | F | o | 16
12 | o | o | o | B | o | o | o | o | o | o |
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | 225 | | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 3: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (6, 5), (6, 2), (11, 2)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (5, 7), (5, 0)], [(11, 5), (9, 5), (9, 7), (5, 7), (5, 11)], [(4, 0), (4, 3), (1, 3), (1, 0)], [(0, 5), (3, 5), (3, 1), (7, 1), (7, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 4:
| 225 | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| o | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
48 | o | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
| B | o | o | B | o | o | o | o | o | o |
| | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 4: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (0, 1)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 5:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| F | o | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
48 | F | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
| F | o | o | B | o | o | o | o | o | o |
| B | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | 225 | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 5: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (6, 1), (6, 2), (11, 2)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 1), (3, 1), (3, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 6:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
| F | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
48 | F | o | o | B | o | o | o | o | o | o |
| B | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | 225 | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 6: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (6, 1), (6, 2), (11, 2)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 1), (5, 1), (5, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 7:
| | 48 | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| F | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
| B | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
| F | o | o | B | o | o | o | o | o | o |
| B | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | 225 | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 7: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (6, 1), (6, 2), (11, 2)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 1), (1, 1), (1, 2), (0, 2)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 8:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
48 | B | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
| B | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
| F | o | o | B | o | o | o | o | o | o |
| B | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | 225 | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 8: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (6, 1), (6, 2), (11, 2)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 1), (1, 1), (1, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 9:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
48 | o | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
| F | o | o | B | o | o | o | o | o | o |
| B | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
| F | o | o | o | o | F | o | o | o | o | 5
| 2025 | 225 | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 9: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (6, 1), (6, 2), (11, 2)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 10:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| F | o | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
48 | F | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
| F | o | o | B | o | o | o | o | o | o |
| o | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
225 | F | o | o | o | o | F | o | o | o | o | 5
| 2025 | | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 10: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (10, 1), (10, 0)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 1), (3, 1), (3, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 11:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
| F | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
48 | F | o | o | B | o | o | o | o | o | o |
| o | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
225 | F | o | o | o | o | F | o | o | o | o | 5
| 2025 | | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 11: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (10, 1), (10, 0)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 1), (5, 1), (5, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 12:
| | 48 | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| F | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
| B | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
| F | o | o | B | o | o | o | o | o | o |
| o | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
225 | F | o | o | o | o | F | o | o | o | o | 5
| 2025 | | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 12: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (10, 1), (10, 0)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 1), (1, 1), (1, 2), (0, 2)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 13:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
48 | B | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
| B | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
| F | o | o | B | o | o | o | o | o | o |
| o | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
225 | F | o | o | o | o | F | o | o | o | o | 5
| 2025 | | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 13: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (10, 1), (10, 0)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 1), (1, 1), (1, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
Solution 14:
| | | 112 | | 48 | 3087 | 9 | 405 | 4 | 1 |
| | F | B | o | o | o | B | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
48 | o | F | B | o | F | o | o | F | o | o | 27
27 | o | o | B | o | o | o | o | o | o | B | 9
| F | o | o | B | o | o | o | o | o | o |
| o | B | o | o | B | o | o | B | o | o | 27
27 | o | o | F | o | B | F | o | o | F | o | 16
12 | o | o | o | B | B | o | B | o | o | o | 112
225 | o | o | o | o | F | o | F | o | F | o |
225 | F | o | o | o | o | F | o | o | o | o | 5
| 2025 | | 64 | 12 | 64 | 5 | 16 | 405 | | 3087 |
Paths for Solution 14: [[(0, 7), (1, 7), (1, 10), (4, 10), (4, 11)], [(7, 11), (7, 9), (9, 9), (9, 7), (11, 7)], [(11, 1), (10, 1), (10, 6), (7, 6), (7, 9), (2, 9), (2, 0)], [(0, 6), (7, 6), (7, 5), (6, 5), (6, 2), (3, 2), (3, 3), (4, 3), (4, 10), (11, 10)], [(9, 0), (9, 5), (8, 5), (8, 4), (5, 4), (5, 1), (10, 1), (10, 0)], [(11, 8), (6, 8), (6, 5), (3, 5), (3, 8), (0, 8)], [(0, 3), (1, 3), (1, 7), (8, 7), (8, 11)], [(11, 5), (9, 5), (9, 7), (8, 7), (8, 5), (7, 5), (7, 3), (11, 3)], [(4, 0), (4, 3), (7, 3), (7, 0)], [(0, 5), (3, 5), (3, 3), (1, 3), (1, 2), (3, 2), (3, 0)], [(0, 10), (1, 10), (1, 11)], [(11, 6), (10, 6), (10, 11)], [(2, 11), (2, 9), (0, 9)], [(8, 0), (8, 4), (11, 4)], [(3, 11), (3, 8), (6, 8), (6, 11)]]
--------------------------------------------------
In [47]:
"""
TWENTY-EIGHT SOLUTIONS: PART 3
Part 3 Runtime: 10 seconds
Adjusting our constraints again.
3087 end position fixed, 2025 full pathway fixed.
Removed the corner 12 constraint.
Search depths are effectively unlimited.
"""
print("TWENTY-EIGHT SOLUTIONS: PART 3")
print("")
print("Constrained Grid")
constrained_grid_2 = [
['', '', '', 112, '', 48, 3087, 9, '', 4, 1, ''],
['', '', '', 'B', 'o', 'o', 'o', '', 'o', 'o', 'B', 1],
[2025, 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'B', 'o', 4],
['', '', '', '', '', '', 'o', '', '', 'o', '', 27],
[27, 'o', 'o', '', 'o', 'o', 'o', 'o', 'o', 'o', 'B', ''],
['', '', '', '', '', '', 'o', '', '', 'o', 'o', ''],
['', '', '', '', '', '', 'o', '', '', 'o', 'o', ''],
['', '', '', '', '', '', 'F', 'o', 'o', 'F', 'o', 16],
[12, '', '', '', '', '', 'o', '', '', '', 'o', ''],
[225, '', '', '', '', 'F', 'o', '', '', '', 'o', ''],
['', 'F', 'o', 'o', '', 'o', 'F', 'o', 'o', 'o', 'o', 5],
['', 2025, '', '', 12, 64, 5, 16, 405, '', 3087, '']
]
print_grid(constrained_grid_2)
steps = [
((0, 7), 12), # Step: 9
((7, 11), 12), # Step: 16
((0, 6), 16), # Step: 3087
((9, 0), 14), # Step: 225
((3, 11), 12), # 27 East
((11, 8), 14), # 405
((0, 3), 14), # Step: 112
((11, 5), 14), # Step: 64
((4, 0), 14), # 27 West
((0, 5), 14), # Step: 48
((11, 4), 12), # Step: 12 south
((8, 0), 12), # Step: 12 west
# Note the following steps are already "solved" in the constraints.
# I include these steps in order to draw the light pathways on our solution grids.
((0, 10), 2), # Step: 1
((11, 6), 2), # Step: 5
((2, 11), 3), # Step: 4
((11, 1), 8), # Step: 2025
]
grid = copy.deepcopy(constrained_grid_2) # Prevent modification to constrained_grid
solutions = [[[grid, []]]] # Note this is a list of list of lists of lists of f*cking lists!
processed_steps = 0 # Track how many steps have been processed
process_new_steps()
print("I have turned off prints - the fourteen solutions are identical to Part 2.")
#display_solutions(solutions[-1])
#print_solutions(solutions[-1])
TWENTY-EIGHT SOLUTIONS: PART 3
Constrained Grid
| | | 112 | | 48 | 3087 | 9 | | 4 | 1 |
| | | B | o | o | o | | o | o | B | 1
2025 | o | o | o | o | o | o | o | o | B | o | 4
| | | | | | o | | | o | | 27
27 | o | o | | o | o | o | o | o | o | B |
| | | | | | o | | | o | o |
| | | | | | o | | | o | o |
| | | | | | F | o | o | F | o | 16
12 | | | | | | o | | | | o |
225 | | | | | F | o | | | | o |
| F | o | o | | o | F | o | o | o | o | 5
| 2025 | | | 12 | 64 | 5 | 16 | 405 | | 3087 |
Step count: 0 Solutions found: 3
Step count: 1 Solutions found: 140
Step count: 2 Solutions found: 4752
Step count: 3 Solutions found: 7143
Step count: 4 Solutions found: 4501
Step count: 5 Solutions found: 1900
Step count: 6 Solutions found: 657
Step count: 7 Solutions found: 285
Step count: 8 Solutions found: 213
Step count: 9 Solutions found: 52
Step count: 10 Solutions found: 15
Step count: 11 Solutions found: 14
Step count: 12 Solutions found: 14
Step count: 13 Solutions found: 14
Step count: 14 Solutions found: 14
Step count: 15 Solutions found: 14
I have turned off prints - the fourteen solutions are identical to Part 2.
In [48]:
def report_duplicates(list):
"""
On inspection, while all solution grids are unique, the final answer (border product sum) may not be.
This is a quick function to report which of our answers are duplicates.
"""
seen = {}
duplicates = []
for index, value in enumerate(list):
if value in seen:
duplicates.append((index, seen[value]))
else:
seen[value] = index
return duplicates
In [49]:
"""
TWENTY-EIGHT SOLUTIONS: PART 4 FINAL
The Twenty-Two Answers
Runtime: 5 sec
I've found 14 solutions twice, now.
I ran a quick script to verify all solutions are unique, and all previously-found solutions are accounted for.
I could play with more constraints, but I'm tired.
Let's solve for final solutions.
"""
print("TWENTY-EIGHT SOLUTIONS: PART 4 FINAL")
print("Twenty-Two Unique Answers:")
print("")
final_solutions_temp = copy.deepcopy(solutions[-1])
final_solutions, answers = dfs_finish_the_solutions(final_solutions_temp)
print(f"Total number of answers & solutions found: ", len(answers))
print(f"Answers sorted smallest to largest: ", sorted(answers))
duplicates = report_duplicates(answers)
print(f"Number of unique answers found: ", len(answers) - len(duplicates))
print(f"Unique answers sorted smallest to largest: ", sorted(list(set(answers))))
print("")
# Check our answers are unique
#if len(answers) == len(set(answers)):
# print("All answers are unique")
#else:
# print("Duplicate answers found: look closer")
print("Duplicates:")
for dup, original in duplicates:
print(f"Answers {dup+1} and {original+1}")
"""
Why do we have duplicate answers?
Comparing answers 1 and 7: We can see borders hold values (1,6) vs (2,5), which will result in the same border product sum.
Comparing answers 3 and 6: We see that 48 has actually taken a completely different pathway to the same border, yet results in the same answer.
"""
print("""
Jane Street Puzzle
March 2025: Hall of Mirrors 3
Twenty-eight solutions
By Kauri Beckmann
kauri.b@outlook.co.nz
18/03/2025
""")
print("")
for i in range(len(final_solutions)):
print(f"Solution ", (i+1), " of ", len(final_solutions))
print(f"Answer ", (i+1), " of ", len(final_solutions), " : ", answers[i])
display_solutions([final_solutions[i]])
print("End.")
TWENTY-EIGHT SOLUTIONS: PART 4 FINAL Twenty-Two Unique Answers: Total number of answers & solutions found: 28 Answers sorted smallest to largest: [576363666480, 578609323776, 582246656016, 601931086080, 617381715456, 617381715456, 618473003076, 618550999008, 620976126640, 621828794436, 621828794436, 623431751360, 625189829220, 625189829220, 627387030704, 640451222002, 640451222002, 641546478474, 641612783238, 645034845780, 645034845780, 648461819786, 648461819786, 667255198260, 693717276948, 869902731720, 874155869246, 877730411052] Number of unique answers found: 22 Unique answers sorted smallest to largest: [576363666480, 578609323776, 582246656016, 601931086080, 617381715456, 618473003076, 618550999008, 620976126640, 621828794436, 623431751360, 625189829220, 627387030704, 640451222002, 641546478474, 641612783238, 645034845780, 648461819786, 667255198260, 693717276948, 869902731720, 874155869246, 877730411052] Duplicates: Answers 6 and 3 Answers 7 and 1 Answers 9 and 2 Answers 15 and 12 Answers 16 and 10 Answers 18 and 11 Jane Street Puzzle March 2025: Hall of Mirrors 3 Twenty-eight solutions By Kauri Beckmann kauri.b@outlook.co.nz 18/03/2025 Solution 1 of 28 Answer 1 of 28 : 648461819786
Solution 2 of 28 Answer 2 of 28 : 645034845780
Solution 3 of 28 Answer 3 of 28 : 640451222002
Solution 4 of 28 Answer 4 of 28 : 641612783238
Solution 5 of 28 Answer 5 of 28 : 693717276948
Solution 6 of 28 Answer 6 of 28 : 640451222002
Solution 7 of 28 Answer 7 of 28 : 648461819786
Solution 8 of 28 Answer 8 of 28 : 641546478474
Solution 9 of 28 Answer 9 of 28 : 645034845780
Solution 10 of 28 Answer 10 of 28 : 625189829220
Solution 11 of 28 Answer 11 of 28 : 621828794436
Solution 12 of 28 Answer 12 of 28 : 617381715456
Solution 13 of 28 Answer 13 of 28 : 618473003076
Solution 14 of 28 Answer 14 of 28 : 667255198260
Solution 15 of 28 Answer 15 of 28 : 617381715456
Solution 16 of 28 Answer 16 of 28 : 625189829220
Solution 17 of 28 Answer 17 of 28 : 618550999008
Solution 18 of 28 Answer 18 of 28 : 621828794436
Solution 19 of 28 Answer 19 of 28 : 874155869246
Solution 20 of 28 Answer 20 of 28 : 869902731720
Solution 21 of 28 Answer 21 of 28 : 877730411052
Solution 22 of 28 Answer 22 of 28 : 623431751360
Solution 23 of 28 Answer 23 of 28 : 620976126640
Solution 24 of 28 Answer 24 of 28 : 627387030704
Solution 25 of 28 Answer 25 of 28 : 578609323776
Solution 26 of 28 Answer 26 of 28 : 576363666480
Solution 27 of 28 Answer 27 of 28 : 582246656016
Solution 28 of 28 Answer 28 of 28 : 601931086080
End.