Given numbers 1 to 3n, construct n equations of the form a + b = c or a x b = c such that each number is used exactly once. For example:

n=1 => 1+2=3
n=2 => 1+4=5, 2x3=6
n=3 => 4+5=9, 1+7=8, 2x3=6

The question is, does a solution exist for every n?

I tried writing a basic program and it becomes too slow after n = 14. Here are the solutions I have so far:

1 ['1+2=3']
2 ['2*3=6', '1+4=5']
3 ['4+5=9', '1+7=8', '2*3=6']
4 ['3+6=9', '1+10=11', '4+8=12', '2+5=7']
5 ['2+8=10', '3+6=9', '1+13=14', '5+7=12', '11+4=15']
6 ['3*5=15', '2+8=10', '4+14=18', '6+11=17', '7+9=16', '1+12=13']
7 ['6+12=18', '3*5=15', '7+10=17', '1+20=21', '4+9=13', '2+14=16', '8+11=19']
8 ['8+14=22', '6+12=18', '7+10=17', '2+19=21', '1+15=16', '11+13=24', '4+5=9', '3+20=23']
9 ['6+19=25', '8+14=22', '4+13=17', '2+18=20', '1+26=27', '3+7=10', '9+15=24', '5+16=21', '11+12=23']
10 ['6+19=25', '14+15=29', '11+17=28', '4+26=30', '2+18=20', '1+21=22', '3*9=27', '8+16=24', '5+7=12', '10+13=23']
11 ['10+23=33', '6+19=25', '14+15=29', '11+17=28', '4+26=30', '2+18=20', '5+27=32', '1+12=13', '9+22=31', '3*7=21', '16+8=24']
12 ['10+23=33', '3+29=32', '6+19=25', '15+21=36', '11+17=28', '8+14=22', '4+16=20', '7+27=34', '2*12=24', '1+30=31', '5+13=18', '9+26=35']
13 ['10+23=33', '3+29=32', '7+30=37', '6+19=25', '5+34=39', '15+21=36', '11+17=28', '18+20=38', '4+31=35', '1+26=27', '9+13=22', '8+16=24', '2+12=14']
14 ['10+23=33', '4+37=41', '3+29=32', '9+25=34', '15+21=36', '11+17=28', '8+14=22', '6+24=30', '13+27=40', '5*7=35', '2+18=20', '1+38=39', '12+19=31', '16+26=42']

Here's the code for the program:

import sys
from itertools import combinations

def main(n):
    r = set(range(1, n*3+1))
    print(n, solve(n, r, []))

def solve(n, lst, solution):
    if not lst:
        if len(solution) != n:
            return False
        return solution
    for c in combinations(lst, 3):
        valid_solution = valid(c)
        if valid_solution:
            new_solution = solution + [valid_solution]
            result = solve(n, set(lst) - set(c), new_solution)
            if result:
                return result
    return False

def valid(lst):
    a = lst[0]
    b = lst[1]
    c = lst[2]
    if a + b == c:
        return "%s+%s=%s" % (a, b, c)
    if a * b == c:
        return "%s*%s=%s" % (a, b, c)
    return False

if __name__ == "__main__":
   n = int(sys.argv[1])
   main(n)