14
$\begingroup$

I came across this beautiful puzzle and decided to create my own version.

Start by placing numbers 1, 2 and 3 anywhere on an infinite square grid. Now place numbers 4, 5, 6 ... $m$ in order, subject to the rule that when you place the number $k$ the sum of its 8 neighbors must be equal to $k$. What is the largest number $m$ that you can place?

$\endgroup$
6
  • 4
    $\begingroup$ By the way if you have a good solution or method for solving this then I strongly encourage you to contribute to the original OEIS sequence. $\endgroup$ Oct 20 '20 at 1:36
  • $\begingroup$ Is this supposed to be done by hand only? I have a feeling there are only a few/reasonable number of possibilities for placing say the first ten rocks and there could be an efficient algorithm for solving this problem. (The OEIS sequence places many 1s at first, so it'll probably blowup in that regard). $\endgroup$
    – user62757
    Oct 20 '20 at 8:49
  • $\begingroup$ I was hoping this particular puzzle is easy enough to be done by hand. However, I am also interested in the general approach to this problem, which may require a computer-based solution. $\endgroup$ Oct 20 '20 at 9:12
  • $\begingroup$ Just to clarify for anyone else reading this that incorrectly intuited the rules the same as myself; timing, or when is extremely important - you can think of of the 6...*m* not existing on your board when the 5 is placed, and the 5 doesn't exist when 4 is placed. Otherwise the challenge ends very quickly :) $\endgroup$
    – TCooper
    Oct 20 '20 at 17:24
  • $\begingroup$ You say to place the first three numbers "anywhere" but the subsequent numbers "subject to the rule". Does that mean the first three numbers are to be placed at random, not with that rule in mind? $\endgroup$
    – msh210
    Oct 22 '20 at 8:13
8
$\begingroup$

My program agrees on the optimal answer! Here are all 4 unique ways of making it, if (big if) I didn’t write in any bugs:

 +----------------------------------------+
 |                21        18            |
 |                14    7   11            |
 |                 6    1         3   19  |
 |      20    8         5    4        16  |
 |      10    2   15         9   13       |
 | 22   12        17                      |
 +----------------------------------------+

 +-----------------------------------+
 |           21        18            |
 |           14    7   11        22  |
 |            6    1         3   19  |
 | 20    8         5    4        16  |
 | 10    2   15         9   13       |
 | 12        17                      |
 +-----------------------------------+

 +-----------------------------------+
 |           21        18            |
 |           14    7   11            |
 |            6    1         3   19  |
 | 20    8         5    4        16  |
 | 10    2   15         9   13       |
 | 12        17             22       |
 +-----------------------------------+

 +-----------------------------------+
 |           21        18            |
 |           14    7   11            |
 |            6    1         3   19  |
 | 20    8         5    4        16  |
 | 10    2   15         9   13       |
 | 12        17        22            |
 +-----------------------------------+

The last one is @RobPratt’s answer, rotated and flipped. They all differ only in the position of the last value.

Some facts about picking the starting points:

  • $\begin{matrix}1 & \cdot & 3\end{matrix}$ allows for 22

  • $\begin{matrix}1 & \cdot & \cdot \\ \cdot & \cdot & 3\end{matrix}$ allows for 21

  • $\begin{matrix}1 & \cdot \\ \cdot & 3 \end{matrix}$ allows for 18

  • $\begin{matrix}1 & \cdot & \cdot \\ \cdot & \cdot & \cdot \\ \cdot & \cdot & 3 \end{matrix}$ allows for 16

  • $\begin{matrix}1 & 3 \end{matrix}$ allows for 12

The code isn’t particularly elegant or optimized, but the approach lets it find the results in 0.07s: start with the unique options for the positions of 1 and 3, then traverse the tree of all possible moves, including letting the 2 pop into existence to make a move possible.

main.rs

#![feature(array_value_iter)]

mod value;

use std::array;
use std::collections::{HashMap, HashSet};
use std::collections::hash_map::Entry;
use std::fmt;

use value::Value;

type Point = (i16, i16);

struct Grid {
    values: HashMap<Point, Value>,
    candidates: HashMap<Point, Value>,
    candidates_by_value: HashMap<Value, HashSet<Point>>,
}

const fn neighbors((x, y): Point) -> [Point; 8] {
    [
        (x - 1, y - 1),
        (x - 1, y),
        (x - 1, y + 1),
        (x, y - 1),
        (x, y + 1),
        (x + 1, y - 1),
        (x + 1, y),
        (x + 1, y + 1),
    ]
}

impl Grid {
    fn new() -> Self {
        Self {
            values: HashMap::new(),
            candidates: HashMap::new(),
            candidates_by_value: HashMap::new(),
        }
    }

    fn push(&mut self, at: Point, value: Value) {
        let newly_inserted = self.values.insert(at, value).is_none();
        debug_assert!(newly_inserted);

        for &n in &neighbors(at) {
            match self.candidates.entry(n) {
                Entry::Occupied(mut occupied) => {
                    let before = *occupied.get();
                    let after = before + value;
                    *occupied.get_mut() = after;

                    if let Entry::Occupied(mut cbs_entry) = self.candidates_by_value.entry(before) {
                        let cbs = cbs_entry.get_mut();
                        cbs.remove(&n);

                        if cbs.is_empty() {
                            cbs_entry.remove();
                        }
                    }

                    self.candidates_by_value.entry(after).or_insert_with(HashSet::new).insert(n);
                }
                Entry::Vacant(vacant) => {
                    vacant.insert(value);

                    self.candidates_by_value.entry(value).or_insert_with(HashSet::new).insert(n);
                }
            }
        }

        // TODO: remove from candidates instead of filtering later?
    }

    fn pop(&mut self, at: Point) {
        let removed = match self.values.remove(&at) {
            Some(removed) => removed,
            None => panic!("attempted to remove empty cell"),
        };

        for &n in &neighbors(at) {
            let before = self.candidates[&n];
            let after = before - removed;

            if let Entry::Occupied(mut cbs_entry) = self.candidates_by_value.entry(before) {
                let cbs = cbs_entry.get_mut();
                cbs.remove(&n);

                if cbs.is_empty() {
                    cbs_entry.remove();
                }
            }

            if before == removed {
                self.candidates.remove(&n);
            } else {
                self.candidates.insert(n, after);
                self.candidates_by_value.entry(after).or_insert_with(HashSet::new).insert(n);
            }
        }
    }

    fn collect_candidates(&self, value: Value) -> Box<[Point]> {
        self.candidates_by_value.get(&value)
            .map(|candidates| -> Box<[Point]> {
                candidates.iter()
                    .copied()
                    .filter(|p| !self.values.contains_key(&p))
                    .collect()
            })
            .unwrap_or_else(|| Box::new([]))
    }

    fn collect_2candidates(&self, target: Value) -> Box<[(Point, Point)]> {
        self.candidates_by_value.get(&(target - Value(2)))
            .map(|candidate_ns| {
                candidate_ns.iter()
                    .filter(|p| !self.values.contains_key(p))
                    .flat_map(|&p|
                        array::IntoIter::new(neighbors(p))
                            .filter(move |&pn| neighbors(pn).iter().all(|&pnn| pnn == p || !self.values.contains_key(&pnn)))
                            .map(move |pn| (pn, p)))
                    .collect::<Box<[(Point, Point)]>>()
            })
            .unwrap_or_else(|| Box::new([]))
    }
}

impl fmt::Display for Grid {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let digit_count = 3;
        let cell_width: usize = 2 + digit_count;

        let min_x = *self.values.keys().map(|(x, _y)| x).min().unwrap();
        let cols = *self.values.keys().map(|(x, _y)| x).max().unwrap() - min_x + 1;

        let min_y = *self.values.keys().map(|(_x, y)| y).min().unwrap();
        let rows = *self.values.keys().map(|(_x, y)| y).max().unwrap() - min_y + 1;

        writeln!(f, "+{:-<width$}+", "", width=cell_width * cols as usize)?;

        for y in min_y..(min_y + rows) {
            write!(f, "|")?;

            for x in min_x..(min_x + cols) {
                match self.values.get(&(x, y)) {
                    None => write!(f, "{:width$}", "", width=cell_width)?,
                Some(i) => write!(f, "{:^width$}", i, width=cell_width)?,
                }
            }

            writeln!(f, "|")?;
        }

        writeln!(f, "+{:-<width$}+", "", width=cell_width * cols as usize)?;

        Ok(())
    }
}

