7
\$\begingroup\$

This is a simple game of getting rid of those damn numbers.

You start with the numbers from 1 to 19, written in a grid of 9 by 3:

1 2 3 4 5 6 7 8 9
1 1 1 2 1 3 1 4 1
5 1 6 1 7 1 8 1 9

You may notice that the number 10 is missing, this because the number zero would be hard to get rid of later on.

The two rules are:

  1. If you find a pair of two numbers such that (a) they are equal OR (b) they add up to 10, you can eliminate both of them. What is a valid pair? Either, they directly follow each other (ignoring any eliminated numbers, potentially continuing in the next row, but not connecting the last with the first row) when going left-to-right through the rows, or they directly follow each other when going top-to-bottom through the columns (ignoring any eliminated numbers, not continuing in any following columns).

Small example:

2 9 1 2
3 4 5 6

Here, we can remove the pair (9, 1) as the sum is ten:

2 x x 2
3 4 5 6

Now we can remove (2, 2) as they are adjacent:

x x x x
3 4 5 6

Now, nothing else can be eliminated.

  1. If nothing can be eliminated anymore, you will copy all remaining numbers to the bottom and continue.

Example. Starting with:

 1 2 3 4 5 6 7 8 X
 X X 1 2 1 3 1 4 1
 5 X X X 7 X 8 X X
 1 X X X X X X X X
 X X X X X X X 2 X
 4 5 X X 4 X 5 6 X
 8

we get:

 1 2 3 4 5 6 7 8 X
 X X 1 2 1 3 1 4 1
 5 X X X 7 X 8 X X
 1 X X X X X X X X
 X X X X X X X 2 X
 4 5 X X 4 X 5 6 X
 8 1 2 3 4 5 6 7 8
 1 2 1 3 1 4 1 5 7
 8 1 2 4 5 4 5 6 8

You have won the game when all numbers are eliminated.

The shortest solution in terms of moves (either an elimination or a "copy remainder") wins this challenge.

If you can prove your solution to be the shortest possible (for example by doing exhaustive BFS), you get extra points. Tell us about your crazy optimizations you used to make this fit into memory! Showing us your code that you used to get to your solution is highly recommended.

Further examples of valid pairs:

  • 1 X 2
3 4 5
X 6 7
    Here, only (4,6) is a valid pair to eliminate, as they add up to ten and are directly adjacent in a column (ignoring all Xs in between).
  • 1 X X
X X X
X X 9
    The only valid pair is (1, 9), as they are directly adjacent row-wise (ignoring the many eliminated numbers in between).
Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ I'm vaguely remembering that there's a mobile game for this puzzle. Is that where you got the idea from? \$\endgroup\$
    – mypetlion
    Mar 10, 2020 at 17:14
  • \$\begingroup\$ The "What is a valid pair? ..." is not all that clear. Could you use [[1,x,2],[3,4,5],[x,6,7]] as an example and list them maybe? I would guess: (1,2), (2,3), (3,4), (4,5), (5,6), (6,7), (1,3), (4,6), (2,5), (5,7) but I may be mistaken. \$\endgroup\$
    – Jonathan Allan
    Mar 10, 2020 at 21:20
  • \$\begingroup\$ @mypetlion My girlfriend is playing this by hand, she got it from someone else - as to where it is originally from, I could not find anything. Happy to learn more! \$\endgroup\$
    – ThE_-_BliZZarD
    Mar 10, 2020 at 21:53
  • 2
    \$\begingroup\$ I mean, what constitutes as a possible pair to check for validity? The sum to ten or equal part is easy to follow it's this text that is not: "Either, they directly follow each other (ignoring any eliminated numbers, potentially continuing in the next row, but not connecting the last with the first row) when going left-to-right through the rows, or they directly follow each other when going top-to-bottom through the columns (ignoring any eliminated numbers, not continuing in any following columns)." \$\endgroup\$
    – Jonathan Allan
    Mar 10, 2020 at 22:14
  • 1
    \$\begingroup\$ So the valid pair condition means the pair is valid if they are adjacent after chaining all numbers either by row or by column and all Xs are removed? Also I suppose that being an atomic code-golf challenge we aren't supposed to give program code but instead the steps needed, are we? \$\endgroup\$
    – Shieru Asakoto
    Mar 10, 2020 at 23:54

1 Answer 1

Reset to default
7
\$\begingroup\$

36 moves

This Rust program finds a 36 move solution in half a second. There’s room to make the search faster, but this solution may already be optimal.

Solution

1 2 3 4 5 6 7 8 9 
1 X X 2 1 3 1 4 1 
5 1 6 1 7 1 8 1 9 

