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);
}
}
}
}
}
}
let mut rng = thread_rng();
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![];
let mut rng = thread_rng();
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.
