# Break The Chain

You are given an $$\ 25 \times 25 \$$ square lattice graph. You are to remove certain nodes from the graph as to minimize your score, based on the following scoring system:

Your score will be the $$\ \text{number of nodes removed} \$$ $$\ + \$$ the $$\ \text{size of the largest connected component} \$$. In the smaller $$\ 4 \times 4 \$$ example below, exactly $$\ 5 \$$ nodes have been crossed out (removed), and the size of the largest connected component is $$\ 4 \$$ (top and left components). Therefore the total score is $$\ 9 \$$.

## Notes

• You should give your score alongside a list of crossed out nodes
• If a program was written to solve this problem, please include it in your answer if possible
• Here is a program to check your score

This is , so the minimum score wins!

• Out of curiosity, as someone not well versed in graph theory, is this equivalent to saying "Divide a 25x25 grid by placing obstacles in cells. Your score is the size of the largest contiguous area free of obstacles, plus the number of obstacles you placed"? Commented May 7, 2020 at 2:15
• @SteveBennett Yes, that is certainly another way to put it :) Commented May 7, 2020 at 2:40
• I sense an OEIS entry in this - Calculate the minimum scores for any NxN grid size. Proving optimality would be pretty challenging at higher N's though. Commented May 7, 2020 at 19:11

# 92+41=133

.......X.........X.......
........X.......X........
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
X.X.........X.........X.X
.X.X.......X.X.......X.X.
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
.X.X.......X.X.......X.X.
X.X.........X.........X.X
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
........X.......X........
.......X.........X.......


Now with 13 regions, all of 41.

# Previous version 93+46=139

X...........X...........X
.X..........X..........X.
..X.........X.........X..
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
XXX.........X.........XXX
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
..X.........X.........X..
.X..........X..........X.
X...........X...........X


8 regions of 46, 4 regions of 41.

• This looks like a spider web. I guess a spider is actually minimizing the size of the holes while using as little silk as possible. Commented May 5, 2020 at 17:00
• Why do I get 185 on this? Commented May 5, 2020 at 17:02
• @mypronounismonicareinstate I don't know. I count 46 for the largest region (there are 8 of them) and 93 X's, total 139. Commented May 5, 2020 at 17:07
• After a long examination, I found the problem: there's a cleverly hidden lowercase X. Commented May 5, 2020 at 17:16
• @mypronounismonicareinstate Edited. Thanks Commented May 5, 2020 at 17:18

# Lower bound: 114

Notation: Add 25 points to each side of the grid to produce a 27-by-27 grid with corners missing. Call these additional 100 points $$\\mathcal{E}\$$. Let $$\\mathcal{X}\$$ denote the set of deleted points. Say the $$\i\$$th component has $$\c_i\$$ points and is bounded by $$\x_i\$$ members of $$\\mathcal{X}\$$ and by $$\e_i\$$ members of $$\\mathcal{E}\$$.

Constraints: First, components that border $$\\mathcal{E}\$$ border disjoint subsets of $$\\mathcal{E}\$$, and so

$$\sum_i e_i \leq 100.$$

Next, consider the simple polygon with vertices/perimeter at the members of $$\\mathcal{X}\$$ and $$\\mathcal{E}\$$ that border the $$\i\$$th component. By Pick's theorem, the area of this polygon is

$$A_i=c_i + \frac{x_i + e_i}{2} - 1.$$

Meanwhile, the octagon with $$\\mathcal{E}\$$ as vertices/perimeter has area 674. As such,

$$\sum_i c_i + \sum_i\Big( \frac{ x_i + e_i }{2} - 1 \Big) = \sum_i A_i \leq 674.$$

Furthermore, it is conjectured (!) that

$$\frac{ x_i + e_i }{2} - 1 \geq \frac{1}{2}\Big\lceil \sqrt{8c_i-4}\Big\rceil.$$

Optimization: In our notation, we seek to minimize $$\|\mathcal{X}|+\max_i c_i\$$. It is convenient to write

$$|\mathcal{X}| = 625 - \sum_i c_i.$$

We may relax our optimization to only consider the above constraints:

$$\text{minimize} \quad 625 - \sum_i c_i + \max_i c_i$$ $$\text{subject to} \quad \sum_i e_i \leq 100, \quad \sum_i c_i + \sum_i\Big( \frac{ x_i + e_i }{2} - 1 \Big) \leq 674,$$ $$\frac{ x_i + e_i }{2} - 1 \geq \frac{1}{2}\Big\lceil \sqrt{8c_i-4}\Big\rceil, \quad x,c,e \geq 0.$$

The square root makes this optimization a pain, so we further relax to a sequence of linear programs. To accomplish this, we take

$$X_k := \sum_{i:c_i=k} x_i, \quad E_k := \sum_{i:c_i=k} e_i, \quad z_k := |\{i:c_i = k\}|, \quad C := \max_i c_i.$$

Then for each $$\C\in\{1,\ldots,133\}\$$, we solve the linear program

$$\text{minimize} \quad 625 - \sum_k kz_k + C$$ $$\text{subject to} \quad \sum_k E_k \leq 100, \quad \sum_k kz_k + \sum_k\Big( \frac{ X_k + E_k }{2} - z_k \Big) \leq 674,$$ $$\frac{ X_k + E_k }{2} - z_k \geq \frac{1}{2}\Big\lceil \sqrt{8k-4}\Big\rceil\cdot z_k, \quad X,E,z \geq 0.$$

Indeed, we only need to consider $$\C\leq 133\$$ thanks to the best known solution. Here's an implementation in MATLAB using CVX:

vals=[];
for C=1:133;
[C min(vals)]
w = ceil(sqrt(8*(1:C)-4))/2;
cvx_begin quiet
variable X(C)
variable E(C)
variable z(C)
minimize( 625 - (1:C)*z + C )
subject to
sum(E) <= 100
(1:C)*z + sum( (X+E)/2-z ) <= 674
for ii=1:C
(X(ii)+E(ii))/2-z(ii) >= w(ii)*z(ii)
end
X >= 0
E >= 0
z >= 0
cvx_end
vals(end+1)=cvx_optval;
end


The minimum value of 113.32 occurs when $$\C=41\$$. (Curiously, this is the size of the components in the best known solution.) Here's a plot of how the minimum varies with $$\C\$$:

## Score 80 + 61 = 141

........X...........X....
.......X.............X...
........X...........X....
.X.......X.........X.....
X.X.......X.......X......
...X.......X.....X.......
....X.......X...X........
.....X.....X.X.X.......X.
......X...X...X.......X.X
.......X.X.....X.....X...
........X.......X...X....
.......X.........X.X.....
......X...........X......
.....X.X.........X.......
....X...X.......X........
...X.....X.....X.X.......
X.X.......X...X...X......
.X.......X.X.X.....X.....
........X...X.......X....
.......X.....X.......X...
......X.......X.......X.X
.....X.........X.......X.
....X...........X........
...X.............X.......
....X...........X........


Found with the help of this program which tells you the number of Xs and the size of each area of .s.

## Previous score 89 + 54 = 143

....X...............X....
.....X.............X.....
......X...........X......
.......X.........X.......
........X...X...X........
.........XXX.XXX.........
........X.......X........
.......X.........X.......
XXXXXXX...........XXXXXXX
.......X.........X.......
.......X.........X.......
........X.......X........
.........XXXXXXX.........
........X.......X........
.......X.........X.......
.......X.........X.......
XXXXXXX...........XXXXXXX
.......X.........X.......
........X.......X........
.........XXX.XXX.........
........X...X...X........
.......X.........X.......
......X...........X......
.....X.............X.....
....X...............X....

• It's pretty. :) Commented May 7, 2020 at 2:12

# C++, score 147

Adding simulated annealing has changed the results very significantly. They are now extremely worrying.

The code:

//#define _GLIBCXX_DEBUG
#include <x86intrin.h>
#include <iostream>
#include <streambuf>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <random>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <unordered_set>

