from sys import stdout from itertools import combinations from mip import Model, xsum, maximize, BINARY import numpy as np m = Model() n = 10 # define grid point and generate variables grid = { (i, j): m.add_var("x({},{})".format(i, j), var_type=BINARY) for i in range(n) for j in range(n) } # return a set of all size-4 subsets of S def findsubsets(S): return set(combinations(S, 4)) # generate all size-4 subsets of grid subsets = findsubsets(set(grid.keys())) # check if 4 points form a square def is_square(Q): A = np.array(Q[0]) B = np.array(Q[1]) C = np.array(Q[2]) D = np.array(Q[3]) center = (A + B + C + D) / 4 v1 = A - center v2 = np.array([-v1[1], v1[0]]) P2 = center - v1 P3 = center + v2 P4 = center - v2 if {tuple(B), tuple(C), tuple(D)} == {tuple(P2), tuple(P3), tuple(P4)}: return True else: return False # check every subset for square squares = [] for Q in subsets: # Q = ((x0,y0),(x1,y1),(x2,y2),(x3,y3)) if is_square(Q): squares.append(Q) squares = set(squares) # set of all possible squares m.objective = maximize(xsum(grid[(i, j)] for i in range(n) for j in range(n))) # for every possible square only at most 3 points can be placed for tup in squares: m += xsum(grid[(tup[i][0], tup[i][1])] for i in range(4)) <= 3 m.optimize() # print best solution if m.num_solutions: output_string = "" for i in range(n): output_string += ( " ".join(["o" if m.vars[n * i + j].x >= 0.99 else "." for j in range(n)]) + "\n" ) stdout.write(output_string)