fn optimize(grid: &mut Grid, high: &mut Value, adding: Value, placed_2: bool) {
    let candidates = grid.collect_candidates(adding);

    for &c in candidates.iter() {
        grid.push(c, adding);

        if adding > *high {
            *high = adding;
            eprintln!("found {}", high);
            eprintln!("{}", grid);
        } else if adding == *high {
            eprintln!("{}", grid);
        }

        optimize(grid, high, adding.succ(), placed_2);

        grid.pop(c);
    }

    if !placed_2 {
        for &(c2, ca) in grid.collect_2candidates(adding).iter() {
            grid.push(c2, Value(2));
            grid.push(ca, adding);
            optimize(grid, high, adding.succ(), true);
            grid.pop(ca);
            grid.pop(c2);
        }
    }
}

fn main() {
    let mut grid = Grid::new();
    grid.push((0, 0), Value(1));

    let candidate_3s = [
        (1, 0),  // 13

        (2, 0),  // 1 3

        (1, 1),  // 1
                 //  3

        (2, 1),  // 1
                 //   3

        (2, 2),  // 1
                 //
                 //   3
    ];

    let mut high = Value(3);

    for &c in &candidate_3s {
        grid.push(c, Value(3));
        optimize(&mut grid, &mut high, Value(4), false);
        grid.pop(c);
    }
}