std::mt19937_64 mt;
int N = 25;
std::vector<char> cuts(N*N);
std::vector<char> marks;
int dfs(int at)
{
char x = at % N, y = at / N;
marks[at] = true;
int sz = 1;
static const char ddx[4] {1, -1, 0, 0};
static const char ddy[4] {0, 0, 1, -1};
for(int d = 0; d < 4; d++)
{
int dx = ddx[d], dy = ddy[d];
int nx = x + dx, ny = y + dy;
if(nx < 0 || ny < 0 || ny >= N || nx >= N) continue;
if(marks[ny * N + nx]) continue;
sz += dfs(ny * N + nx);
}
return sz;
}
bool connected(int at)
{
char x = at % N, y = at / N;
static const char ddx[4] {1, -1, 0, 0};
static const char ddy[4] {0, 0, 1, -1};
for(int d = 0; d < 4; d++)
{
int dx = ddx[d], dy = ddy[d];
int nx = x + dx, ny = y + dy;
if(nx < 0 || ny < 0 || ny >= N || nx >= N) continue;
if(cuts[ny * N + nx]) return true;
}
return false;
}
int score()
{
marks = cuts; //true -> pretend it's already cut
int ans1 = 0, ans2 = 0;
for(char el : cuts) ans2 += el == true;
for(int i = 0; i < N*N; i++)
{
if(marks[i]) continue;
ans1 = std::max(ans1, dfs(i));
}
return ans1 + ans2;
}
int main()//int64_t argc, char*argv[])
{
int gs = 8;
for(int y = 0; y < N; y++)
for(int x = 0; x < N; x += gs)
cuts[y*N+x] ^= true;
for(int y = 0; y < N; y += gs)
for(int x = 0; x < N; x++)
cuts[y*N+x] ^= true;
for(int x = 0; x < N; x++)
cuts[x] ^= true,
cuts[N*x] ^= true,
cuts[N*(N-1)+x] ^= true,
cuts[N*x+N-1] ^= true;
//do random changes, minimizing score
printf("%d\n", score());
int its = 1e6;
float temp = 1;
for(int y = 0; y < N; y++)
{
for(int x = 0; x < N; x++) printf("%c", cuts[y*N+x] ? '#' : '.');
printf("\n");
}
while(its --> 0)
{
if(its % 1000 == 0) printf("i: %d\n", its);
temp -= 2e-6;
int i = 0;
do { i = mt() % (N*N); }
while(!cuts[i] && !connected(i));
//fun fact: do..while loops don't actually need braces
int sb = score();
cuts[i] ^= 1;
int sa = score();
int delta = sb - sa; //positive -> good
//printf("%d\n", delta);
if(delta <= 0 && (temp <= 0 || ldexpf(std::exp(delta / temp), 60) < mt()))
cuts[i] ^= 1;
else printf("%d\n", sa);
}
for(int y = 0; y < N; y++)
{
for(int x = 0; x < N; x++) printf("%c", cuts[y*N+x] ? '#' : '.');
printf("\n");
}
}


The output, with the starting condition being a 3x3 grid:

........#........#.......
.........#......#........
........#.......#........
.......#.......#.........
........#.......#........
........#........#.......
.......#........#........
.#....#.#......#.#...#.##
#.#.##...#...##...#.#.#..
...#......#.#....#.#.....
...........#.....#.......
..........#......#.......
.........#.......#.......
#......##........#.......
.#....#.......###........
..##.#.......#..#........
....#......##....#....#.#
.....#....#......#...#.#.
......#.##........###....
.......#.........#.......
.......#........#........
........#......#.........
.......#......#..........
.......#......#..........
.......#.....#...........
$$$$


# Score: 158 145 141

-4 thanks to @LevelRiverSt !

.....X.............X.....
.....X.............X.....
......X...........X......
.......X.........X.......
........X.......X........
XX.......X.....X.......XX
..X.......X.X.X.......X..
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.......X.X......
.......X.........X.......
......X...........X......
.......X.........X.......
......X.X.......X.X......
.....X...X.....X...X.....
....X.....X...X.....X....
...X.......X.X.......X...
..X.......X.X.X.......X..
XX.......X.....X.......XX
........X.......X........
.......X.........X.......
......X...........X......
.....X.............X.....
.....X.............X.....


Try it online!

Number of X: 80
Largest component: 61

Divide the grid into 9 rougly equal areas of size ~60.

• There is a way to get 80+61 by revising the spokes (more or less a rotation by 1/16 turn.) Do 2 rows of .....X.............X..... at the top then go diagonally in toward the central diamond. Commented May 6, 2020 at 23:52
• @LevelRiverSt thanks! Commented May 7, 2020 at 3:47

# 92 + 45 = 137

