title: How can I solve this arithmetic puzzle? My solution is too slow after n = 14
body: <p>Given numbers 1 to 3n, construct n equations of the form <code>a + b = c</code> or <code>a x b = c</code> such that each number is used exactly once. For example:</p>
  <pre><code>n=1 =&gt; 1+2=3
  n=2 =&gt; 1+4=5, 2x3=6
  n=3 =&gt; 4+5=9, 1+7=8, 2x3=6
  </code></pre>
  <p>The question is, does a solution exist for every n?</p>
  <p>I tried writing a basic program and it becomes too slow after n = 14. Here are the solutions I have so far:</p>
  <pre><code>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']
  
  </code></pre>
  <p>Here's the code for the program:</p>
  <pre><code>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 &quot;%s+%s=%s&quot; % (a, b, c)
      if a * b == c:
          return &quot;%s*%s=%s&quot; % (a, b, c)
      return False
  
  if __name__ == &quot;__main__&quot;:
     n = int(sys.argv[1])
     main(n)
  </code></pre>