The GNU Linear Programming Kit (GLPK)
Solving with the Gnu Linear Programming Kit (GLPK)
The GNU Linear Programming Kit is a free set of tools for solving linear programming problems. It is written in C but there are several interfaces that allow it to be used from Python. These include PyGLPK, ctypes-glpk and PyMathProg but, sadly, none of these have been updated to work with Python 3 or the current version of GLPK (4.49). However, ctypes-glpk uses Python’s ctypes for its GLPK interface and I found that it was possible to build on this to provide a version that works with Python 3 and glpk 4.49 on Windows. I have made my version available here.
Using GLPK via Python, we can now solve the puzzle as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
# import the interface to the GNU Linear Programming Kit from glpk import * # the circles are numbered as follows: # # 1 (1,1) # 2 3 (2,1) (2,2) # 4 5 6 (3,1) (3,2) (3,3) # .... def indx(i, j): return i * (i - 1) // 2 + j # solve for a given number of rows def solve(rows): # the number of circles size = rows * (rows + 1) // 2 # silence GLPK solver output glp_term_out(False) # create and name a GLPK maximisation problem lp = glp_create_prob() glp_set_prob_name(lp, 'Sunday Times Teaser 2161'.encode()) glp_set_obj_dir(lp, GLP_MAX) # add a boolean variable for each circle glp_add_cols(lp, size) for i in range(1, size + 1): # name the variable as indicated earlier glp_set_col_name(lp, i, str(i).encode()) # set it as a boolean variable (circle has red heart) glp_set_col_kind(lp, i, GLP_BV) # set the objecctive as the sum of all variables glp_set_obj_coef(lp, i, 1) # find all triples of circles that form equilateral triangles eqt = [] # for each row except the last (i) for i in range(1, rows): # for each position in this row (j) for j in range(1, i + 1): # for each triangle of side length k with its upper vertex # at j and its sides parallel to those of the overall shape for k in range(1, rows - i + 1): # the sets of 3 points at the same distances clockwise along the # sides of the these triangles form k equilateral triangles for m in range(k): eqt.append((indx(i + m, j), indx(i + k, j + m), indx(i + k - m, j + k - m))) # add each possible equilateral triangle as a constraint where # the sum of the indexed variables involved is less than three glp_add_rows(lp, len(eqt)) v = (1.0, 1.0, 1.0) # run through the equilateral triangles for i, p3 in enumerate(eqt): # name the constraint glp_set_row_name(lp, i + 1, str(i + 1).encode()) # set an upper bound of 2 glp_set_row_bnds(lp, i + 1, GLP_UP, 0, 2) # add this constraint to the constraint matrix glp_set_mat_row(lp, i + 1, p3, v) # solve the problem glp_simplex(lp) # for integer values glp_intopt(lp) # extract the maximum number of red hearts n_hearts = int(glp_mip_obj_val(lp)) # find the numbers of the circles with red heaarts hearts = [] for i in range(size): if glp_mip_col_val(lp, i + 1): hearts += [(glp_get_col_name(lp, i + 1)).decode()] return n_hearts, tuple(hearts), len(eqt) for rows in range(2, 12): # the sum of three consecutive numbers must # give the total number of circles # (x - 1) + x + (x + 1) = rows * (rows + 1) / 2 x, r = divmod(rows * (rows + 1), 6) # solve for this number of rows n, t, c = solve(rows) if rows > 3 and not r: if x - 1 <= n <= x + 1: print('solution! -> ', end='') print(rows, n, c) # now display the rows for r in range(1, rows + 1): s = ' ' * (rows // 2 + 6 - r) for c in range(1, r + 1): s += ' O' if str(r * (r - 1) // 2 + c) in t else ' -' print(s) print() |
Here are some of the configurations that the program finds:
There is also a solution with 22 red hearts in 11 rows but this takes more than 9 hours to find on my 2GHz i7 machine, which means that the prospect of going further with GLPK is bleak.