1 2 3 4 5 6 7 8 9 
1 . . 2 1 3 1 4 1 
5 1 6 1 7 1 8 X X 

X 2 3 4 5 6 7 8 9 
X . . 2 1 3 1 4 1 
5 1 6 1 7 1 8 . . 

. 2 3 4 5 6 7 8 X 
. . . 2 1 3 1 4 X 
5 1 6 1 7 1 8 . . 

. 2 3 4 5 6 7 X . 
. . . X 1 3 1 4 . 
5 1 6 1 7 1 8 . . 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 1 6 1 7 1 8 . . 
2 3 4 5 6 7 1 3 1 
4 5 1 6 1 7 1 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 1 6 1 7 1 X . . 
X 3 4 5 6 7 1 3 1 
4 5 1 6 1 7 1 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 1 X 1 7 1 . . . 
. 3 X 5 6 7 1 3 1 
4 5 1 6 1 7 1 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 X . X 7 1 . . . 
. 3 . 5 6 7 1 3 1 
4 5 1 6 1 7 1 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 7 X 3 1 
4 5 1 6 1 7 X 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 X . X 1 
4 5 1 6 1 7 . 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 7 . 8 2 
3 4 5 6 7 1 3 1 4 
5 7 1 3 5 6 1 4 5 
1 6 1 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 7 . X X 
3 4 5 6 7 1 3 1 4 
5 7 1 3 5 6 1 4 5 
1 6 1 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 X . . . 
X 4 5 6 7 1 3 1 4 
5 7 1 3 5 6 1 4 5 
1 6 1 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 . . . . 
. 4 5 6 7 1 3 1 4 
5 7 X 3 5 6 1 4 5 
1 6 X 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 . . . . 
. 4 5 6 7 1 3 1 4 
5 X . X 5 6 1 4 5 
1 6 . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 . . . . 
. 4 5 6 7 1 3 1 4 
X . . . X 6 1 4 5 
1 6 . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 . . . . 
. 4 5 6 7 1 3 1 X 
. . . . . X 1 4 5 
1 6 . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 . . . . 
. 4 5 6 7 1 3 X . 
. . . . . . X 4 5 
1 6 . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 1 . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 . . . . 
. X 5 6 7 1 3 . . 
. . . . . . . 4 5 
1 X . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . 7 X . . . 
. 3 . 5 6 . . . 1 
4 5 1 6 1 . . . . 
. . 5 6 7 X 3 . . 
. . . . . . . 4 5 
1 . . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
5 . . . X . . . . 
. X . 5 6 . . . 1 
4 5 1 6 1 . . . . 
. . 5 6 7 . 3 . . 
. . . . . . . 4 5 
1 . . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 4 . 
X . . . . . . . . 
. . . X 6 . . . 1 
4 5 1 6 1 . . . . 
. . 5 6 7 . 3 . . 
. . . . . . . 4 5 
1 . . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 1 X . 
. . . . . . . . . 
. . . . X . . . 1 
4 5 1 6 1 . . . . 
. . 5 6 7 . 3 . . 
. . . . . . . 4 5 
1 . . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 X . . 
. . . . . . . . . 
. . . . . . . . X 
4 5 1 6 1 . . . . 
. . 5 6 7 . 3 . . 
. . . . . . . 4 5 
1 . . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 . . . 
. . . . . . . . . 
. . . . . . . . . 
4 5 1 6 1 . . . . 
. . 5 6 X . X . . 
. . . . . . . 4 5 
1 . . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 . . . 
. . . . . . . . . 
. . . . . . . . . 
4 5 1 6 1 . . . . 
. . 5 X . . . . . 
. . . . . . . X 5 
1 . . 7 8 

. 2 3 4 5 6 7 . . 
. . . . 1 3 . . . 
. . . . . . . . . 
. . . . . . . . . 
4 5 1 6 1 . . . . 
. . X . . . . . . 
. . . . . . . . X 
1 . . 7 8 

. 2 3 4 5 6 7 . . 
. . . . X 3 . . . 
. . . . . . . . . 
. . . . . . . . . 
4 5 1 6 X . . . . 
. . . . . . . . . 
. . . . . . . . . 
1 . . 7 8 

. 2 3 4 5 6 X . . 
. . . . . X . . . 
. . . . . . . . . 
. . . . . . . . . 
4 5 1 6 . . . . . 
. . . . . . . . . 
. . . . . . . . . 
1 . . 7 8 

. 2 3 4 5 X . . . 
. . . . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
X 5 1 6 . . . . . 
. . . . . . . . . 
. . . . . . . . . 
1 . . 7 8 