value.rs

use std::fmt;

#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct Value(pub u16);

impl Value {
    pub fn succ(self) -> Self {
        Self(self.0 + 1)
    }
}

impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        self.0.fmt(f)
    }
}

impl std::ops::Add for Value {
    type Output = Self;

    fn add(self, other: Value) -> Value {
        Value(self.0 + other.0)
    }
}

impl std::ops::Sub for Value {
    type Output = Self;

    fn sub(self, other: Value) -> Value {
        Value(self.0 - other.0)
    }
}
$\endgroup$
7
  • $\begingroup$ This is a brilliant answer as it shows all the possible ways to get the optimal score. Love the code too. Bonus points for doing this in Rust. You get the tick from me :) $\endgroup$ Oct 21 '20 at 7:21
  • $\begingroup$ If I am not mistaken the first and the fifth solutions are exactly identical. They probably used difference paths to arrive there though. There could be other duplicates, I haven't checked. $\endgroup$ Oct 21 '20 at 7:29
  • 1
    $\begingroup$ @DmitryKamenetsky: You’re right, and I’m not immediately sure why that’s possible (might be something with the 2 placement). Also, I can only get 18 with a knight’s move 1-3 configuration, but Bass’s answer has 21 with one of those, so something’s wrong here. Maybe put the tick back for now ;) $\endgroup$
    – Ry-
    Oct 21 '20 at 7:32
  • $\begingroup$ @DmitryKamenetsky: Should be fixed! $\endgroup$
    – Ry-
    Oct 21 '20 at 9:08
  • 1
    $\begingroup$ When 1–4 are free, you can get at least 30 (altering the 2 logic in this code to place all of 2, 3, and 4), but I don’t know for sure that that’s the maximum yet (still need to consider placing multiple-element subsets of {2,3,4} at the same time). $\endgroup$
    – Ry-
    Oct 21 '20 at 9:27
