Riddler Express
The following \(8\)-by-\(8\) grid is covered with a total of \(64\) chess pieces, with one piece on each square. You should begin this puzzle at the white bishop on the green square. You can then move from white piece to white piece via the following rules:
If you are on a pawn, move up one space diagonally (left or right). If you are on a knight, move in an “L” shape — two spaces up, down, left or right, and then one space in a perpendicular direction. If you are on a bishop, move one space in any diagonal direction. If you are on a rook, move one space up, down, left or right. If you are on a queen, move one space in any direction (horizontal, vertical or diagonal). Chess board with 64 pieces on it. From left to right in each row, and then top to bottom, the pieces are (b = black, w = white:
For example, suppose your first move from the bishop is diagonally down and to the right. Now you’re at a white rook, so your possible moves are left or up to a pawn or right to a knight.
Your objective is to reach one of the four black kings on the grid. However, at no point can you land on any of the other black pieces. (Knights are allowed to hop over the black pieces.)
What sequence of moves will allow you to reach a king?
Computational Solution
Here is the Python code for solving the problem using directed graphs. Every square on the chessboard is a node. All squares that are reachable from any given square subject to the movement constraints of the piece on that square are neighbours of the given square. The neighbours of a square are connected by directed edges whose source is the original square and the destination is a neighbour. Given this representation, the above problem reduces to finding a directed path in the graph from the source(i.e. the green square) to the destination (i.e. one the sqares with a black king).
def moves(piece, i, j, size=8):
def is_valid(pos):
i,j = pos
return True if i >= 0 and i < size and j >= 0 and j < size else False
piece_moves = {
"p": [(i+1,j+1),(i-1,j+1)],
"b": [(i+1,j+1),(i-1,j+1),(i-1,j-1),(i+1,j-1)],
"r": [(i,j+1),(i-1,j),(i+1,j),(i,j-1)],
"h": [(i-1,j+2), (i+1,j+2), (i-1,j-2),(i+1,j-2),
(i-2,j-1), (i-2,j+1),(i+2,j-1),(i+2,j+1)],
"q": [(i,j+1),(i-1,j),(i+1,j),(i,j-1),(i+1,j+1),
(i-1,j+1),(i-1,j-1),(i+1,j-1)]
}
return list(filter(is_valid, piece_moves[piece]))
def paths(board, source, targets):
import networkx as nx
pieces = {}
for i, line in enumerate(reversed(board)):
for j, piece in enumerate(line):
pieces[(j,i)] = piece.strip()
G = nx.DiGraph()
for (i,j), piece in pieces.items():
if piece[0] == "w":
for move in moves(piece[1],i,j):
if pieces[move][0] == "w" or pieces[move] == "bk":
G.add_edge((i,j), move)
paths = []
for target in targets:
path = None
try:
path = nx.shortest_path(G, source, target)
except:
pass
if path:
paths.append(path)
return paths
board1 = [
["bk", "bb", "wb", "bb", "bk", "wr", "wb", "wr"],
["wh", "wr", "wh", "wh", "wp", "wh", "bk", "wb"],
["wr", "bp", "wh", "bh", "wp", "wr", "wp", "wr"],
["bp", "bb", "wp", "wr", "bh", "wh", "br", "bh"],
["wh", "wh", "wh", "wb", "br", "wb", "wr", "wb"],
["wq", "wr", "wh", "wp", "br", "wh", "wr", "wq"],
["bb", "br", "wr", "wp", "wb", "wp", "wb", "wq"],
["bk", "wb", "wq", "wh", "wp", "wr", "wh", "wh"]
]
print(paths(board1, (4,1), [(0,0),(0,7),(4,7),(6,6)]))
Riddler Classic
Today marks the beginning of the Summer Olympics! One of the brand-new events this year is sport climbing, in which competitors try their hands (and feet) at lead climbing, speed climbing and bouldering.
Suppose the event’s organizers accidentally forgot to place all the climbing holds on and had to do it last-minute for their \(10\)-meter wall (the regulation height for the purposes of this riddle). Climbers won’t have any trouble moving horizontally along the wall. However, climbers can’t move between holds that are more than \(1\) meter apart vertically.
In a rush, the organizers place climbing holds randomly until there are no vertical gaps between climbing holds (including the bottom and top of the wall). Once they are done placing the holds, how many will there be on average (not including the bottom and top of the wall)?
Extra credit: Now suppose climbers find it just as difficult to move horizontally as vertically, meaning they can’t move between any two holds that are more than \(1\) meter apart in any direction. Suppose also that the climbing wall is a \(10\)-by-\(10\) meter square. If the organizers again place the holds randomly, how many have to be placed on average until it’s possible to climb the wall?
Computational Solution 1
Start with an array \(\[0,height=10\]\) and repeatedly add uniform random values from \(\mathcal{U}[0, height]\) to this array (while keeping it \(\textbf{sorted}\)) until all consecutive differences are less than \(d=1\). Average length of the array across multiple runs gives us the average number of holds that need to be placed. From the simulation below we see that the average number of holds is \(\approx \textbf{43}\).
from random import uniform
def avg_holds_1d(height, d, runs = 10000):
sum_hold_cnts = 0
for _ in range(runs):
holds = [0, height]
while any([holds[i+1] - holds[i] > d for i in range(len(holds)-1)]):
new_hold = uniform(0, height)
i = 0
while holds[i] < new_hold:
i += 1
holds.insert(i, new_hold)
sum_hold_cnts += len(holds)-2
return sum_hold_cnts/runs
print(avg_holds_1d(10.0,1.0))Computational Solution 2
The computational trick to increase the speed of simulation is to use the \(\textbf{Union-Find}\) algorithm to keep track of all climbable paths (i.e. paths without any gaps) identified so far as new holds are randomly added. When we find a climbable path that contains the top and bottom holds, we stop the simulation run.
Using the simulation code below, we see that the average number of holds when there are no vertical gaps greater than \(1\)m is \(\approx\textbf{43}\) and the average number of holds when there are no gaps(in any direction) greater than \(1\)m is \(\approx\textbf{143}\).
from networkx.utils.union_find import UnionFind
from random import uniform
from math import sqrt
def dist(p1, p2):
return sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
def vdist(p1, p2):
return abs(p1[1]-p2[1])
def avg_holds(height, d, climb_type="1d", runs = 1000):
dist_fun = vdist if climb_type == "1d" else dist
sum_holds_cnt = 0
for _ in range(runs):
holds, top, bot, cnt = {}, 1, 2, 2
holds[top], holds[bot] = (0,0), (0,height)
climbable_paths = UnionFind()
climbable_paths.union(top)
climbable_paths.union(bot)
while True:
cnt, new_hold = cnt+1, (uniform(0, height), uniform(0,height))
for i, hold in holds.items():
if i == top or i == bot:
if vdist(hold, new_hold) <= d:
climbable_paths.union(i, cnt)
elif dist_fun(hold, new_hold) <= d:
climbable_paths.union(i, cnt)
climbable_paths.union(cnt)
holds[cnt] = new_hold
if climbable_paths[top]==climbable_paths[bot]:
break
sum_holds_cnt += cnt-2
return sum_holds_cnt/runs
print(avg_holds(10, 1, "1d"))
print(avg_holds(10, 1, "2d"))