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)