A simple puzzle as a programming exercise

Translated from Polish. Originally published on morony.pl on 23 Nov 2016.

Every idea for a good programming exercise is very valuable. A good exercise for students should be interesting and tied to some real-life problem, so that it's easier to focus on the essence of programming rather than on the problem itself. I once attended classes where the instructor came up with abstract problems that were easy to code but very hard to understand – what was the point of it all? Yesterday I opened a new multipack of matchboxes, and it turned out they were the ones with the classic move-one-matchstick puzzle:

I thought this could make a nice exercise for first-year students. I usually teach Python, so I had a go at writing the program. In the first version, the program's job is simply to find the solution (or solutions) to a single puzzle:

plus = dict()
plus[0] = [8]
plus[1] = [7]
plus[2] = []
plus[3] = [9]
plus[4] = []
plus[5] = [9]
plus[6] = [8]
plus[7] = []
plus[8] = []
plus[9] = [8]

minus = dict()
minus[0] = []
minus[1] = []
minus[2] = []
minus[3] = []
minus[4] = []
minus[5] = []
minus[6] = []
minus[7] = [1]
minus[8] = [0, 6, 9]
minus[9] = [3, 5]

swap = dict()
swap[0] = [6, 9]
swap[1] = []
swap[2] = [3]
swap[3] = [2, 5]
swap[4] = []
swap[5] = [3]
swap[6] = [0, 9]
swap[7] = []
swap[8] = []
swap[9] = [0, 6]

def test_single(a, o1, b, o2, c):
    if o2 == "=":
        if o1 == "+":
            return a+b==c
        elif o1 == "-":
            return a-b==c
        else:
            print('ERROR')
    elif o1 == "=":
        if o2 == "+":
            return a+b==c
        elif o2 == "-":
            return a-b==c
        else:
            print('ERROR')
    else:
        print('ERROR')
def print_result(a, o1, b, o2, c,debug):
    print("{5}: {0}{1}{2}{3}{4}:".format(a,o1,b,o2,c,debug), test_single(a, o1, b, o2, c));

def all_comb(a, o1, b, o2, c):
    #print("SWAPY")
    for a1 in swap[a]:
        print_result(a1, o1, b, o2, c,1)
    for b1 in swap[b]:
        print_result(a, o1, b1, o2, c,2)
    for c1 in swap[c]:
        print_result(a, o1, b, o2, c1,3)
    if o1 == '-':
        print_result(a, "=", b, "-", c,4)
    #print("A minus")
    for a1 in minus[a]:
        for b1 in plus[b]:
            print_result(a1, o1, b1, o2, c,5)
        for c1 in plus[c]:
            print_result(a1, o1, b, o2, c1,6)
        if o1 == "-":
            print_result(a1, "+", b, o2, c,7)
        if o2 == "-":
            print_result(a1, o1, b, "+", c,8)
    #print("B minus")
    for b1 in minus[b]:
        for a1 in plus[a]:
            print_result(a1, o1, b1, o2, c,9)
        for c1 in plus[c]:
            print_result(a, o1, b1, o2, c1,10)
        if o1 == "-":
            print_result(a, "+", b1, o2, c,11)
        if o2 == "-":
            print_result(a, o1, b1, "+", c,12)
    #print("C minus")
    for c1 in minus[c]:
        for b1 in plus[b]:
            print_result(a, o1, b1, o2, c1,13)
        for a1 in plus[a]:
            print_result(a1, o1, b, o2, c1,14)
        if o1 == "-":
            print_result(a, "+", b, o2, c1,15)
        if o2 == "-":
            print_result(a, o1, b, "+", c1,16)

    #print("+ minus")
    if o1 == "+":
        for a1 in plus[a]:
            print_result(a1, "-", b, o2, c,17)
        for b1 in plus[b]:
            print_result(a, "-", b1, o2, c,18)
        for c1 in plus[c]:
            print_result(a, "-", b, o2, c1,19)

all_comb(1,"+",2,"=",8)

This solution is not optimized in any way. I'd be happy if a class managed to arrive at a solution like this. For the equation 1+2=8, the program returns the following result:

The program is based, first, on 3 defined dictionaries that specify which digit a given digit can be turned into by removing, adding or moving one matchstick. Second, the program covers all possible kinds of moves: e.g. taking a matchstick from the first digit and adding it to the second or third digit. Altogether 19 cases are covered (maybe this could be optimized?).

A second, equally interesting version of the program generates all possible puzzles. Here you have to decide whether to consider equations that are already correct at the start. I decided not to skip them, because we require the equation to be correct after moving one matchstick. The code looks like this:

plus = dict()
plus[0] = [8]
plus[1] = [7]
plus[2] = []
plus[3] = [9]
plus[4] = []
plus[5] = [9]
plus[6] = [8]
plus[7] = []
plus[8] = []
plus[9] = [8]

