How can I solve this arithmetic puzzle? My solution is too slow after n = 14-CodePudding

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)

CodePudding user response：

This looks like a combinatorial problem where its "messiness" suggests no mathematical answer can be formulated. The cheer number of allowed combinations makes it ever more likely that each n has a valid solution, especially given that for small n you already found solutions.

Finding solutions for larger n can be tricky. One approach is called "simulated annealing", where you would take a random set of equations, I try to improve it step by step. "Bad equations" (i.e. equations that have numbers overlapping with others in the set) get removed, and new equations are tried.

Whatever approach is used, it probably can be speed up with heuristics. Such as start creating equations for numbers that show up in the least number of possible equations.

A somewhat related problem is called "graceful labeling", which has no definite answer and for which similar algorithms are appropriate.

Here is an approach using z3py, a library which implements a sat/smt solver.

First, for each number, a list of possible expressions is made. For each possible expression, a symbolic boolean indicates whether the expression will be used in the solution. To have a valid solution, for each number, exactly one of its possible expressions should be True.

from z3 import Int, And, Or, Not, Bool, Sum, Solver, sat

def exactly_one(expr):
    return Or([And([(expr[j] == (i == j))
                    for j in range(len(expr))])
               for i in range(len(expr))])

for N in range(1, 43):
    exp_for_i = [[] for i in range(3 * N   1)]
    expressions = []
    for i in range(1, 3 * N - 1):
        for j in range(i   1, 3 * N   1):
            if i   j <= 3 * N:
                expr = Bool(f'{i} {j}={i   j}')
                expressions.append(expr)
                exp_for_i[i].append(expr)
                exp_for_i[j].append(expr)
                exp_for_i[i   j].append(expr)
            if i > 1 and i * j <= 3 * N:
                expr = Int(f'{i}*{j}={i * j}')
                expressions.append(expr)
                exp_for_i[i].append(expr)
                exp_for_i[j].append(expr)
                exp_for_i[i * j].append(expr)

    s = Solver()
    s.add([exactly_one(expr) for expr in exp_for_i[1:]])
    if s.check() != sat:
        print(f'No solution for N={N}')
    else:
        m = s.model()
        print(f'N={N}:', [expr for expr in expressions if m.eval(expr) == True])
    s.reset()