13
$\begingroup$

22: \begin{matrix} 0 & 0 & 0 & 20 & 10 & 12 \\ 0 & 0 & 0 & 8 & 2 & 0 \\ 21 & 14 & 6 & 0 & 15 & 17 \\ 0 & 7 & 1 & 5 & 0 & 0 \\ 18 & 11 & 0 & 4 & 9 & 22 \\ 0 & 0 & 3 & 0 & 13 & 0 \\ 0 & 0 & 19 & 16 & 0 & 0 \end{matrix}

$\endgroup$
4
  • $\begingroup$ I confirm this is optimal. you cannot have more than 22 with a code. $\endgroup$
    – Oray
    Oct 20 '20 at 16:59
  • 1
    $\begingroup$ @Oray care to post the code as an answer? I'm sure I'm not the only one who'd find it of interest. $\endgroup$
    – TCooper
    Oct 20 '20 at 17:25
  • $\begingroup$ @TCooper if OP does not, I will, dont worry. probably he did the same programming. it is pretty simple imo, not long recursive function, I dont want to disturb his answer. $\endgroup$
    – Oray
    Oct 20 '20 at 17:29
  • $\begingroup$ @Oray My search was not exhaustive. Please feel free to post your code. $\endgroup$
    – RobPratt
    Oct 20 '20 at 17:33
9
$\begingroup$

Here's my first go:

enter image description here

Method:

After a lot of fiddling around, it seemed like a good idea to crowd the 1 and 2 as much as possible. I started with jamming as much stuff around the 1 as possible, while keeping an eye out for a nice spot for the 2. After a couple of tries, this pattern produced the sweetest spot for the 2 at the last possible moment, and the numbers up to nineteen fell into place naturally. After a couple of small adjustments to cram in the final twenty, there still seemed to be room for improvement, because it was already possible to sum up two of the "larger" numbers, but if there's an obvious way to fit something more in, I didn't spot it.

EDIT: one more!

enter image description here

$\endgroup$
1
  • $\begingroup$ Your solutions have a very different structure to the others (kind of rectangular). Love the improvement! $\endgroup$ Oct 20 '20 at 12:01
6
$\begingroup$

Just putting this answer to show my code and explain how it is done;

Everything starts with 4 since 1,2 and 3 already placed, so the only possible way to do that,

$1$ and $3$ should be close enough to each other to form a $4$. otherwise there is no possible to continue playing the game, and $2$ does not matter much at this point.

Therefore, I put two square distance between those two ($1$ and $3$) at most in the code and put 1 into the middle of a big square grid (25x25). To make it work out online, I changed the size 25x25, it works even for 200x200 anyway :)

For

$2$, I placed it every single available square in the grid just in case if I miss something and found out that @RobPratt's answer is the optimal as below.

The idea behind code works recursively, determining possible...

next number location, as 4 first, then put it and go on, if fails, it goes nack and try another location possibility for 4, if there is any possibitility left, etc.

since there are not many possible ways to do that, program takes so short to run to find the optimal;

22.

Here is the code which works online too. you may change the grid bigger on a computer if you wish.

$\endgroup$
1
  • $\begingroup$ Very nice, thank you for the code! I wonder if it is able to solve larger versions of this problem, such as first 4 numbers placed? $\endgroup$ Oct 20 '20 at 23:10
5
$\begingroup$

First try:

16
14 02 13
12       11 17
   10 05 06
   04 01    15
07 03 08 09
   18

Approach:

Observing that 4 must be 1+3, I tried various initial layouts of 1 and 3 to generate the highest sequence without 2, and then added 2 at some distance to go further. Adding 2 earlier in the game tended to terminate the entire game early.

$\endgroup$
1
  • $\begingroup$ Very nice - you've already beaten my record. $\endgroup$ Oct 20 '20 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.