minus = dict()
minus[0] = []
minus[1] = []
minus[2] = []
minus[3] = []
minus[4] = []
minus[5] = []
minus[6] = []
minus[7] = [1]
minus[8] = [0, 6, 9]
minus[9] = [3, 5]

swap = dict()
swap[0] = [6, 9]
swap[1] = []
swap[2] = [3]
swap[3] = [2, 5]
swap[4] = []
swap[5] = [3]
swap[6] = [0, 9]
swap[7] = []
swap[8] = []
swap[9] = [0, 6]

def test_single(a, o1, b, o2, c):
    if o2 == "=":
        if o1 == "+":
            return a+b==c
        elif o1 == "-":
            return a-b==c
        else:
            print('ERROR')
    elif o1 == "=":
        if o2 == "+":
            return a+b==c
        elif o2 == "-":
            return a-b==c
        else:
            print('ERROR')
    else:
        print('ERROR')
def print_result(wa,wo1,wb,wo2,wc,a, o1, b, o2, c):
    if test_single(a, o1, b, o2, c):
        print("{0}{1}{2}{3}{4} -> {5}{6}{7}{8}{9}".format(wa,wo1,wb,wo2,wc,a,o1,b,o2,c))
        return 1
    else:
        return 0;

def all_comb(a, o1, b, o2, c):
    count = 0
    for a1 in swap[a]:
        count = count + print_result(a,o1,b,o2,c,a1, o1, b, o2, c)
    for b1 in swap[b]:
        count = count + print_result(a,o1,b,o2,c,a, o1, b1, o2, c)
    for c1 in swap[c]:
        count = count + print_result(a,o1,b,o2,c,a, o1, b, o2, c1)
    if o1 == '-':
        count = count + print_result(a,o1,b,o2,c,a, "=", b, "-", c)
    for a1 in minus[a]:
        for b1 in plus[b]:
            count = count + print_result(a,o1,b,o2,c,a1, o1, b1, o2, c)
        for c1 in plus[c]:
            count = count + print_result(a,o1,b,o2,c,a1, o1, b, o2, c1)
        if o1 == "-":
            count = count + print_result(a,o1,b,o2,c,a1, "+", b, o2, c)
        if o2 == "-":
            count = count + print_result(a,o1,b,o2,c,a1, o1, b, "+", c)
    for b1 in minus[b]:
        for a1 in plus[a]:
            count = count + print_result(a,o1,b,o2,c,a1, o1, b1, o2, c)
        for c1 in plus[c]:
            count = count + print_result(a,o1,b,o2,c,a, o1, b1, o2, c1)
        if o1 == "-":
            count = count + print_result(a,o1,b,o2,c,a, "+", b1, o2, c)
        if o2 == "-":
            count = count + print_result(a,o1,b,o2,c,a, o1, b1, "+", c)
    for c1 in minus[c]:
        for b1 in plus[b]:
            count = count + print_result(a,o1,b,o2,c,a, o1, b1, o2, c1)
        for a1 in plus[a]:
            count = count + print_result(a,o1,b,o2,c,a1, o1, b, o2, c1)
        if o1 == "-":
            count = count + print_result(a,o1,b,o2,c,a, "+", b, o2, c1)
        if o2 == "-":
            count = count + print_result(a,o1,b,o2,c,a, o1, b, "+", c1)
    if o1 == "+":
        for a1 in plus[a]:
            count = count + print_result(a,o1,b,o2,c,a1, "-", b, o2, c)
        for b1 in plus[b]:
            count = count + print_result(a,o1,b,o2,c,a, "-", b1, o2, c)
        for c1 in plus[c]:
            count = count + print_result(a,o1,b,o2,c,a, "-", b, o2, c1)
    return count

for to1 in ["+", "-"]:
    for ta in range(10):
        for tb in range(10):
            for tc in range(10):
                tcount = all_comb(ta,to1,tb,"=",tc)
                #if tcount > 2:
                #   print("{0}{1}{2}{3}{4}".format(ta,to1,tb,"=",tc), tcount)

The result is computed in the blink of an eye. The solutions for the puzzles in the picture are as follows:

A list of all the combinations, for posterity:

0+0=6 -> 6+0=6
0+0=6 -> 0+6=6
0+0=6 -> 0+0=0
0+0=8 -> 8-0=8
0+0=9 -> 9+0=9
0+0=9 -> 0+9=9
0+0=9 -> 0+0=0
0+1=7 -> 6+1=7
0+1=7 -> 8-1=7
0+1=8 -> 8+1=9
0+2=3 -> 0+3=3
0+2=3 -> 0+2=2
0+2=6 -> 8-2=6
0+2=8 -> 6+2=8
0+3=2 -> 0+2=2
0+3=2 -> 0+3=3
0+3=5 -> 0+5=5
0+3=5 -> 0+3=3
0+3=5 -> 8-3=5
0+3=8 -> 0+9=9
0+3=9 -> 6+3=9
0+4=4 -> 8-4=4
0+5=3 -> 0+3=3
0+5=3 -> 0+5=5
0+5=3 -> 8-5=3
0+5=8 -> 0+9=9
0+6=0 -> 0+0=0
0+6=0 -> 0+6=6
0+6=2 -> 8-6=2
0+6=9 -> 0+9=9
0+6=9 -> 0+6=6
0+7=1 -> 8-7=1
0+7=9 -> 8+1=9
0+8=0 -> 8-8=0
0+8=3 -> 0+9=9
0+8=5 -> 0+9=9
0+8=8 -> 8+0=8
0+9=0 -> 0+0=0
0+9=0 -> 0+9=9
0+9=6 -> 0+6=6
0+9=6 -> 0+9=9
1+0=7 -> 1+6=7
1+0=7 -> 7-0=7
1+0=8 -> 1+8=9
1+1=3 -> 1+1=2
1+1=6 -> 7-1=6
1+2=2 -> 1+2=3
1+2=4 -> 1+3=4
1+2=5 -> 1+2=3
1+2=5 -> 7-2=5
1+2=8 -> 7+2=9
1+3=3 -> 1+2=3
1+3=4 -> 7-3=4
1+3=6 -> 1+5=6
1+4=3 -> 1+4=5
1+4=3 -> 7-4=3
1+5=0 -> 1+5=6
1+5=2 -> 7-5=2
1+5=4 -> 1+3=4
1+5=9 -> 1+5=6
1+6=1 -> 1+0=1
1+6=1 -> 7-6=1
1+6=8 -> 1+8=9
1+7=0 -> 7-7=0
1+7=8 -> 7+1=8
1+8=0 -> 1+8=9
1+8=1 -> 1+6=7
1+8=6 -> 1+8=9
1+8=7 -> 7+0=7
1+9=1 -> 1+0=1
1+9=7 -> 1+6=7
1+9=8 -> 1+8=9
2+0=3 -> 3+0=3
2+0=3 -> 2+0=2
2+0=8 -> 2+6=8
2+1=2 -> 2+1=3
2+1=4 -> 3+1=4
2+1=5 -> 2+1=3
2+1=8 -> 2+7=9
2+2=5 -> 3+2=5
2+2=5 -> 2+3=5
2+3=3 -> 2+3=5
2+3=4 -> 2+2=4
2+3=6 -> 3+3=6
2+3=7 -> 2+5=7
2+4=0 -> 2+4=6
2+4=7 -> 3+4=7
2+4=9 -> 2+4=6
2+5=5 -> 2+3=5
2+5=8 -> 3+5=8
2+6=2 -> 2+0=2
2+6=9 -> 3+6=9
2+7=0 -> 2+7=9
2+7=6 -> 2+7=9
2+8=0 -> 2+6=8
2+8=6 -> 2+6=8
2+8=9 -> 2+6=8
2+9=1 -> 2+5=7
2+9=2 -> 2+0=2
2+9=8 -> 2+6=8
3+0=2 -> 2+0=2
3+0=2 -> 3+0=3
3+0=5 -> 5+0=5
3+0=5 -> 3+0=3
3+0=8 -> 9+0=9
3+0=9 -> 3+6=9
3+0=9 -> 9-0=9
3+1=3 -> 2+1=3
3+1=6 -> 5+1=6
3+1=8 -> 9-1=8
3+2=3 -> 3+2=5
3+2=4 -> 2+2=4
3+2=6 -> 3+3=6
3+2=7 -> 5+2=7
3+2=7 -> 9-2=7
3+3=0 -> 3+3=6
3+3=5 -> 2+3=5
3+3=5 -> 3+2=5
3+3=6 -> 9-3=6
3+3=8 -> 5+3=8
3+3=8 -> 3+5=8
3+3=9 -> 3+3=6
3+4=5 -> 9-4=5
3+4=6 -> 2+4=6
3+4=9 -> 5+4=9
3+5=4 -> 9-5=4
3+5=6 -> 3+3=6
3+5=7 -> 2+5=7
3+6=0 -> 3+6=9
3+6=3 -> 3+0=3
3+6=3 -> 9-6=3
3+6=6 -> 3+6=9
3+6=8 -> 2+6=8
3+7=2 -> 9-7=2
3+7=9 -> 2+7=9
3+8=1 -> 9-8=1
3+8=3 -> 3+6=9
3+8=5 -> 3+6=9
3+8=9 -> 9+0=9
3+9=0 -> 3+5=8
3+9=0 -> 9-9=0
3+9=3 -> 3+0=3
3+9=6 -> 3+5=8
3+9=9 -> 3+6=9
3+9=9 -> 3+5=8
4+1=3 -> 4+1=5
4+2=0 -> 4+2=6
4+2=7 -> 4+3=7
4+2=9 -> 4+2=6
4+3=6 -> 4+2=6
4+3=9 -> 4+5=9
4+5=0 -> 4+5=9
4+5=6 -> 4+5=9
4+5=7 -> 4+3=7
4+6=4 -> 4+0=4
4+9=1 -> 4+3=7
4+9=3 -> 4+5=9
4+9=4 -> 4+0=4
4+9=5 -> 4+5=9
5+0=3 -> 3+0=3
5+0=3 -> 5+0=5
5+0=8 -> 9+0=9
5+0=9 -> 9-0=9
5+1=0 -> 5+1=6
5+1=4 -> 3+1=4
5+1=8 -> 9-1=8
5+1=9 -> 5+1=6
5+2=5 -> 3+2=5
5+2=7 -> 9-2=7
5+2=8 -> 5+3=8
5+3=6 -> 3+3=6
5+3=6 -> 9-3=6
5+3=7 -> 5+2=7
5+4=0 -> 5+4=9
5+4=5 -> 9-4=5
5+4=6 -> 5+4=9
5+4=7 -> 3+4=7
5+5=4 -> 9-5=4
5+5=8 -> 3+5=8
5+5=8 -> 5+3=8
5+6=3 -> 9-6=3
5+6=5 -> 5+0=5
5+6=9 -> 3+6=9
5+7=2 -> 9-7=2
5+8=1 -> 9-8=1
5+8=9 -> 9+0=9
5+9=0 -> 5+3=8
5+9=0 -> 9-9=0
5+9=5 -> 5+0=5
5+9=6 -> 5+3=8
5+9=9 -> 5+3=8
6+0=0 -> 0+0=0
6+0=0 -> 6+0=6
6+0=8 -> 8-0=8
6+0=9 -> 9+0=9
6+0=9 -> 6+0=6
6+1=1 -> 0+1=1
6+1=7 -> 8-1=7
6+1=8 -> 8+1=9
6+2=2 -> 0+2=2
6+2=6 -> 8-2=6
6+2=9 -> 6+3=9
6+3=0 -> 6+3=9
6+3=3 -> 0+3=3
6+3=5 -> 8-3=5
6+3=6 -> 6+3=9
6+3=8 -> 6+2=8
6+4=4 -> 0+4=4
6+4=4 -> 8-4=4
6+5=3 -> 8-5=3
6+5=5 -> 0+5=5
6+5=9 -> 6+3=9
6+6=2 -> 8-6=2
6+6=6 -> 0+6=6
6+6=6 -> 6+0=6
6+7=1 -> 6+1=7
6+7=1 -> 8-7=1
6+7=7 -> 0+7=7
6+7=9 -> 8+1=9
6+8=0 -> 8-8=0
6+8=8 -> 0+8=8
6+8=8 -> 8+0=8
6+9=3 -> 6+3=9
6+9=5 -> 6+3=9
6+9=6 -> 6+0=6
6+9=9 -> 0+9=9
7+0=1 -> 7-0=7
7+0=9 -> 1+8=9
7+1=0 -> 7-7=0
7+1=8 -> 1+7=8
7+2=0 -> 7+2=9
7+2=6 -> 7+2=9
7+3=9 -> 7+2=9
7+6=1 -> 1+6=7
7+6=7 -> 7+0=7
7+6=9 -> 1+8=9
7+7=0 -> 1+7=8
7+7=0 -> 7+1=8
7+7=6 -> 1+7=8
7+7=6 -> 7+1=8
7+7=9 -> 1+7=8
7+7=9 -> 7+1=8
7+8=1 -> 7+0=7
7+8=3 -> 1+8=9
7+8=5 -> 1+8=9
7+9=7 -> 7+0=7
7+9=9 -> 1+8=9
8+0=0 -> 8-8=0
8+0=0 -> 8-0=8
8+0=3 -> 9+0=9
8+0=5 -> 9+0=9
8+0=6 -> 8-0=8
8+0=8 -> 0+8=8
8+0=9 -> 8-0=8
8+1=0 -> 8+1=9
8+1=1 -> 6+1=7
8+1=1 -> 8-7=1
8+1=1 -> 8-1=7
8+1=6 -> 8+1=9
8+1=7 -> 0+7=7
8+2=0 -> 6+2=8
8+2=6 -> 6+2=8
8+2=9 -> 6+2=8
8+3=3 -> 6+3=9
8+3=5 -> 6+3=9
8+3=9 -> 0+9=9
8+5=9 -> 0+9=9
8+6=0 -> 8-8=0
8+6=8 -> 8+0=8
8+6=8 -> 0+8=8
8+7=1 -> 0+7=7
8+7=3 -> 8+1=9
8+7=5 -> 8+1=9
8+8=0 -> 0+8=8
8+8=0 -> 8+0=8
8+8=6 -> 0+8=8
8+8=6 -> 8+0=8
8+8=9 -> 0+8=8
8+8=9 -> 8+0=8
8+9=0 -> 8-8=0
8+9=3 -> 0+9=9
8+9=5 -> 0+9=9
8+9=8 -> 8+0=8
8+9=8 -> 0+8=8
9+0=0 -> 0+0=0
9+0=0 -> 9+0=9
9+0=1 -> 9-8=1
9+0=3 -> 9-0=9
9+0=5 -> 9-0=9
9+0=6 -> 6+0=6
9+0=6 -> 9+0=9
9+0=8 -> 8-0=8
9+1=0 -> 9-1=8
9+1=1 -> 0+1=1
9+1=2 -> 9-7=2
9+1=6 -> 9-1=8
9+1=7 -> 6+1=7
9+1=7 -> 8-1=7
9+1=8 -> 8+1=9
9+1=9 -> 9-1=8
9+2=1 -> 5+2=7
9+2=1 -> 9-2=7
9+2=2 -> 0+2=2
9+2=6 -> 8-2=6
9+2=8 -> 6+2=8
9+3=0 -> 5+3=8
9+3=0 -> 9-9=0
9+3=3 -> 0+3=3
9+3=5 -> 8-3=5
9+3=6 -> 5+3=8
9+3=9 -> 6+3=9
9+3=9 -> 5+3=8
9+4=1 -> 3+4=7
9+4=3 -> 5+4=9
9+4=4 -> 0+4=4
9+4=4 -> 8-4=4
9+4=5 -> 5+4=9
9+5=0 -> 3+5=8
9+5=0 -> 9-9=0
9+5=3 -> 8-5=3
9+5=5 -> 0+5=5
9+5=6 -> 3+5=8
9+5=9 -> 3+5=8
9+6=1 -> 9-8=1
9+6=2 -> 8-6=2
9+6=3 -> 3+6=9
9+6=5 -> 3+6=9
9+6=6 -> 0+6=6
9+6=9 -> 9+0=9
9+7=1 -> 8-7=1
9+7=7 -> 0+7=7
9+7=9 -> 8+1=9
9+8=0 -> 8-8=0
9+8=3 -> 9+0=9
9+8=5 -> 9+0=9
9+8=8 -> 0+8=8
9+8=8 -> 8+0=8
9+9=1 -> 9-8=1
9+9=9 -> 0+9=9
9+9=9 -> 9+0=9
0-0=0 -> 0=0-0
0-0=6 -> 6-0=6
0-0=6 -> 0-0=0
0-0=8 -> 0+0=0
0-0=9 -> 9-0=9
0-0=9 -> 0-0=0
0-1=5 -> 6-1=5
0-1=7 -> 0+1=1
0-1=8 -> 9-1=8
0-2=4 -> 6-2=4
0-2=7 -> 9-2=7
0-2=8 -> 8-2=6
0-3=3 -> 6-3=3
0-3=6 -> 9-3=6
0-3=9 -> 0+3=3
0-3=9 -> 8-3=5
0-4=2 -> 6-4=2
0-4=5 -> 9-4=5
0-5=1 -> 6-5=1
0-5=4 -> 9-5=4
0-5=9 -> 8-5=3
0-5=9 -> 0+5=5
0-6=0 -> 6-6=0
0-6=0 -> 0-0=0
0-6=3 -> 9-6=3
0-6=8 -> 0+6=6
0-7=1 -> 0+1=1
0-7=2 -> 9-7=2
0-7=7 -> 8-1=7
0-7=7 -> 8-7=1
0-8=0 -> 0+0=0
0-8=1 -> 9-8=1
0-8=2 -> 8-6=2
0-8=6 -> 0+6=6
0-8=8 -> 8-0=8
0-8=8 -> 8-8=0
0-8=9 -> 0+9=9
0-9=0 -> 9-9=0
0-9=0 -> 0-0=0
0-9=3 -> 0+3=3
0-9=3 -> 8-5=3
0-9=5 -> 8-3=5
0-9=5 -> 0+5=5
0-9=8 -> 0+9=9
1-0=1 -> 1=0-1
1-0=7 -> 1+0=1
1-1=0 -> 1=1-0
1-1=6 -> 1-1=0
1-1=8 -> 7-1=6
1-1=9 -> 1-1=0
1-2=9 -> 1+2=3
1-2=9 -> 7-2=5
1-4=9 -> 7-4=3
1-4=9 -> 1+4=5
1-5=8 -> 1+5=6
1-6=1 -> 1-0=1
1-6=7 -> 7-6=1
1-7=2 -> 1+1=2
1-7=6 -> 7-1=6
1-7=8 -> 7-7=0
1-8=1 -> 1+0=1
1-8=1 -> 7-6=1
1-8=7 -> 7-0=7
1-8=7 -> 1+6=7
1-8=8 -> 1+8=9
1-9=1 -> 1-0=1
1-9=2 -> 7-5=2
1-9=4 -> 7-3=4
1-9=4 -> 1+3=4
1-9=6 -> 1+5=6
2-0=2 -> 2=0-2
2-0=3 -> 3-0=3
2-0=3 -> 2-0=2
2-1=1 -> 2=1-1
2-1=2 -> 3-1=2
2-1=9 -> 2+1=3
2-2=0 -> 2=2-0
2-2=1 -> 3-2=1
2-2=6 -> 2-2=0
2-2=9 -> 2-2=0
2-3=0 -> 3-3=0
2-3=0 -> 2-2=0
2-3=9 -> 2+3=5
2-4=8 -> 2+4=6
2-6=2 -> 2-0=2
2-7=3 -> 2+1=3
2-7=8 -> 2+7=9
2-8=2 -> 2+0=2
2-8=8 -> 2+6=8
2-9=2 -> 2-0=2
2-9=5 -> 2+3=5
2-9=7 -> 2+5=7
3-0=2 -> 2-0=2
3-0=2 -> 3-0=3
3-0=3 -> 3=0-3
3-0=5 -> 5-0=5
3-0=5 -> 3-0=3
3-0=8 -> 9-0=9
3-0=9 -> 3+0=3
3-1=1 -> 2-1=1
3-1=2 -> 3=1-2
3-1=3 -> 3-1=2
3-1=4 -> 5-1=4
3-2=0 -> 2-2=0
3-2=0 -> 3-3=0
3-2=1 -> 3=2-1
3-2=3 -> 5-2=3
3-2=9 -> 3+2=5
3-3=0 -> 3=3-0
3-3=1 -> 3-2=1
3-3=2 -> 5-3=2
3-3=6 -> 3-3=0
3-3=8 -> 9-3=6
3-3=8 -> 3+3=6
3-3=9 -> 3-3=0
3-4=1 -> 5-4=1
3-4=9 -> 9-4=5
3-5=0 -> 5-5=0
3-5=0 -> 3-3=0
3-6=3 -> 3-0=3
3-6=8 -> 3+6=9
3-6=9 -> 9-6=3
3-7=4 -> 3+1=4
3-7=8 -> 9-1=8
3-8=0 -> 9-9=0
3-8=3 -> 3+0=3
3-8=3 -> 9-6=3
3-8=7 -> 9-8=1
3-8=9 -> 9-0=9
3-8=9 -> 3+6=9
3-9=3 -> 3-0=3
3-9=4 -> 9-5=4
3-9=6 -> 9-3=6
3-9=6 -> 3+3=6
3-9=8 -> 3+5=8
3-9=8 -> 9-9=0
4-0=4 -> 4=0-4
4-1=2 -> 4-1=3
4-1=3 -> 4=1-3
4-1=5 -> 4-1=3
4-1=9 -> 4+1=5
4-2=1 -> 4-3=1
4-2=2 -> 4=2-2
4-2=3 -> 4-2=2
4-2=8 -> 4+2=6
4-3=1 -> 4=3-1
4-3=2 -> 4-2=2
4-4=0 -> 4=4-0
4-4=6 -> 4-4=0
4-4=9 -> 4-4=0
4-5=1 -> 4-3=1
4-5=8 -> 4+5=9
4-6=4 -> 4-0=4
4-7=5 -> 4+1=5
4-8=4 -> 4+0=4
4-9=4 -> 4-0=4
4-9=7 -> 4+3=7
4-9=9 -> 4+5=9
5-0=3 -> 3-0=3
5-0=3 -> 5-0=5
5-0=5 -> 5=0-5
5-0=8 -> 9-0=9
5-0=9 -> 5+0=5
5-1=2 -> 3-1=2
5-1=4 -> 5=1-4
5-1=8 -> 5+1=6
5-2=1 -> 3-2=1
5-2=2 -> 5-3=2
5-2=2 -> 5-2=3
5-2=3 -> 5=2-3
5-2=5 -> 5-2=3
5-3=0 -> 3-3=0
5-3=0 -> 5-5=0
5-3=2 -> 5=3-2
5-3=3 -> 5-2=3
5-3=3 -> 5-3=2
5-3=8 -> 9-3=6
5-4=1 -> 5=4-1
5-4=8 -> 5+4=9
5-4=9 -> 9-4=5
5-5=0 -> 5=5-0
5-5=2 -> 5-3=2
5-5=6 -> 5-5=0
5-5=9 -> 5-5=0
5-6=5 -> 5-0=5
5-6=9 -> 9-6=3
5-7=6 -> 5+1=6
5-7=8 -> 9-1=8
5-8=0 -> 9-9=0
5-8=3 -> 9-6=3
5-8=5 -> 5+0=5
5-8=7 -> 9-8=1
5-8=9 -> 9-0=9
5-9=4 -> 9-5=4
5-9=5 -> 5-0=5
5-9=6 -> 9-3=6
5-9=8 -> 5+3=8
5-9=8 -> 9-9=0
6-0=0 -> 0-0=0
6-0=0 -> 6-6=0
6-0=0 -> 6-0=6
6-0=6 -> 6=0-6
6-0=8 -> 6+0=6
6-0=9 -> 9-0=9
6-0=9 -> 6-0=6
6-1=3 -> 6-1=5
6-1=5 -> 6=1-5
6-1=8 -> 9-1=8
6-2=3 -> 6-3=3
6-2=4 -> 6=2-4
6-2=7 -> 9-2=7
6-2=8 -> 8-2=6
6-3=1 -> 6-5=1
6-3=2 -> 6-3=3
6-3=3 -> 6=3-3
6-3=4 -> 6-2=4
6-3=5 -> 6-3=3
6-3=6 -> 9-3=6
6-3=8 -> 6+3=9
6-3=9 -> 8-3=5
6-4=2 -> 6=4-2
6-4=3 -> 6-4=2
6-4=5 -> 9-4=5
6-5=1 -> 6=5-1
6-5=3 -> 6-3=3
6-5=4 -> 9-5=4
6-5=9 -> 8-5=3
6-6=0 -> 6=6-0
6-6=3 -> 9-6=3
6-6=6 -> 6-0=6
6-6=6 -> 6-6=0
6-6=9 -> 6-6=0
6-7=2 -> 9-7=2
6-7=7 -> 8-1=7
6-7=7 -> 6+1=7
6-7=7 -> 8-7=1
6-8=1 -> 9-8=1
6-8=2 -> 8-6=2
6-8=6 -> 6+0=6
6-8=8 -> 8-0=8
6-8=8 -> 8-8=0
6-9=0 -> 9-9=0
6-9=0 -> 6-6=0
6-9=3 -> 8-5=3
6-9=5 -> 8-3=5
6-9=6 -> 6-0=6
6-9=9 -> 6+3=9
7-0=1 -> 7-6=1
7-0=1 -> 1+0=1
7-0=7 -> 7=0-7
7-1=0 -> 7-1=6
7-1=2 -> 1+1=2
7-1=6 -> 7=1-6
7-1=8 -> 7-7=0
7-1=9 -> 7-1=6
7-2=3 -> 7-2=5
7-2=3 -> 1+2=3
7-2=4 -> 7-3=4
7-2=5 -> 7=2-5
7-2=8 -> 7+2=9
7-3=2 -> 7-5=2
7-3=4 -> 7=3-4
7-3=4 -> 1+3=4
7-3=5 -> 7-2=5
7-4=2 -> 7-4=3
7-4=3 -> 7=4-3
7-4=5 -> 7-4=3
7-4=5 -> 1+4=5
7-5=2 -> 7=5-2
7-5=3 -> 7-5=2
7-5=4 -> 7-3=4
7-5=6 -> 1+5=6
7-6=1 -> 7=6-1
7-6=7 -> 7-0=7
7-6=7 -> 1+6=7
7-7=0 -> 7=7-0
7-7=6 -> 7-7=0
7-7=8 -> 1+7=8
7-7=8 -> 7+1=8
7-7=9 -> 7-7=0
7-8=1 -> 7-0=7
7-8=7 -> 7+0=7
7-8=9 -> 1+8=9
7-9=1 -> 7-6=1
7-9=7 -> 7-0=7
8-0=0 -> 0+0=0
8-0=1 -> 9-8=1
8-0=2 -> 8-6=2
8-0=3 -> 9-0=9
8-0=5 -> 9-0=9
8-0=6 -> 6+0=6
8-0=8 -> 8=0-8
8-0=8 -> 8-8=0
8-0=9 -> 9+0=9
8-1=0 -> 9-1=8
8-1=1 -> 0+1=1
8-1=2 -> 9-7=2
8-1=6 -> 9-1=8
8-1=7 -> 8=1-7
8-1=7 -> 6+1=7
8-1=7 -> 8-7=1
8-1=8 -> 8+1=9
8-1=9 -> 9-1=8
8-2=0 -> 8-2=6
8-2=1 -> 9-2=7
8-2=2 -> 0+2=2
8-2=5 -> 8-3=5
8-2=6 -> 8=2-6
8-2=8 -> 6+2=8
8-2=9 -> 8-2=6
8-3=0 -> 9-9=0
8-3=3 -> 8-5=3
8-3=3 -> 8-3=5
8-3=3 -> 0+3=3
8-3=5 -> 8=3-5
8-3=6 -> 8-2=6
8-3=9 -> 6+3=9
8-4=4 -> 8=4-4
8-4=4 -> 0+4=4
8-5=0 -> 9-9=0
8-5=2 -> 8-5=3
8-5=3 -> 8=5-3
8-5=5 -> 8-3=5
8-5=5 -> 8-5=3
8-5=5 -> 0+5=5
8-6=1 -> 9-8=1
8-6=2 -> 8=6-2
8-6=3 -> 8-6=2
8-6=6 -> 0+6=6
8-6=8 -> 8-0=8
8-6=8 -> 8-8=0
8-7=1 -> 8=7-1
8-7=1 -> 8-1=7
8-7=7 -> 0+7=7
8-7=9 -> 8+1=9
8-8=0 -> 8=8-0
8-8=0 -> 8-0=8
8-8=6 -> 8-8=0
8-8=6 -> 8-0=8
8-8=8 -> 0+8=8
8-8=8 -> 8+0=8
8-8=9 -> 8-8=0
8-8=9 -> 8-0=8
8-9=1 -> 9-8=1
8-9=2 -> 8-6=2
8-9=8 -> 8-0=8
8-9=8 -> 8-8=0
8-9=9 -> 0+9=9
9-0=0 -> 0-0=0
9-0=0 -> 9-9=0
9-0=0 -> 9-0=9
9-0=3 -> 9-6=3
9-0=3 -> 3+0=3
9-0=5 -> 5+0=5
9-0=6 -> 6-0=6
9-0=6 -> 9-0=9
9-0=7 -> 9-8=1
9-0=8 -> 9+0=9
9-0=9 -> 9=0-9
9-1=4 -> 3+1=4
9-1=5 -> 6-1=5
9-1=6 -> 5+1=6
9-1=8 -> 9=1-8
9-2=4 -> 6-2=4
9-2=5 -> 3+2=5
9-2=6 -> 9-3=6
9-2=7 -> 9=2-7
9-2=7 -> 5+2=7
9-2=8 -> 8-2=6
9-3=0 -> 9-3=6
9-3=3 -> 6-3=3
9-3=4 -> 9-5=4
9-3=6 -> 9=3-6
9-3=6 -> 3+3=6
9-3=7 -> 9-2=7
9-3=8 -> 5+3=8
9-3=8 -> 9-9=0
9-3=9 -> 9-3=6
9-3=9 -> 8-3=5
9-4=2 -> 6-4=2
9-4=3 -> 9-4=5
9-4=5 -> 9=4-5
9-4=7 -> 3+4=7
9-4=9 -> 5+4=9
9-5=1 -> 6-5=1
9-5=4 -> 9=5-4
9-5=6 -> 9-3=6
9-5=8 -> 3+5=8
9-5=8 -> 9-9=0
9-5=9 -> 8-5=3
9-6=0 -> 6-6=0
9-6=0 -> 9-9=0
9-6=2 -> 9-6=3
9-6=3 -> 9=6-3
9-6=5 -> 9-6=3
9-6=7 -> 9-8=1
9-6=9 -> 9-0=9
9-6=9 -> 3+6=9
9-7=0 -> 9-1=8
9-7=2 -> 9=7-2
9-7=3 -> 9-7=2
9-7=6 -> 9-1=8
9-7=7 -> 8-1=7
9-7=7 -> 8-7=1
9-7=9 -> 9-1=8
9-8=1 -> 9=8-1
9-8=2 -> 8-6=2
9-8=3 -> 9-0=9
9-8=5 -> 9-0=9
9-8=8 -> 8-0=8
9-8=8 -> 8-8=0
9-8=9 -> 9+0=9
9-9=0 -> 9=9-0
9-9=3 -> 9-6=3
9-9=3 -> 8-5=3
9-9=5 -> 8-3=5
9-9=6 -> 9-9=0
9-9=7 -> 9-8=1
9-9=9 -> 9-0=9
9-9=9 -> 9-9=0

I hope there are no glaring mistakes in the solution?

As an exercise, I encourage anyone who's up for it to solve this problem in your favorite programming language. If you say it can be done more simply, you're probably right, but I'm always happy to see your code.