......X.........X........
.......X........X........
........X........X.......
.......X.X.......X.......
......X..X......X.X......
.....X....X....X...X.....
....X......X..X.....X...X
X..X.......X.X.......X.X.
.XX.........X.........X..
...X.......X.X.......X...
....X.....X...X.....X....
.....X...X.....X...X.....
......X.X.....X.X.X......
.......X.....X...X.......
......X.....X.....X......
.....X......X......X.....
....X......X........X....
....X.....X.X........XXX.
XXXX.X...X...X......X...X
......X.X.....X....X.....
.......X.......X..X......
.......X........XX.......
........X.......X........
........X.......X........
........X.......X........


Try it online!

I started with a program, then I took the best output and hand-modified it to get this. Next I'm going to try restricting the program to only place Xs on one color of squares - that seems like it might work better. The program is written in rust. The key idea was to seed the map with a Vornoi diagram before running a simplified simulating annealing:

use rand::prelude::*;

use std::collections::{HashMap, HashSet};

fn make_neighbors(point: (usize, usize), size: usize) -> Vec<(usize, usize)> {
let (r, c) = point;
let mut neighbors = vec![];
if r > 0 {
neighbors.push((r - 1, c));
}
if c > 0 {
neighbors.push((r, c - 1));
}
if r < size - 1 {
neighbors.push((r + 1, c));
}
if c < size - 1 {
neighbors.push((r, c + 1));
}
neighbors
}

fn value_board(board: &Vec<Vec<bool>>) -> usize {
let size = board.len();
let mut color_counts = vec![];
let mut removed_count = 0;
let mut seen = HashSet::new();
for r in 0..size {
for c in 0..size {
if board[r][c] {
removed_count += 1;
} else {
let mut color_count = 0;
let mut flood_stack = vec![(r, c)];
while !flood_stack.is_empty() {
let point = flood_stack.pop().unwrap();
if !board[point.0][point.1] &&!seen.contains(&point) {
seen.insert(point);
color_count += 1;
let neighbors = make_neighbors(point, size);
flood_stack.extend(neighbors);
}
}
color_counts.push(color_count);
}
}
}
let max_color_count = color_counts.into_iter().max().unwrap_or(0);
removed_count + max_color_count
}