N=1: [1 2=3]
N=2: [1 4=5, 2*3=6]
N=3: [1 7=8, 2*3=6, 4 5=9]
N=4: [1 10=11, 2*4=8, 3 6=9, 5 7=12]
N=5: [1 10=11, 2*7=14, 3*4=12, 5 8=13, 6 9=15]
N=6: [1 13=14, 2 7=9, 3*5=15, 4 12=16, 6 11=17, 8 10=18]
N=7: [1 17=18, 2 14=16, 3*5=15, 4 6=10, 7 13=20, 8 11=19, 9 12=21]
N=8: [1 18=19, 2 3=5, 4 17=21, 6 14=20, 7 9=16, 8 15=23, 10 12=22, 11 13=24]
N=9: [1 22=23, 2 19=21, 3 17=20, 4*6=24, 5 7=12, 8 10=18, 9 16=25, 11 15=26, 13 14=27]
N=10: [1 13=14, 2 23=25, 3*8=24, 4 22=26, 5 16=21, 6 9=15, 7 20=27, 10 19=29, 11 17=28, 12 18=30]
N=11: [1 23=24, 2*13=26, 3 25=28, 4 7=11, 5 22=27, 6 9=15, 8 21=29, 10 20=30, 12 19=31, 14 18=32, 16 17=33]
N=12: [1 6=7, 2 9=11, 3 26=29, 4 24=28, 5 25=30, 8 23=31, 10 22=32, 12 21=33, 13 14=27, 15 20=35, 16 18=34, 17 19=36]
N=13: [1 13=14, 2 8=10, 3 26=29, 4 28=32, 5 17=22, 6 25=31, 7 30=37, 9 24=33, 11 27=38, 12 23=35, 15 19=34, 16 20=36, 18 21=39]
N=14: [1 31=32, 2 12=14, 3*9=27, 4 30=34, 5 6=11, 7 28=35, 8 29=37, 10 26=36, 13 25=38, 15 24=39, 16 17=33, 18 23=41, 19 21=40, 20 22=42]
N=15: [1 5=6, 2 12=14, 3*11=33, 4 32=36, 7 31=38, 8 29=37, 9 30=39, 10 25=35, 13 28=41, 15 27=42, 16 18=34, 17 26=43, 19 21=40, 20 24=44, 22 23=45]
N=16: [1 25=26, 2 34=36, 3 11=14, 4 35=39, 5 37=42, 6 32=38, 7 13=20, 8 33=41, 9 10=19, 12 31=43, 15 29=44, 16 24=40, 17 30=47, 18 28=46, 21 27=48, 22 23=45]
N=17: [1 38=39, 2 25=27, 3 37=40, 4 13=17, 5 36=41, 6 9=15, 7 35=42, 8 11=19, 10 34=44, 12 33=45, 14 32=46, 16 31=47, 18 30=48, 20 29=49, 21 22=43, 23 28=51, 24 26=50]
N=18: [1 44=45, 2*25=50, 3 51=54, 4 42=46, 5 14=19, 6 22=28, 7 24=31, 8 33=41, 9 39=48, 10 30=40, 11 27=38, 12 35=47, 13 23=36, 15 37=52, 16 18=34, 17 26=43, 20 29=49, 21 32=53]
N=19: [1 18=19, 2 41=43, 3*14=42, 4 8=12, 5 40=45, 6 10=16, 7 39=46, 9 38=47, 11 37=48, 13 36=49, 15 35=50, 17 34=51, 20 33=53, 21 23=44, 22 32=54, 24 31=55, 25 27=52, 26 30=56, 28 29=57]
N=20: [1 44=45, 2 15=17, 3 43=46, 4 10=14, 5 42=47, 6 18=24, 7 41=48, 8 12=20, 9 40=49, 11 39=50, 13 38=51, 16 37=53, 19 36=55, 21 35=56, 22 30=52, 23 34=57, 25 33=58, 26 28=54, 27 32=59, 29 31=60]
N=21: [1 46=47, 2 17=19, 3 45=48, 4 7=11, 5 44=49, 6 15=21, 8 43=51, 9 13=22, 10 42=52, 12 41=53, 14 40=54, 16 39=55, 18 38=56, 20 37=57, 23 36=59, 24 26=50, 25 35=60, 27 34=61, 28 30=58, 29 33=62, 31 32=63]
N=22: [1 49=50, 2 21=23, 3*17=51, 4 15=19, 5 47=52, 6*8=48, 7 46=53, 9 45=54, 10 14=24, 11 44=55, 12 26=38, 13 43=56, 16 42=58, 18 41=59, 20 40=60, 22 39=61, 25 37=62, 27 36=63, 28 29=57, 30 35=65, 31 33=64, 32 34=66]
N=23: [1 40=41, 2*27=54, 3 13=16, 4 42=46, 5 62=67, 6 55=61, 7 45=52, 8 49=57, 9 59=68, 10 56=66, 11 14=25, 12 48=60, 15 29=44, 17 34=51, 18 35=53, 19 39=58, 20 30=50, 21 22=43, 23 24=47, 26 38=64, 28 37=65, 31 32=63, 33 36=69]
N=24: [1 18=19, 2 53=55, 3 51=54, 4*14=56, 5 52=57, 6 7=13, 8 21=29, 9 16=25, 10 49=59, 11 47=58, 12 48=60, 15 46=61, 17 45=62, 20 44=64, 22 43=65, 23 27=50, 24 42=66, 26 41=67, 28 40=68, 30 39=69, 31 32=63, 33 38=71, 34 36=70, 35 37=72]
N=25: [1 57=58, 2*32=64, 3 60=63, 4 41=45, 5 37=42, 6 69=75, 7 46=53, 8 62=70, 9 13=22, 10 49=59, 11 29=40, 12 61=73, 14 25=39, 15 35=50, 16 52=68, 17 55=72, 18 48=66, 19 24=43, 20 47=67, 21 30=51, 23 33=56, 26 28=54, 27 44=71, 31 34=65, 36 38=74]
N=26: [1 70=71, 2*17=34, 3 26=29, 4 44=48, 5 18=23, 6 57=63, 7 66=73, 8 37=45, 9 51=60, 10 68=78, 11 61=72, 12 52=64, 13 43=56, 14 40=54, 15 50=65, 16 33=49, 19 39=58, 20 55=75, 21 53=74, 22 25=47, 24 38=62, 27 42=69, 28 31=59, 30 46=76, 32 35=67, 36 41=77]
N=27: [1 15=16, 2*30=60, 3 58=61, 4 18=22, 5 57=62, 6 20=26, 7*9=63, 8 56=64, 10 55=65, 11 13=24, 12 54=66, 14 53=67, 17 52=69, 19 51=70, 21 50=71, 23 49=72, 25 48=73, 27 47=74, 28 31=59, 29 46=75, 32 45=77, 33 35=68, 34 44=78, 36 43=79, 37 39=76, 38 42=80, 40 41=81]
N=28: [1 61=62, 2 20=22, 3 68=71, 4 49=53, 5 51=56, 6 35=41, 7 70=77, 8 21=29, 9 57=66, 10 13=23, 11 54=65, 12 64=76, 14 67=81, 15 58=73, 16 34=50, 17 46=63, 18 24=42, 19 60=79, 25 55=80, 26 33=59, 27 48=75, 28 44=72, 30 52=82, 31 47=78, 32 37=69, 36 38=74, 39 45=84, 40 43=83]
N=29: [1 64=65, 2 61=63, 3 26=29, 4 27=31, 5 17=22, 6 74=80, 7 48=55, 8 62=70, 9 11=20, 10 43=53, 12 69=81, 13 54=67, 14 57=71, 15 21=36, 16 52=68, 18 60=78, 19 58=77, 23 56=79, 24 49=73, 25 59=84, 28 44=72, 30 45=75, 32 34=66, 33 50=83, 35 51=86, 37 39=76, 38 47=85, 40 42=82, 41 46=87]
N=30: [1 64=65, 2 28=30, 3*22=66, 4 63=67, 5 15=20, 6 26=32, 7 62=69, 8 9=17, 10 61=71, 11 13=24, 12 60=72, 14 59=73, 16 58=74, 18 70=88, 19 57=76, 21 56=77, 23 55=78, 25 54=79, 27 53=80, 29 52=81, 31 51=82, 33 35=68, 34 50=84, 36 49=85, 37 38=75, 39 48=87, 40 43=83, 41 45=86, 42 47=89, 44 46=90]
N=31: [1 69=70, 2 83=85, 3 20=23, 4 75=79, 5 68=73, 6*7=42, 8 82=90, 9 41=50, 10 43=53, 11 46=57, 12 51=63, 13 39=52, 14 66=80, 15 25=40, 16 76=92, 17 64=81, 18 56=74, 19 59=78, 21 37=58, 22 71=93, 24 48=72, 26 35=61, 27 62=89, 28 60=88, 29 36=65, 30 54=84, 31 55=86, 32 45=77, 33 34=67, 38 49=87, 44 47=91]
N=32: [1 75=76, 2*36=72, 3 74=77, 4 17=21, 5 24=29, 6 67=73, 7 19=26, 8 58=66, 9 53=62, 10 85=95, 11 60=71, 12 68=80, 13 20=33, 14 79=93, 15 39=54, 16 41=57, 18 65=83, 22 48=70, 23 61=84, 25 56=81, 27 63=90, 28 64=92, 30 59=89, 31 47=78, 32 55=87, 34 35=69, 37 49=86, 38 50=88, 40 42=82, 43 51=94, 44 52=96, 45 46=91]
N=33: [1 27=28, 2 73=75, 3 22=25, 4 72=76, 5 11=16, 6 71=77, 7 54=61, 8 70=78, 9 23=32, 10 69=79, 12 18=30, 13 68=81, 14 20=34, 15 67=82, 17 66=83, 19 65=84, 21 64=85, 24 63=87, 26 62=88, 29 60=89, 31 59=90, 33 58=91, 35 57=92, 36 38=74, 37 56=93, 39 41=80, 40 55=95, 42 44=86, 43 53=96, 45 52=97, 46 48=94, 47 51=98, 49 50=99]
N=34: [1 74=75, 2 19=21, 3 73=76, 4 28=32, 5 18=23, 6*13=78, 7 70=77, 8 71=79, 9 72=81, 10 24=34, 11 69=80, 12 26=38, 14 16=30, 15 68=83, 17 67=84, 20 66=86, 22 65=87, 25 64=89, 27 63=90, 29 62=91, 31 61=92, 33 60=93, 35 59=94, 36 49=85, 37 58=95, 39 57=96, 40 42=82, 41 56=97, 43 45=88, 44 55=99, 46 54=100, 47 51=98, 48 53=101, 50 52=102]
N=35: [1 62=63, 2 76=78, 3*25=75, 4*24=96, 5 94=99, 6 59=65, 7 74=81, 8 82=90, 9 38=47, 10 57=67, 11 73=84, 12 31=43, 13 21=34, 14 86=100, 15 49=64, 16 85=101, 17 60=77, 18 80=98, 19 23=42, 20 71=91, 22 50=72, 26 79=105, 27 61=88, 28 41=69, 29 68=97, 30 36=66, 32 55=87, 33 70=103, 35 58=93, 37 46=83, 39 56=95, 40 52=92, 44 45=89, 48 54=102, 51 53=104]
N=36: [1 81=82, 2 24=26, 3 76=79, 4 15=19, 5 78=83, 6 31=37, 7 77=84, 8 35=43, 9 21=30, 10 75=85, 11 17=28, 12 74=86, 13 23=36, 14 73=87, 16 72=88, 18 71=89, 20 70=90, 22 69=91, 25 68=93, 27 67=94, 29 66=95, 32 65=97, 33 63=96, 34 64=98, 38 62=100, 39 41=80, 40 61=101, 42 60=102, 44 59=103, 45 47=92, 46 58=104, 48 57=105, 49 50=99, 51 56=107, 52 54=106, 53 55=108]
N=37: [1 76=77, 2 65=67, 3 37=40, 4 23=27, 5 55=60, 6 103=109, 7 87=94, 8 80=88, 9 66=75, 10 31=41, 11 47=58, 12 84=96, 13 59=72, 14 91=105, 15 93=108, 16 79=95, 17 73=90, 18 30=48, 19 78=97, 20 62=82, 21 71=92, 22 89=111, 24 61=85, 25 39=64, 26 42=68, 28 35=63, 29 81=110, 32 74=106, 33 69=102, 34 70=104, 36 50=86, 38 45=83, 43 57=100, 44 54=98, 46 53=99, 49 52=101, 51 56=107]
N=38: [1 83=84, 2 32=34, 3*9=27, 4 82=86, 5 15=20, 6 81=87, 7 23=30, 8 80=88, 10 79=89, 11 25=36, 12 78=90, 13 16=29, 14 77=91, 17 76=93, 18 22=40, 19 75=94, 21 74=95, 24 73=97, 26 72=98, 28 71=99, 31 70=101, 33 69=102, 35 68=103, 37 67=104, 38 58=96, 39 66=105, 41 65=106, 42 43=85, 44 64=108, 45 47=92, 46 63=109, 48 62=110, 49 51=100, 50 61=111, 52 60=112, 53 54=107, 55 59=114, 56 57=113]
N=39: [1 86=87, 2*19=38, 3 85=88, 4*10=40, 5 84=89, 6 30=36, 7 83=90, 8 34=42, 9 82=91, 11 81=92, 12 14=26, 13 80=93, 15 17=32, 16 79=95, 18 78=96, 20 77=97, 21 23=44, 22 76=98, 24 75=99, 25 28=53, 27 74=101, 29 73=102, 31 72=103, 33 71=104, 35 70=105, 37 69=106, 39 68=107, 41 67=108, 43 66=109, 45 65=110, 46 48=94, 47 64=111, 49 51=100, 50 63=113, 52 62=114, 54 61=115, 55 57=112, 56 60=116, 58 59=117]
N=40: [1 96=97, 2 85=87, 3 60=63, 4 69=73, 5 104=109, 6 76=82, 7 71=78, 8 53=61, 9 58=67, 10 98=108, 11 106=117, 12 14=26, 13 28=41, 15 90=105, 16 86=102, 17 33=50, 18 81=99, 19 29=48, 20 42=62, 21 59=80, 22 91=113, 23 77=100, 24 94=118, 25 95=120, 27 74=101, 30 49=79, 31 83=114, 32 84=116, 34 54=88, 35 40=75, 36 56=92, 37 52=89, 38 65=103, 39 72=111, 43 64=107, 44 66=110, 45 70=115, 46 47=93, 51 68=119, 55 57=112]
N=41: [1 110=111, 2 13=15, 3 51=54, 4 77=81, 5 84=89, 6 97=103, 7 99=106, 8 85=93, 9 11=20, 10 34=44, 12 75=87, 14 43=57, 16 79=95, 17 88=105, 18 98=116, 19 90=109, 21 96=117, 22 64=86, 23 37=60, 24 70=94, 25 42=67, 26 39=65, 27 74=101, 28 55=83, 29 78=107, 30 92=122, 31 35=66, 32 59=91, 33 82=115, 36 72=108, 38 76=114, 40 80=120, 41 63=104, 45 68=113, 46 56=102, 47 53=100, 48 73=121, 49 69=118, 50 62=112, 52 71=123, 58 61=119]
N=42: [1 88=89, 2 94=96, 3*42=126, 4 47=51, 5 109=114, 6 69=75, 7 52=59, 8 33=41, 9 108=117, 10 60=70, 11 84=95, 12 111=123, 13 48=61, 14 85=99, 15 43=58, 16 81=97, 17 38=55, 18 80=98, 19 34=53, 20 105=125, 21 103=124, 22 68=90, 23 87=110, 24 83=107, 25 67=92, 26 56=82, 27 91=118, 28 78=106, 29 86=115, 30 71=101, 31 73=104, 32 40=72, 35 65=100, 36 66=102, 37 79=116, 39 54=93, 44 77=121, 45 74=119, 46 76=122, 49 64=113, 50 62=112, 57 63=120]
N=43: [1 79=80, 2 109=111, 3*14=42, 4 50=54, 5 112=117, 6 89=95, 7 90=97, 8 21=29, 9 74=83, 10 88=98, 11 32=43, 12 114=126, 13 110=123, 15 103=118, 16 68=84, 17 35=52, 18 59=77, 19 86=105, 20 82=102, 22 34=56, 23 58=81, 24 101=125, 25 60=85, 26 96=122, 27 100=127, 28 93=121, 30 61=91, 31 63=94, 33 66=99, 36 70=106, 37 76=113, 38 49=87, 39 65=104, 40 67=107, 41 78=119, 44 48=92, 45 71=116, 46 62=108, 47 73=120, 51 64=115, 53 75=128, 55 69=124, 57 72=129]
N=44: [1 28=29, 2 83=85, 3 86=89, 4 117=121, 5 96=101, 6 42=48, 7 70=77, 8 118=126, 9 30=39, 10 100=110, 11 120=131, 12 80=92, 13 82=95, 14 19=33, 15 51=66, 16 90=106, 17 99=116, 18 53=71, 20 107=127, 21 36=57, 22 81=103, 23 109=132, 24 91=115, 25 54=79, 26 97=123, 27 67=94, 31 88=119, 32 72=104, 34 78=112, 35 63=98, 37 74=111, 38 84=122, 40 47=87, 41 73=114, 43 50=93, 44 58=102, 45 60=105, 46 62=108, 49 76=125, 52 61=113, 55 75=130, 56 68=124, 59 69=128, 64 65=129]
N=45: [1 41=42, 2 98=100, 3 92=95, 4 97=101, 5 48=53, 6 122=128, 7 107=114, 8 62=70, 9 102=111, 10 108=118, 11 73=84, 12 21=33, 13 78=91, 14 112=126, 15 65=80, 16 45=61, 17 49=66, 18 29=47, 19 74=93, 20 55=75, 22 68=90, 23 56=79, 24 105=129, 25 110=135, 26 99=125, 27 86=113, 28 39=67, 30 85=115, 31 96=127, 32 89=121, 34 72=106, 35 88=123, 36 94=130, 37 87=124, 38 82=120, 40 69=109, 43 76=119, 44 59=103, 46 58=104, 50 83=133, 51 81=132, 52 64=116, 54 77=131, 57 60=117, 63 71=134]
N=46: [1 100=101, 2 128=130, 3*34=102, 4 121=125, 5 24=29, 6 30=36, 7 40=47, 8 58=66, 9 32=41, 10 124=134, 11 67=78, 12 115=127, 13 83=96, 14 91=105, 15 57=72, 16 73=89, 17 87=104, 18 81=99, 19 60=79, 20 97=117, 21 95=116, 22 62=84, 23 53=76, 25 93=118, 26 103=129, 27 108=135, 28 85=113, 31 88=119, 33 90=123, 35 71=106, 37 74=111, 38 69=107, 39 98=137, 42 80=122, 43 51=94, 44 92=136, 45 75=120, 46 68=114, 48 64=112, 49 82=131, 50 59=109, 52 86=138, 54 56=110, 55 77=132, 61 65=126, 63 70=133]
N=47: [1 102=103, 2 41=43, 3 45=48, 4*26=104, 5 32=37, 6 101=107, 7*15=105, 8 100=108, 9 24=33, 10 99=109, 11 35=46, 12 98=110, 13 17=30, 14 97=111, 16 96=112, 18 95=113, 19 20=39, 21 94=115, 22 28=50, 23 93=116, 25 92=117, 27 91=118, 29 90=119, 31 89=120, 34 88=122, 36 87=123, 38 86=124, 40 85=125, 42 84=126, 44 83=127, 47 82=129, 49 81=130, 51 80=131, 52 54=106, 53 79=132, 55 78=133, 56 58=114, 57 77=134, 59 76=135, 60 61=121, 62 75=137, 63 65=128, 64 74=138, 66 73=139, 67 69=136, 68 72=140, 70 71=141]
N=48: [1 126=127, 2*26=52, 3 105=108, 4 103=107, 5 101=106, 6 31=37, 7 102=109, 8 33=41, 9 39=48, 10 100=110, 11 35=46, 12 99=111, 13 16=29, 14 28=42, 15 98=113, 17 97=114, 18 22=40, 19 96=115, 20 24=44, 21 95=116, 23 94=117, 25 93=118, 27 92=119, 30 91=121, 32 90=122, 34 89=123, 36 88=124, 38 87=125, 43 86=129, 45 85=130, 47 84=131, 49 83=132, 50 54=104, 51 82=133, 53 81=134, 55 57=112, 56 80=136, 58 79=137, 59 61=120, 60 78=138, 62 77=139, 63 65=128, 64 76=140, 66 75=141, 67 68=135, 69 74=143, 70 72=142, 71 73=144]
N=49: [1 136=137, 2 34=36, 3 135=138, 4 126=130, 5 61=66, 6 32=38, 7 81=88, 8 109=117, 9 105=114, 10 58=68, 11 120=131, 12 80=92, 13 42=55, 14 97=111, 15 71=86, 16 102=118, 17 46=63, 18 101=119, 19 122=141, 20 112=132, 21 48=69, 22 94=116, 23 29=52, 24 91=115, 25 75=100, 26 98=124, 27 106=133, 28 79=107, 30 99=129, 31 96=127, 33 70=103, 35 37=72, 39 89=128, 40 73=113, 41 82=123, 43 65=108, 44 60=104, 45 95=140, 47 74=121, 49 76=125, 50 84=134, 51 59=110, 53 93=146, 54 90=144, 56 87=143, 57 85=142, 62 77=139, 64 83=147, 67 78=145]
N=50: [1 7=8, 2 40=42, 3*37=111, 4 109=113, 5 39=44, 6 108=114, 9 106=115, 10 35=45, 11 105=116, 12 15=27, 13 104=117, 14 33=47, 16 103=119, 17 95=112, 18 102=120, 19 32=51, 20 29=49, 21 101=122, 22 99=121, 23 100=123, 24 107=131, 25 30=55, 26 98=124, 28 97=125, 31 96=127, 34 94=128, 36 93=129, 38 92=130, 41 91=132, 43 90=133, 46 89=135, 48 88=136, 50 87=137, 52 86=138, 53 57=110, 54 85=139, 56 84=140, 58 60=118, 59 83=142, 61 82=143, 62 64=126, 63 81=144, 65 80=145, 66 68=134, 67 79=146, 69 78=147, 70 71=141, 72 77=149, 73 75=148, 74 76=150]
N=51: [1 51=52, 2 111=113, 3 38=41, 4 45=49, 5 110=115, 6*19=114, 7 109=116, 8*14=112, 9 108=117, 10 24=34, 11 32=43, 12 107=119, 13 26=39, 15 105=120, 16 31=47, 17 104=121, 18 36=54, 20 103=123, 21 101=122, 22 102=124, 23 106=129, 25 100=125, 27 29=56, 28 99=127, 30 98=128, 33 97=130, 35 96=131, 37 95=132, 40 94=134, 42 93=135, 44 92=136, 46 91=137, 48 90=138, 50 89=139, 53 88=141, 55 87=142, 57 86=143, 58 60=118, 59 85=144, 61 84=145, 62 64=126, 63 83=146, 65 82=147, 66 67=133, 68 81=149, 69 71=140, 70 80=150, 72 79=151, 73 75=148, 74 78=152, 76 77=153]
N=52: [1 115=116, 2 17=19, 3 114=117, 4 50=54, 5 113=118, 6 37=43, 7 38=45, 8 111=119, 9 112=121, 10 13=23, 11 109=120, 12 110=122, 14 33=47, 15 108=123, 16 32=48, 18 107=125, 20 106=126, 21 35=56, 22 105=127, 24 104=128, 25 27=52, 26 103=129, 28 102=130, 29 31=60, 30 101=131, 34 99=133, 36 98=134, 39 97=136, 40 95=135, 41 96=137, 42 58=100, 44 94=138, 46 93=139, 49 92=141, 51 91=142, 53 90=143, 55 89=144, 57 88=145, 59 87=146, 61 63=124, 62 86=148, 64 85=149, 65 67=132, 66 84=150, 68 83=151, 69 71=140, 70 82=152, 72 81=153, 73 74=147, 75 80=155, 76 78=154, 77 79=156]
N=53: [1 114=115, 2 30=32, 3 113=116, 4 38=42, 5 51=56, 6 43=49, 7*17=119, 8 112=120, 9*13=117, 10 111=121, 11 34=45, 12 110=122, 14 109=123, 15 25=40, 16 108=124, 18 107=125, 19 36=55, 20 27=47, 21 106=127, 22 129=151, 23 105=128, 24 29=53, 26 104=130, 28 103=131, 31 102=133, 33 101=134, 35 100=135, 37 99=136, 39 98=137, 41 97=138, 44 96=140, 46 95=141, 48 94=142, 50 93=143, 52 92=144, 54 91=145, 57 90=147, 58 60=118, 59 89=148, 61 88=149, 62 64=126, 63 87=150, 65 67=132, 66 86=152, 68 85=153, 69 70=139, 71 84=155, 72 74=146, 73 83=156, 75 82=157, 76 78=154, 77 81=158, 79 80=159]
N=54: [1 22=23, 2 57=59, 3*42=126, 4 91=95, 5 136=141, 6 52=58, 7 37=44, 8 104=112, 9 153=162, 10 46=56, 11 113=124, 12 115=127, 13 84=97, 14 118=132, 15 119=134, 16 133=149, 17 63=80, 18 96=114, 19 139=158, 20 31=51, 21 62=83, 24 74=98, 25 121=146, 26 116=142, 27 120=147, 28 81=109, 29 99=128, 30 105=135, 32 129=161, 33 107=140, 34 88=122, 35 108=143, 36 87=123, 38 100=138, 39 72=111, 40 53=93, 41 69=110, 43 102=145, 45 92=137, 47 70=117, 48 103=151, 49 101=150, 50 106=156, 54 90=144, 55 76=131, 60 65=125, 61 94=155, 64 66=130, 67 85=152, 68 89=157, 71 77=148, 73 86=159, 75 79=154, 78 82=160]
N=55: [1 31=32, 2*76=152, 3 138=141, 4 62=66, 5*21=105, 6 159=165, 7 58=65, 8 117=125, 9 144=153, 10 147=157, 11 73=84, 12 83=95, 13 118=131, 14 55=69, 15 124=139, 16 146=162, 17 61=78, 18 103=121, 19 70=89, 20 116=136, 22 107=129, 23 92=115, 24 110=134, 25 112=137, 26 94=120, 27 122=149, 28 130=158, 29 111=140, 30 96=126, 33 75=108, 34 127=161, 35 74=109, 36 114=150, 37 91=128, 38 41=79, 39 54=93, 40 102=142, 42 106=148, 43 80=123, 44 46=90, 45 88=133, 47 98=145, 48 49=97, 50 104=154, 51 100=151, 52 67=119, 53 60=113, 56 99=155, 57 86=143, 59 101=160, 63 72=135, 64 68=132, 71 85=156, 77 87=164, 81 82=163]
N=56: [1 53=54, 2 122=124, 3*41=123, 4 121=125, 5 51=56, 6*21=126, 7 120=127, 8 28=36, 9 119=128, 10 39=49, 11 118=129, 12 26=38, 13 45=58, 14 117=131, 15 19=34, 16 116=132, 17 43=60, 18 115=133, 20 114=134, 22 113=135, 23 24=47, 25 112=137, 27 111=138, 29 110=139, 30 32=62, 31 109=140, 33 108=141, 35 107=142, 37 106=143, 40 105=145, 42 104=146, 44 103=147, 46 102=148, 48 101=149, 50 100=150, 52 99=151, 55 98=153, 57 97=154, 59 96=155, 61 95=156, 63 94=157, 64 66=130, 65 93=158, 67 69=136, 68 92=160, 70 91=161, 71 73=144, 72 90=162, 74 89=163, 75 77=152, 76 88=164, 78 87=165, 79 80=159, 81 86=167, 82 84=166, 83 85=168]
N=57: [1 36=37, 2 149=151, 3 56=59, 4 166=170, 5 80=85, 6 135=141, 7 114=121, 8 90=98, 9 128=137, 10 113=123, 11 143=154, 12 148=160, 13 47=60, 14 52=66, 15 150=165, 16 100=116, 17 34=51, 18 146=164, 19 140=159, 20 53=73, 21 115=136, 22 110=132, 23 102=125, 24 88=112, 25 78=103, 26 79=105, 27 74=101, 28 134=162, 29 129=158, 30 89=119, 31 107=138, 32 139=171, 33 75=108, 35 109=144, 38 104=142, 39 57=96, 40 117=157, 41 106=147, 42 76=118, 43 87=130, 44 83=127, 45 124=169, 46 99=145, 48 63=111, 49 84=133, 50 70=120, 54 77=131, 55 67=122, 58 94=152, 61 65=126, 62 91=153, 64 92=156, 68 93=161, 69 86=155, 71 97=168, 72 95=167, 81 82=163]
N=58: [1 127=128, 2 16=18, 3 126=129, 4 50=54, 5*26=130, 6 125=131, 7 52=59, 8 124=132, 9 33=42, 10 123=133, 11 35=46, 12 122=134, 13 31=44, 14 121=135, 15 48=63, 17 120=137, 19 119=138, 20 37=57, 21 118=139, 22 39=61, 23 117=140, 24 41=65, 25 116=141, 27 29=56, 28 115=143, 30 114=144, 32 113=145, 34 112=146, 36 111=147, 38 110=148, 40 109=149, 43 108=151, 45 107=152, 47 106=153, 49 105=154, 51 104=155, 53 103=156, 55 102=157, 58 101=159, 60 100=160, 62 99=161, 64 98=162, 66 97=163, 67 69=136, 68 96=164, 70 72=142, 71 95=166, 73 94=167, 74 76=150, 75 93=168, 77 92=169, 78 80=158, 79 91=170, 81 90=171, 82 83=165, 84 89=173, 85 87=172, 86 88=174]
N=59: [1 129=130, 2 47=49, 3 128=131, 4 54=58, 5 40=45, 6*22=132, 7 127=134, 8 20=28, 9*15=135, 10 126=136, 11 41=52, 12 125=137, 13 38=51, 14 124=138, 16 123=139, 17 43=60, 18 122=140, 19 72=91, 21 121=142, 23 120=143, 24 32=56, 25 119=144, 26 36=62, 27 118=145, 29 117=146, 30 34=64, 31 116=147, 33 115=148, 35 114=149, 37 113=150, 39 112=151, 42 111=153, 44 110=154, 46 109=155, 48 108=156, 50 107=157, 53 106=159, 55 105=160, 57 104=161, 59 103=162, 61 102=163, 63 101=164, 65 100=165, 66 67=133, 68 73=141, 69 99=168, 70 97=167, 71 98=169, 74 96=170, 75 77=152, 76 95=171, 78 80=158, 79 94=173, 81 93=174, 82 84=166, 83 92=175, 85 87=172, 86 90=176, 88 89=177]
N=60: [1 125=126, 2*71=142, 3 148=151, 4 74=78, 5 168=173, 6 91=97, 7*20=140, 8 81=89, 9 158=167, 10 47=57, 11 128=139, 12 164=176, 13 124=137, 14 18=32, 15 75=90, 16 66=82, 17 45=62, 19 93=112, 21 38=59, 22 100=122, 23 130=153, 24 121=145, 25 102=127, 26 88=114, 27 143=170, 28 95=123, 29 109=138, 30 136=166, 31 70=101, 33 129=162, 34 118=152, 35 106=141, 36 98=134, 37 132=169, 39 41=80, 40 77=117, 42 104=146, 43 135=178, 44 133=177, 46 108=154, 48 113=161, 49 61=110, 50 99=149, 51 120=171, 52 79=131, 53 119=172, 54 111=165, 55 92=147, 56 103=159, 58 86=144, 60 115=175, 63 94=157, 64 116=180, 65 85=150, 67 96=163, 68 87=155, 69 105=174, 72 107=179, 73 83=156, 76 84=160]