The shortest way of getting rid of these numbers 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:


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.


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).
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() -&gt; Vec&lt;i32&gt; {
    (1..10).chain((1..10).flat_map(|i| vec![1, i])).collect()
}

fn display(solution: &amp;[Option&lt;(usize, usize)&gt;]) {
    let mut grid = start();
    for &amp;step in solution {
        if let Some((i, j)) = step {
            grid[i] = 0;
            grid[j] = 0;
        } else {
            grid.extend(&amp;grid.iter().copied().filter(|&amp;n| n != 0).collect::&lt;Vec&lt;_&gt;&gt;());
        }
        for (k, row) in (0..).step_by(9).zip(grid.chunks(9)) {
            for (l, &amp;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: &amp;mut Vec&lt;i32&gt;,
    solution: &amp;mut Vec&lt;Option&lt;(usize, usize)&gt;&gt;,
    best: &amp;mut usize,
    mut skips: usize,
    prune: &amp;mut HashSet&lt;(usize, usize)&gt;,
) {
    let len = grid.len();
    if solution.len() &gt;= *best || len &gt;= *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(&amp;(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(&amp;(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(&amp;grid.iter().copied().filter(|&amp;n| n != 0).collect::&lt;Vec&lt;_&gt;&gt;());
            solution.push(None);
            search(grid, solution, best, skips, &amp;mut HashSet::new());
            solution.pop();
            grid.truncate(len);
        }
    })();
    for m in pruned {
        prune.remove(&amp;m);
    }
}

fn main() {
    let mut grid = start();
    let mut best = 200;
    for skips in 0.. {
        println!("skips = {}", skips);
        search(
            &amp;mut grid,
            &amp;mut vec![],
            &amp;mut best,
            skips,
            &amp;mut HashSet::new(),
        );
    }
}