. 2 3 4 X . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. X 1 6 . . . . . 
. . . . . . . . . 
. . . . . . . . . 
1 . . 7 8 

. 2 3 X . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . 1 X . . . . . 
. . . . . . . . . 
. . . . . . . . . 
1 . . 7 8 

. 2 3 . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . X . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
X . . 7 8 

. 2 X . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . . . . . . . . 
. . . X 8 

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

Code

use std::collections::HashSet;

fn start() -> Vec<i32> {
    (1..10).chain((1..10).flat_map(|i| vec![1, i])).collect()
}

fn display(solution: &[Option<(usize, usize)>]) {
    let mut grid = start();
    for &step in solution {
        if let Some((i, j)) = step {
            grid[i] = 0;
            grid[j] = 0;
        } else {
            grid.extend(&grid.iter().copied().filter(|&n| n != 0).collect::<Vec<_>>());
        }
        for (k, row) in (0..).step_by(9).zip(grid.chunks(9)) {
            for (l, &n) in (k..).zip(row) {
                if n != 0 {
                    print!("{} ", n);
                } else if let Some((i, j)) = step {
                    if l == i || l == j {
                        print!("X ");
                    } else {
                        print!(". ");
                    }
                } else {
                    print!(". ");
                }
            }
            println!();
        }
        println!();
    }
    println!("{} moves", solution.len());
    println!();
}

fn search(
    grid: &mut Vec<i32>,
    solution: &mut Vec<Option<(usize, usize)>>,
    best: &mut usize,
    mut skips: usize,
    prune: &mut HashSet<(usize, usize)>,
) {
    let len = grid.len();
    if solution.len() >= *best || len >= *best * 2 {
        return;
    }

    let mut pruned = vec![];
    (|| {
        let mut stuck = true;
        let mut i = !0;
        let mut m = !0;
        for j in 0..len {
            let n = grid[j];
            if n != 0 {
                if m == n || m + n == 10 {
                    if !prune.contains(&(i, j)) {
                        grid[i] = 0;
                        grid[j] = 0;
                        solution.push(Some((i, j)));
                        search(grid, solution, best, skips, prune);
                        solution.pop();
                        grid[i] = m;
                        grid[j] = n;
                    }
                    if skips == 0 {
                        return;
                    }
                    stuck = false;
                    skips -= 1;
                    prune.insert((i, j));
                    pruned.push((i, j))
                }
                i = j;
                m = n;
            }
        }
        if i == !0 {
            *best = solution.len();
            display(solution);
            return;
        }
        for k in 0..9 {
            i = !0;
            m = !0;
            for j in (k..len).step_by(9) {
                let n = grid[j];
                if n != 0 {
                    if m == n || m + n == 10 {
                        if !prune.contains(&(i, j)) {
                            grid[i] = 0;
                            grid[j] = 0;
                            solution.push(Some((i, j)));
                            search(grid, solution, best, skips, prune);
                            solution.pop();
                            grid[i] = m;
                            grid[j] = n;
                        }
                        if skips == 0 {
                            return;
                        }
                        stuck = false;
                        skips -= 1;
                        prune.insert((i, j));
                        pruned.push((i, j))
                    }
                    i = j;
                    m = n;
                }
            }
        }
        if stuck {
            grid.extend(&grid.iter().copied().filter(|&n| n != 0).collect::<Vec<_>>());
            solution.push(None);
            search(grid, solution, best, skips, &mut HashSet::new());
            solution.pop();
            grid.truncate(len);
        }
    })();
    for m in pruned {
        prune.remove(&m);
    }
}

fn main() {
    let mut grid = start();
    let mut best = 200;
    for skips in 0.. {
        println!("skips = {}", skips);
        search(
            &mut grid,
            &mut vec![],
            &mut best,
            skips,
            &mut HashSet::new(),
        );
    }
}
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Also, there’s a 26 move solution if you’re allowed to do a copy-remaining even when another move is available. The rules seem to say you’re not, though. \$\endgroup\$
    – Anders Kaseorg
    Mar 11, 2020 at 2:31
  • \$\begingroup\$ Very nice! Checking your solution made me realize an error in my implementation, so thank you twice! I tried implementing a BFS to have a guarantee for finding the shortest solution, but I can not get past depth 28 due to the exponential blowup in the search tree. With incremental DFS, 36 steps is definitely the shortest solution possible under the given rules. :) \$\endgroup\$
    – ThE_-_BliZZarD
    Mar 12, 2020 at 10:54

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.