A chain is an orthogonally connected group of stones of the same color.
Here is a position with 6 chains, no two of which are of the same size:
Here is a position with 4 black chains, no two of which are of the same size:
Is a single stone (1 in both diagrams) a chain?
Don’t have time to think about it now but if a solution to problem 1 exists, then chains must have lengths 1,2,…, 12. There would be 3 remaining free intersections, and each free intersection should be a common liberty of 4 chains. I don’t know yet if that’s possible or not.
Yes, a single stone is a chain!
If a single stone is a chain, your definition of a chain (connected group of stones; that is 2 plurals) is confusing, to say the least.
So, can you explain why a single stone is a chain?
Perhaps the definition from Sensei’s library is more clearly worded:
A chain consists of one stone together with all stones strictly connected to that stone (and only those).
Very similar (but different) puzzle
Very helpful.
I was thinking about how the 1 chain has to be in a funny snap back like shape.
Example
Very nice!
Here is my solution for comparison:
I can confirm that the other puzzle is also possible, though it is probably a bit harder!
I think I’m more stumbling around and making it work than finding a principle, other than probably it’s too big to leave gaps of size 3 or more. Except I imagine the two piece has to fit snugly in the corner 
Nice! Yep I was also just stumbling around:
Open question: Is it possible to place 9 black chains of different sizes on an 8x8 board? It seems to be either just barely possible or just barely impossible. This is the closest I was able to get so far:
This one looks very difficult, not a lot of room to manoeuvre.
I’m not sure if I’ll figure it out accidentally, but my feeling is that since you have to be very efficient it might be forced to have shapes like 2, 3, 4 and 6 stuck in corners, as at least the 7, 8, 9 shapes have a few clumpy shapes that bend around others.
^^ Here’s just the one chain missing for example.
I remember @antonTobi talking about simulated annealing approaches before to problems like these
and one could imagine taking a template like
and doing some Monte Carlo method to randomly add or take away stones in a checkerboard like pattern but keeping like the triangles stones fixed.
For example you can get another similar one that almost works (8 groups) as it’s missing the one stone
It’s also relatively easy to do by hand this way
You can imagine a similar template like
with the triangle stones fixed, but it leaves an extra gap beside the two stones in the corner.
The method kind of enforced the bulkiness on the shape, by trying to retain a certain checkerboard like pattern.
I think the bulkiness is basically following a staircase pattern on the outside of the shape, vertical horizontal alternating, whenever you’re not bordering an edge or the space touching the two size piece.
For some reason I read that as Shel Silverstein?
I’ve never used simulated annealing myself before, so I asked ChatGPT to do it for me. It did a bit better than I expected! The solutions are not good but the basic logic seems to be working.
Note that a chain is often called a string. Linked strings are called groups.
I tweaked it a bit for the 8x8 puzzle, tweaked the initial state and tweaking the score to try to force it to pick 9 groups, with 9 sizes, and certain numbers of empty space etc. Then run it on a loop for a while.
-3*abs(max(sizes) - 9 ) ** 2 - 3*abs(len(chains) - 9) ** 2 - 3*abs(unique_sizes - 9) ** 2 - abs(empty - 19) - abs(full - 45)
where the idea is that the theorized solution has groups 1,2,…, 9 which has max size 9, 9 chains, 9 unique sizes, and then 45 occupied spaces and 19 empty spaces.
It’s not there of course, but not terrible
Might play some more with it in a bit.
Sure if we’re vibe coding anyway 
I asked gemini to do it efficiently and it took a few prompts but:
import random
import math
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
from collections import deque
from tqdm import tqdm
custom_board_1 = [
[True, False, True, False, True, False, True, True],
[False, True, False, True, False, True, False, True],
[True, False, True, False, True, False, True, False],
[False, True, False, True, False, True, False, True],
[True, False, True, False, True, False, True, False],
[True, True, False, True, False, True, False, True],
[False, False, True, False, True, False, True, False],
[True, True, False, True, False, True, False, True]
]
fixed_1_mask = [[False]*8,
[False]*8,
[False]*8,
[False]*8,
[False]*8,
[True, True, False, False, False, False, False, False],
[True, True, True, False, False, False, False, False],
[True, True, True, True, False, False, False, False]
]
custom_board_2 = [
[True, True, False, True, False, True, False, True],
[True, False, True, False, True, False, True, False],
[False, True, False, True, False, True, False, True],
[True, False, True, False, True, False, True, False],
[True, True, False, True, False, True, False, True],
[False, True, True, False, True, False, True, False],
[True, False, False, True, False, True, False, True],
[False, True, True, False, True, False, True, True]
]
fixed_1 = [r for r in zip(np.nonzero(fixed_1_mask)[0],np.nonzero(fixed_1_mask)[1])]
custom_board_3 = [
[True, True, True, False, True, False, True, True],
[True, True, False, True, False, True, False, True],
[True, False, True, False, True, False, True, False],
[False, True, False, True, False, True, False, True],
[True, False, True, False, True, False, True, False],
[True, True, False, True, False, True, False, True],
[False, False, True, False, True, False, True, True],
[True, True, False, True, False, True, True, True]
]
custom_board_4 = [
[True, True, True, False, True, True, True, True],
[True, True, False, True, False, True, True, True],
[True, False, True, False, True, False, True, True],
[False, True, False, True, False, True, False, True],
[True, False, True, False, True, False, True, False],
[True, True, False, True, False, True, False, True],
[False, False, True, False, True, False, True, True],
[True, True, False, True, False, True, True, True]
]
class GoBoardPuzzleSA:
def __init__(self, board_size=8, target_groups=9, target_sizes=range(1, 10), target_total_stones=45):#,fixed=[]):
self.board_size = board_size
self.target_groups = target_groups
self.target_sizes = set(target_sizes)
self.target_total_stones = target_total_stones
#self.fixed = fixed
def _get_black_groups(self, board):
visited = np.zeros_like(board, dtype=bool)
groups = []
for r in range(self.board_size):
for c in range(self.board_size):
if board[r, c] and not visited[r, c]:
group = []
q = deque([(r, c)])
visited[r, c] = True
group.append((r, c))
while q:
row, col = q.popleft()
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = row + dr, col + dc
if 0 <= nr < self.board_size and 0 <= nc < self.board_size and \
board[nr, nc] and not visited[nr, nc]:
visited[nr, nc] = True
group.append((nr, nc))
q.append((nr, nc))
groups.append(tuple(sorted(group)))
return tuple(sorted(groups))
def _calculate_energy(self, board):
groups = self._get_black_groups(board)
num_groups = len(groups)
group_sizes = set(len(g) for g in groups)
total_stones = np.sum(board)
energy = 0
# Penalty for not having the target number of groups
energy += abs(num_groups - self.target_groups) * 30
# Penalty for not having the target group sizes
energy += len(self.target_sizes.symmetric_difference(group_sizes)) * np.prod(list(self.target_sizes.symmetric_difference(group_sizes)))
# Penalty for not having the target total number of stones
energy += abs(total_stones - self.target_total_stones) * 10
# Bonus for having the exact target configuration (0 energy is ideal)
if num_groups == self.target_groups and group_sizes == self.target_sizes and total_stones == self.target_total_stones:
return 0
return energy
def _get_neighbor(self, board):
new_board = np.copy(board)
empty_spaces = [(r, c) for r in range(self.board_size) for c in range(self.board_size) if not new_board[r, c]]
black_stones = [(r, c) for r in range(self.board_size) for c in range(self.board_size) if new_board[r, c]]
if not empty_spaces and not black_stones:
return new_board
operation = random.choice(['add', 'remove'])
if operation == 'add' and empty_spaces:
r, c = random.choice(empty_spaces)
new_board[r, c] = True #^ ((r,c) in self.fixed)
elif operation == 'remove' and black_stones:
r, c = random.choice(black_stones)
new_board[r, c] = False #^ ((r,c) in self.fixed)
return new_board
def solve(self, temp_start=100, temp_end=0.1, cooling_rate=0.99, max_iterations=10000, initial_board=None):
if initial_board is None:
current_board = np.zeros((self.board_size, self.board_size), dtype=bool)
elif initial_board == 'checkerboard':
current_board = np.array([[bool((r + c) % 2) for c in range(self.board_size)] for r in range(self.board_size)])
else:
if np.array(initial_board).shape == (self.board_size, self.board_size) and np.array(initial_board).dtype == bool:
current_board = np.array(initial_board)
else:
print("Warning: Invalid custom initial board provided. Starting with an empty board.")
current_board = np.zeros((self.board_size, self.board_size), dtype=bool)
current_energy = self._calculate_energy(current_board)
best_board = np.copy(current_board)
best_energy = current_energy
temperature = temp_start
for i in range(max_iterations):
if temperature <= temp_end:
break
next_board = self._get_neighbor(current_board)
next_energy = self._calculate_energy(next_board)
delta_energy = next_energy - current_energy
acceptance_probability = 1.0
if delta_energy > 0:
acceptance_probability = math.exp(-delta_energy / temperature)
if random.random() < acceptance_probability:
current_board = next_board
current_energy = next_energy
if current_energy < best_energy:
best_energy = current_energy
best_board = np.copy(current_board)
# print(f"Iteration {i}, Temperature: {temperature:.2f}, Best Energy: {best_energy}")
if best_energy == 0:
print("Perfect solution found!")
return best_board, best_energy
temperature *= cooling_rate
# print(f"Run finished. Best Energy: {best_energy}")
return best_board, best_energy
def plot_board(self, board, ax=None, title="Go Board"):
if ax is None:
fig, ax = plt.subplots(figsize=(8, 8))
ax.set_xlim(-0.5, self.board_size - 0.5)
ax.set_ylim(-0.5, self.board_size - 0.5)
ax.set_xticks(range(self.board_size))
ax.set_yticks(range(self.board_size))
ax.grid(True, color='black', linewidth=1)
ax.set_xticklabels([])
ax.set_yticklabels([])
ax.invert_yaxis()
ax.set_aspect('equal')
ax.set_title(title)
groups = self._get_black_groups(board)
num_groups = len(groups)
colors = plt.cm.viridis(np.linspace(0, 1, num_groups))
for i, group in enumerate(groups):
color = colors[i]
for r, c in group:
circle = patches.Circle((c, r), radius=0.45, color=color, edgecolor='black')
ax.add_patch(circle)
ax.text(c, r, str(i + 1), ha='center', va='center', color='white', fontsize=8)
return ax
puzzle_sa = GoBoardPuzzleSA()
num_retries = 500
best_solution = None
best_energy_overall = float('inf')
total_energy = 0
for retry in tqdm(range(num_retries)):
# print(f"\n--- Retry {retry + 1} ---")
solution_board, final_energy = puzzle_sa.solve(max_iterations=10000, initial_board=custom_board_4)
# solution_board, final_energy = puzzle_sa.solve(max_iterations=10000, initial_board=[[True]*8]*8)
# solution_board, final_energy = puzzle_sa.solve(max_iterations=10000, initial_board='checkerboard')
# solution_board, final_energy = puzzle_sa.solve(max_iterations=10000)
total_energy += final_energy
if final_energy < best_energy_overall:
best_energy_overall = final_energy
best_solution = solution_board
print(f"Run finished. Best Energy: {best_energy_overall}")
if final_energy == 0:
print("\nPerfect solution found, breaking out of the loop.")
break
if best_solution is not None:
print("\n--- Best Result Across All Retries ---")
print(f"Best Energy: {best_energy_overall}")
fig, ax = plt.subplots(figsize=(8, 8))
puzzle_sa.plot_board(best_solution, ax=ax, title=f"Best SA Result (Energy: {best_energy_overall})")
plt.show()
final_groups = puzzle_sa._get_black_groups(best_solution)
final_group_sizes = sorted(len(g) for g in final_groups)
final_total_stones = np.sum(best_solution)
print("Final Number of Groups:", len(final_groups))
print("Final Group Sizes:", final_group_sizes)
print("Final Total Stones:", final_total_stones)
print("Average Energy:", total_energy/num_retries)
else:
print("Simulated Annealing failed to find any solution across multiple retries.")
I was doing tweaking here and there which I’ve left commented out in some cases. I was also tweaking the energy penalties for the different aspects, like how much it’s punished for not having exactly 9 groups, or exactly the sizes 1-9, or not having 45 stones.
It seems quite fast though, but doesn’t get there either, though it looks cool enough
Looks like it might get easier the larger you go for n+1 on the nxn board also because (n+1)(n+2)/2 = (n^2+3n+2) ~ n^2/2 for large n.
A solution for 10 on the 9x9 board using the code above (so it can sometimes find solutions at least ) I think the arrangement in this one is quite nice.
While going smaller you can’t have 5 on a 4x4 since 15=16-1 so that’s only one group.
6 on a 5x5 would be 21 stones on a 25 space board, which I think is at most 3 groups.
7 on a 6x6 is 28 out of 36. I’m not sure you can remove 8 stones to make more than 6 groups.
8 on 7x7 is 36 out of 49. 13 stones to work with seems better but maybe equally difficult or as impossibke as 9 on 8x8.
For fun, I wrote a C++ program that does exhaustive search with a whole bunch of pruning techniques that in theory are provably sound, if I implemented them right and reasoned about them correctly.
You can see very roughly documented in the source code what the pruning techniques are, each one is marked with a “PRUNING:” comment. Right now configurations are hardcoded in the main function, you comment in and out what you want and then re-compile.
I used 7x7 for a while as a testbed for performance benchmarking. It was kind of fun starting with only 2-3 basic pruning methods, and having it take 2-3 minutes to run in order to prove a 7x7 solution is impossible, and gradually as I made those pruning methods sharper and added more and more pruning methods, and then finally multithreading, to watch the time to prove impossibility go down and down and down. The original benchmark I started with that took 2-3 minutes to be proven impossible now takes only 0.7 seconds on my computer with 16 threads.
Anyways, when compiling with g++ -O3 -o regionsolver regionsolver.cpp and running it with 16 threads on my computer, here are some claimed results (if you trust that there aren’t any serious bugs. This might not be an entirely trustworthy assumption):
For reference, the completely naive exhaustive search without any further pruning or symmetry exploitation would for 7x7 be 49 choose 13 ~= 262 billion and for 8x8 would be 64 choose 19 ~= 8.7 quadrillion (or 8720 trillion, or 8720000 billion). So pruning methods are doing a lot of work here to cut those down to 13 million and 32 billion respectively.
I’m sure it’s possible to do even far better than this if one were to work more and optimize this seriously and think harder about better pruning.