// TODO: make removed, neighbor_removed into VecSets.
fn simulated_annealing(input_board: &Vec<Vec<bool>>, max_steps: usize) -> Vec<Vec<bool>> {
let size = input_board.len();
let mut coloring: HashMap<(usize, usize), usize> = HashMap::new();
let mut max_color = 0;
let mut color_counts = vec![];
let mut removed: Vec<(usize, usize)> = vec![];
let mut neighbor_removed: Vec<(usize, usize)> = vec![];
let mut board = input_board.clone();
for r in 0..size {
for c in 0..size {
if board[r][c] {
removed.push((r, c));
let neighbors = make_neighbors((r, c), size);
for point in neighbors {
if !board[point.0][point.1] && !neighbor_removed.contains(&point) {
neighbor_removed.push(point);
}
}
} else {
if !coloring.contains_key(&(r, c)) {
let color = max_color;
max_color += 1;
color_counts.push(0);
let mut flood_stack = vec![(r, c)];
while !flood_stack.is_empty() {
let point = flood_stack.pop().unwrap();
if !board[point.0][point.1] && !coloring.contains_key(&point) {
coloring.insert(point, color);
color_counts[color] += 1;
let neighbors = make_neighbors(point, size);
flood_stack.extend(neighbors);
}
}
}
}
}
}
for step in 0..max_steps {
//dbg!(&removed, &neighbor_removed, &coloring, &board);
assert_eq!(removed.len() + coloring.len(), size.pow(2));
if rng.gen::<f64>() < 0.5  && !removed.is_empty() {
let index = rng.gen_range(0, removed.len());
let &(r, c) = &removed[index];
assert!(removed.contains(&(r, c)));
assert!(!neighbor_removed.contains(&(r, c)));
assert!(!coloring.contains_key(&(r, c)));
assert!(board[r][c]);
let neighbors = make_neighbors((r, c), size);
let neighbor_colors: HashSet<usize> = neighbors
.iter()
.filter_map(|n| coloring.get(n))
.cloned()
.collect();
// Remove if only 1 color.
// This will always be a neutral or improving step
// Never remove otherwise
if neighbor_colors.len() <= 1 {
board[r][c] = false;
removed.swap_remove(index);
let neighbors = make_neighbors((r, c), size);
for neighbor in neighbors {
if board[neighbor.0][neighbor.1] {
neighbor_removed.push((r, c));
break;
}
}
let new_color = if neighbor_colors.len() == 1 {
neighbor_colors.into_iter().next().unwrap()
} else {
let new_color = max_color;
max_color += 1;
color_counts.push(0);
new_color
};
coloring.insert((r, c), new_color);
color_counts[new_color] += 1;
}
} else if !neighbor_removed.is_empty() {
let index = rng.gen_range(0, neighbor_removed.len());
let (r, c) = neighbor_removed[index];
let my_color = *coloring.get(&(r, c)).unwrap();
let is_max_color = color_counts.iter().enumerate().all(|(i, &color_count)| {
i == my_color || color_count < color_counts[my_color]
});
// Flip if either is a max color, in which case it's free,
// or temp is high enough and get lucky.
let take_action = is_max_color || {
step < max_steps / 2 && rng.gen::<f64>() < 0.1
};
if take_action {
board[r][c] = true;
neighbor_removed.swap_remove(index);
removed.push((r, c));
coloring.remove(&(r, c));
color_counts[my_color] -= 1;
let neighbors = make_neighbors((r, c), size);
for neighbor in neighbors {
if !board[neighbor.0][neighbor.1] && !neighbor_removed.contains(&neighbor) {
neighbor_removed.push(neighbor)
}
}
}
}
}
board
}
// Given starting points and a board size, make a vornoi diagram
fn vornoi(points: &Vec<(usize, usize)>, size: usize) -> Vec<Vec<bool>> {
let mut time_board: Vec<Vec<Option<usize>>> = vec![vec![None; size]; size];
let mut board = vec![vec![false; size]; size];
for (i, point) in points.iter().enumerate() {
time_board[point.0][point.1] = Some(i);
}
for _ in 0..size {
let mut new_board = time_board.clone();
for r in 0..size {
for c in 0..size {
if let Some(i) = time_board[r][c] {
let neighbors = make_neighbors((r, c), size);
for (nr, nc) in neighbors {
if let Some(j) = new_board[nr][nc] {
if i != j {
board[r][c] = true;
}
} else {
new_board[nr][nc] = Some(i);
}
}
}
}
}
time_board = new_board
}
board
}

fn random_vornoi(num_points: usize, size: usize) -> Vec<Vec<bool>> {
let mut points = vec![];
while points.len() < num_points {
let r = rng.gen_range(0, size);
let c = rng.gen_range(0, size);
if !points.contains(&(r, c)) {
points.push((r, c))
}
}
vornoi(&points, size)
}
fn print_board(board: &Vec<Vec<bool>>) {
let string_board = board
.iter()
.map(|row| {
row.iter()
.map(|&c| if c { 'X' } else { '.' })
.collect::<String>()
})
.collect::<Vec<String>>()
.join("\n");
println!("{}", string_board);
}
fn main() {
let size: usize = 25;
let reps = 100;
let steps = 30000000;
let mut best_points = 0;
let mut best_board = None;
let mut best_value = size.pow(2);
for num_points in 8..17 {
let mut best_board_points = None;
let mut best_value_points = size.pow(2);
for _ in 0..reps {
let board = random_vornoi(num_points, size);
let better_board = simulated_annealing(&board, steps);
let value = value_board(&better_board);
if value < best_value {
best_board = Some(better_board.clone());
best_value = value;
best_points = num_points;
}
if value < best_value_points {
best_board_points = Some(better_board);
best_value_points = value;
}
}
println!("{} {}", num_points, best_value_points);
print_board(&best_board_points.unwrap());
println!();
}
println!("{} {}", best_points, best_value);
print_board(&best_board.unwrap());
println!();
}


To run the program, put the above file in src/main.rs and put rand = "*" in your Cargo.toml.

# Score: 314 313

-1 thanks to @Level River St

.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.
X.X.X.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X.X.X.


The largest connected component is of size 1.

Verify the score here: Try it online!

• I make your score 313. 625/2 rounded up. Or alternatively add each pair of rows and you get 12*25 with an additional 13` for the odd row at the bottom. Commented May 5, 2020 at 16:28