Break The Chain
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.
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\$:
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>
#include <thread>
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:
........#........#.......
.........#......#........
........#.......#........
.......#.......#.........
........#.......#........
........#........#.......
.......#........#........
.#....#.#......#.#...#.##
#.#.##...#...##...#.#.#..
...#......#.#....#.#.....
...........#.....#.......
..........#......#.......
.........#.......#.......
#......##........#.......
.#....#.......###........
..##.#.......#..#........
....#......##....#....#.#
.....#....#......#...#.#.
......#.##........###....
.......#.........#.......
.......#........#........
........#......#.........
.......#......#..........
.......#......#..........
.......#.....#...........
```