The shortest way of getting rid of these numbers
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(),
        );
    }
}