Optimal grid shape filling with squares

Question

I recently developed a riddle for children. However, I would like an optimal solution.

The problem is this: you have this number made up of small squares

You have to fill it with big squares and score it in the following table:

| Square Size | 1x1 | 2x2 | 3x3 | 4x4 | 5x5 | 6x6 | 7x7 | 8x8 | |-------------|-----|-----|-----|-----|-----|-----|-----|-----| | Points | 0 | 4 | 10 | 20 | 35 | 60 | 84 | 120 | 

There are simply many possible solutions to test all of them. Some others have suggested dynamic programming, but I don’t know how to divide the figure into smaller ones, which together have the same optimal solution.

I would like to find a way to find optimal solutions to these problems in a reasonable amount of time (for example, a couple of days maximum on a regular desktop). The highest score so far found using the guessing algorithm, and some manual work - 1112.

Also welcomed are solutions to similar problems with combining subtasks. I do not need all the code. Outlines or ideas for the algorithm would be enough.

Note. The largest square that can fit is 8x8, so scores for large squares are not included.

 [[1,1,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,1], [1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1], [1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1], [0,0,0,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0], [0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1], [0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1], [1,0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1], [1,1,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1], [1,1,1,0,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,0,0], [0,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,1,0,0,0], [0,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0], [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0], [0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1], [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1], [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1], [0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1], [0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0], [0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0], [0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0], [0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1], [0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1], [0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1], [0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1], [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1], [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1], [0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1], [0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1], [0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1], [1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1], [1,1,1,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1], [1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1], [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1], [1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1], [1,1,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1], [1,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1], [1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,1,1,1], [1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,1,1], [0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1], [0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1], [0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]]; 

Answer 1

Here is a fairly general prototype using Mixed-integer-programming , which solves your instance optimally (I got the value 1112, as you yourself deduced) and can solve others too.

In general, your problem is np-complete , and this complicates the work (there are some cases that will be the problem).

Although I suspect that the SAT-solver and CP-solver approaches may be more powerful (due to the combinatorial nature, I was even surprised that the MIP works here), the MIP approach also has some advantages:

• MIP solvers complete (like SAT and CP, but many randomness-based heuristics are not):
• If necessary, many commercial-grade solvers are available.
• The drug is quite simple (especially compared to SAT, SAT formulations will need to advance no more than k from n-formulations (for scoring formulations) that grow subquadratically (the naive approach grows exponentially)! Exist, but not trivial)
• Optimization-lens is just natural (SAT and CP need iterative refinement = solve with some lower bound, increment is connected and solves)
• MIP solvers can also be powerful enough to obtain approximations of the optimal solution, as well as for some proven boundaries (for example, optimal below x)

The following code is implemented in python using publicly available scientific tools (all of this is open source ). This allows you to set the range of tiles (for example, adding 9x9 tiles) and various cost functions. Comments should be enough to understand ideas. It will use some (possibly better) open source MIP solver, but can also use commercial ones (using outcommented line shows).

the code

 import numpy as np import itertools from collections import defaultdict import matplotlib.pyplot as plt # visualization only import seaborn as sns # "" from pulp import * # MIP-modelling & solver """ INSTANCE """ instance = np.asarray([[1,1,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,1], [1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1], [1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1], [0,0,0,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0], [0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1], [0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1], [1,0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1], [1,1,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1], [1,1,1,0,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,0,0], [0,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,1,0,0,0], [0,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0], [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0], [0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1], [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1], [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1], [0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1], [0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0], [0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0], [1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0], [0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0], [0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1], [0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1], [0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1], [0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1], [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1], [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1], [0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1], [0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1], [0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1], [1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1], [1,1,1,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1], [1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1], [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1], [1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1], [1,1,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1], [1,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1], [1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,1,1,1], [1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,1,1], [0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1], [0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1], [0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]], dtype=bool) def plot_compare(instance, solution, subgrids): f, (ax1, ax2) = plt.subplots(2, sharex=True, sharey=True) sns.heatmap(instance, ax=ax1, cbar=False, annot=True) sns.heatmap(solution, ax=ax2, cbar=False, annot=True) plt.show() """ PARAMETERS """ SUBGRIDS = 8 # 1x1 - 8x8 SUGBRID_SCORES = {1:0, 2:4, 3:10, 4:20, 5:35, 6:60, 7:84, 8:120} N, M = instance.shape # free / to-fill = zeros! """ HELPER FUNCTIONS """ def get_square_covered_indices(instance, pos_x, pos_y, sg): """ Calculate all covered tiles when given a top-left position & size -> returns the base-index too! """ N, M = instance.shape neighbor_indices = [] valid = True for sX in range(sg): for sY in range(sg): if pos_x + sX < N: if pos_y + sY < M: if instance[pos_x + sX, pos_y + sY] == 0: neighbor_indices.append((pos_x + sX, pos_y + sY)) else: valid = False break else: valid = False break else: valid = False break return valid, neighbor_indices def preprocessing(instance, SUBGRIDS): """ Calculate all valid placement / tile-selection combinations """ placements = {} index2placement = {} placement2index = {} placement2type = {} type2placement = defaultdict(list) cover2index = defaultdict(list) # cell covered by placement-index index_gen = itertools.count() for sg in range(1, SUBGRIDS+1): # sg = subgrid size for pos_x in range(N): for pos_y in range(M): if instance[pos_x, pos_y] == 0: # free feasible, covering = get_square_covered_indices(instance, pos_x, pos_y, sg) if feasible: new_index = next(index_gen) placements[(sg, pos_x, pos_y)] = covering index2placement[new_index] = (sg, pos_x, pos_y) placement2index[(sg, pos_x, pos_y)] = new_index placement2type[new_index] = sg type2placement[sg].append(new_index) cover2index[(pos_x, pos_y)].append(new_index) return placements, index2placement, placement2index, placement2type, type2placement, cover2index def calculate_collisions(placements, index2placement): """ Calculate collisions between tile-placements (position + tile-selection) -> only upper triangle is used: a < b! """ n_p = len(placements) coll_mat = np.zeros((n_p, n_p), dtype=bool) # only upper triangle is used for pA in range(n_p): for pB in range(n_p): if pA < pB: covered_A = placements[index2placement[pA]] covered_B = placements[index2placement[pB]] if len(set(covered_A).intersection(set(covered_B))) > 0: coll_mat[pA, pB] = True return coll_mat """ PREPROCESSING """ placements, index2placement, placement2index, placement2type, type2placement, cover2index = preprocessing(instance, SUBGRIDS) N_P = len(placements) coll_mat = calculate_collisions(placements, index2placement) """ MIP-MODEL """ prob = LpProblem("GridFill", LpMaximize) # Variables X = np.empty(N_P, dtype=object) for x in range(N_P): X[x] = LpVariable('x'+str(x), 0, 1, cat='Binary') # Objective placement_scores = [SUGBRID_SCORES[index2placement[p][0]] for p in range(N_P)] prob += lpDot(placement_scores, X), "Score" # Constraints # C1: Forbid collisions of placements for a in range(N_P): for b in range(N_P): if a < b: # symmetry-reduction if coll_mat[a, b]: prob += X[a] + X[b] <= 1 # not both! """ SOLVE """ print('solve') #prob.solve(GUROBI()) # much faster commercial solver; if available prob.solve(PULP_CBC_CMD(msg=1, presolve=True, cuts=True)) print("Status:", LpStatus[prob.status]) """ INTERPRET AND COMPLETE SOLUTION """ solution = np.zeros((N, M), dtype=int) for x in range(N_P): if X[x].value() > 0.99: sg, pos_x, pos_y = index2placement[x] _, positions = get_square_covered_indices(instance, pos_x, pos_y, sg) for pos in positions: solution[pos[0], pos[1]] = sg fill_with_ones = np.logical_and((solution == 0), (instance == 0)) solution[fill_with_ones] = 1 """ VISUALIZE """ plot_compare(instance, solution, SUBGRIDS) 

Assumptions / Nature of the Algorithm

• There are no restrictions describing the need for each free cell.
  • It works when there are no negative ratings.
  • A positive score will be awarded if it improves the goal.
  • A zero point (for example, your example) may leave some cells free, but they turned out to be 1 (added after optimization)

Performance

This is a good example of a mismatch between open-source and commercial solvers. The two solvers were cbc and Gurobi .

Sample cbc output (only some end parts)

 Result - Optimal solution found Objective value: 1112.00000000 Enumerated nodes: 0 Total iterations: 307854 Time (CPU seconds): 2621.19 Time (Wallclock seconds): 2627.82 Option for printingOptions changed from normal to all Total time (CPU seconds): 2621.57 (Wallclock seconds): 2628.24 

Requires: ~ 45 minutes

Gurobi Example Example

 Explored 0 nodes (7004 simplex iterations) in 5.30 seconds Thread count was 4 (of 4 available processors) Optimal solution found (tolerance 1.00e-04) Best objective 1.112000000000e+03, best bound 1.112000000000e+03, gap 0.0% 

6 seconds required

General remarks about crucial performance

• Gurobi should have much more functionality, recognizing the nature of the problem and using the appropriate hyperparameters inside
• I also think that there are some SAT-based approaches used internally (since one of the main developers wrote his dissertation mainly about combining these very different algorithmic methods).
• We use much better heuristics that can quickly provide non-optimal solutions (which will help in the next steps)

Output example: the optimal solution with a score of 1112 (click to enlarge)

Answer 2

You can reformulate the problem in another NP-hard problem :-)

Create a weighted graph where the vertices are all possible squares that can be placed on a board with weights relative to the size, and the edges between the intersecting squares. There is no need to represent 1x1 squares, as the weight is zero.

eg. for a simple empty 3x3 board, there are: - 5 vertices: one 3x3 and four 2x2, - 7 edges: four between 3x3 squares and 2x2 square and six between each pair of 2x2 squares.

Now the problem is to find the maximum independent weight .

I am not familiar with this topic, but from the Wikipedia description it seems that a reasonably fast algorithm can exist. This graph is not part of one of the classes with the well-known polynomial time algorithm, but it is pretty close to a graph free of P5. It seems to me that the only possibility is to have P5 in this graph between 2x2 squares, which means having a strip of width 2 of length 5. There is one in the lower left corner. These areas can be covered (deleted) before finding an independent set without losing a single or very little optimal solution.

Answer 3

(This is not a complete answer, I'm just sharing what I'm working on so we can collaborate.)

I think that a good first step is to convert the binary grid, giving each cell the value of the maximum size of the square that the cell can be in the upper left corner, for example:

 0,0,3,2,1,0,3,2,2,2,2,1,0,0,0,0,0,0,2,1,0,0,0,0,0,2,1,0,0,0 0,0,2,2,2,3,3,2,1,1,1,1,0,0,0,3,3,3,3,3,3,2,1,0,0,1,2,1,0,0 0,2,1,1,1,2,3,2,1,0,0,0,0,3,2,2,2,2,2,2,3,3,2,1,0,0,3,2,1,0 3,2,1,0,0,1,3,2,1,0,0,0,3,2,2,1,1,1,1,1,2,3,3,2,1,0,2,2,2,1 3,3,2,1,0,0,2,2,2,1,0,3,2,2,1,1,0,0,0,0,1,2,4,3,2,2,1,1,1,1 2,3,3,2,1,0,2,1,1,1,2,3,2,1,1,0,0,0,0,0,0,1,3,3,2,1,1,0,0,0 1,2,3,4,3,2,1,1,0,0,1,3,2,1,0,0,0,0,0,0,0,0,2,2,2,1,0,0,0,0 0,1,2,3,3,2,1,0,0,0,0,2,2,1,0,0,0,0,0,0,0,0,2,1,1,2,2,2,1,0 0,0,1,2,3,2,1,0,0,0,0,1,2,1,0,0,0,0,0,0,0,0,2,1,0,1,1,2,1,0 0,0,0,1,2,2,1,0,0,0,0,0,2,1,0,0,0,0,0,0,0,2,1,1,0,0,0,3,2,1 1,0,0,0,1,2,1,0,0,0,0,0,4,3,2,1,0,0,0,4,3,2,1,0,0,0,0,2,2,1 2,1,0,0,0,1,2,1,0,0,5,5,4,4,4,4,4,4,4,5,5,4,3,2,1,0,0,1,2,1 3,2,1,0,0,0,1,6,6,5,4,4,4,3,3,3,3,3,3,4,4,5,4,3,2,1,0,0,1,1 3,2,1,0,0,0,0,6,5,5,4,3,3,3,2,2,2,2,2,3,3,4,5,4,3,2,1,0,0,0 3,2,2,2,2,7,6,6,5,4,4,3,2,2,2,1,1,1,1,2,2,3,5,5,4,3,2,1,0,0 2,2,1,1,1,7,6,5,5,4,3,3,2,1,1,1,0,0,0,1,1,2,4,6,5,4,3,2,1,0 2,1,1,0,0,7,6,5,4,4,3,2,2,1,0,0,0,0,0,0,0,1,3,6,5,4,3,2,1,0 1,1,0,0,8,7,6,5,4,3,3,2,1,1,0,0,0,0,0,0,0,0,2,7,6,5,4,3,2,1 1,0,0,0,8,7,6,5,4,3,2,2,1,0,0,0,0,0,0,0,0,0,1,7,6,5,4,3,2,1 0,0,0,7,8,7,6,5,4,3,2,1,1,0,0,0,0,0,0,0,0,0,0,6,6,5,4,3,2,1 0,0,0,6,8,7,6,5,4,3,2,1,0,0,0,0,0,0,0,0,0,0,0,6,5,5,4,3,2,1 0,0,0,5,7,7,6,5,4,3,2,1,0,0,0,0,0,0,0,0,0,0,0,6,5,4,4,3,2,1 0,0,0,4,6,7,7,6,5,4,3,2,1,0,0,0,0,0,0,0,0,0,6,5,5,4,3,3,2,1 0,0,0,3,5,6,7,7,6,5,4,3,2,1,0,0,0,0,0,0,0,6,6,5,4,4,3,2,2,1 1,0,0,2,4,5,6,7,8,7,6,5,4,3,2,1,0,0,0,7,6,6,5,5,4,3,3,2,1,1 1,0,0,1,3,4,5,6,7,7,8,8,8,8,8,8,7,7,6,6,6,5,5,4,4,3,2,2,1,0 2,1,0,0,2,3,4,5,6,6,7,7,8,7,7,7,7,6,6,5,5,5,4,4,3,3,2,1,1,0 2,1,0,0,1,2,3,4,5,5,6,6,8,7,6,6,6,6,5,5,4,4,4,3,3,2,2,1,0,0 3,2,1,0,0,1,2,3,4,4,5,5,8,7,6,5,5,5,5,4,4,3,3,3,2,2,1,1,0,0 3,2,1,0,0,0,1,2,3,3,4,4,8,7,6,5,4,4,4,4,3,3,2,2,2,1,1,0,0,0 4,3,2,1,0,0,0,1,2,2,3,3,8,7,6,5,4,3,3,3,3,2,2,1,1,1,0,0,0,0 3,3,2,1,0,0,0,0,1,1,2,2,8,7,6,5,4,3,2,2,2,2,1,1,0,0,0,0,0,0 2,2,2,2,1,0,0,0,0,0,1,1,8,7,6,5,4,3,2,1,1,1,1,0,0,0,0,0,0,0 1,1,1,2,1,0,0,0,0,0,0,0,8,7,6,5,4,3,2,1,0,0,0,0,0,0,0,0,0,0 0,0,0,2,1,0,0,0,0,0,0,0,8,8,7,6,5,4,3,2,1,0,0,0,0,0,0,0,0,0 0,0,0,2,1,0,0,0,0,0,0,6,8,7,7,6,6,5,4,3,2,1,0,0,0,0,0,0,0,0 0,0,0,2,2,2,3,3,3,3,3,5,7,7,6,6,5,5,4,3,3,3,3,2,1,0,0,0,0,0 0,0,3,2,1,1,3,2,2,2,2,4,6,6,6,5,5,4,4,3,2,2,2,2,1,0,0,0,0,0 0,0,3,2,1,0,3,2,1,1,1,3,5,5,5,5,4,4,3,3,2,1,1,2,1,0,0,0,0,0 0,0,3,2,1,0,3,2,1,0,0,2,4,4,4,4,4,3,3,2,2,1,0,2,1,0,0,0,0,0 0,4,3,2,1,0,3,2,1,0,0,1,3,3,3,4,3,3,2,2,1,1,0,2,1,0,0,0,0,0 0,4,3,2,1,0,3,2,1,0,0,0,2,2,2,3,3,2,2,1,1,0,0,2,1,0,0,0,0,0 0,4,3,2,1,0,3,2,1,0,0,0,1,1,1,2,2,2,1,1,0,0,0,2,1,0,0,0,0,0 3,3,3,2,1,0,3,2,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,3,2,1,0,0,0,0 2,2,2,2,1,0,2,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,1,0,0,0,0 1,1,1,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0 

If you want to view all the parameters using brute force, try each size of the square, which the cell can be an angle (including 1x1), mark the square with zeros, adjust the cell values ​​to 7 places to the left / above the square and recursion with a new grid.

If you iterate through the cells from top to bottom and from left to right, you will only need to copy the grid, starting from the current row to the bottom row, and you will only need to adjust the cell values ​​to 7 places to the left of the area.

The JS code I tested quickly runs for the top 2 or 3 rows of the grid (result: 24 and 44), takes 8 seconds to finish the top 4 lines (result: 70) and 30 minutes for 5 lines (result: 86). I do not try 6 lines.

But, as you can see from this grid, the number of possibilities is so great that brute force will never be an option. On the other hand, at first I try something like adding large squares, and then filling the remaining space with smaller squares, I will never guarantee the optimal result, I'm afraid. It is too easy to come up with examples that could interfere with such a strategy.

 7,6,5,4,3,2,1,0,0,0,0,0,0,7,6,5,4,3,2,1 6,6,5,4,3,2,1,0,0,0,0,0,0,6,6,5,4,3,2,1 5,5,5,4,3,2,1,0,0,0,0,0,0,5,5,5,4,3,2,1 4,4,4,4,3,2,1,0,0,0,0,0,0,4,4,4,4,3,2,1 3,3,3,3,3,2,1,0,0,0,0,0,0,3,3,3,3,3,2,1 2,2,2,2,2,2,1,0,0,0,0,0,0,2,2,2,2,2,2,1 1,1,1,1,1,1,8,7,6,5,4,3,2,1,1,1,1,1,1,1 0,0,0,0,0,0,7,7,6,5,4,3,2,1,0,0,0,0,0,0 0,0,0,0,0,0,6,6,6,5,4,3,2,1,0,0,0,0,0,0 0,0,0,0,0,0,5,5,5,5,4,3,2,1,0,0,0,0,0,0 0,0,0,0,0,0,4,4,4,4,4,3,2,1,0,0,0,0,0,0 0,0,0,0,0,0,3,3,3,3,3,3,2,1,0,0,0,0,0,0 0,0,0,0,0,0,2,2,2,2,2,2,2,1,0,0,0,0,0,0 7,6,5,4,3,2,1,1,1,1,1,1,1,7,6,5,4,3,2,1 6,6,5,4,3,2,1,0,0,0,0,0,0,6,6,5,4,3,2,1 5,5,5,4,3,2,1,0,0,0,0,0,0,5,5,5,4,3,2,1 4,4,4,4,3,2,1,0,0,0,0,0,0,4,4,4,4,3,2,1 3,3,3,3,3,2,1,0,0,0,0,0,0,3,3,3,3,3,2,1 2,2,2,2,2,2,1,0,0,0,0,0,0,2,2,2,2,2,2,1 1,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1 

In the above example, placing an 8x8 square in the center and four 6x6 squares in the corners gives a lower score than placing a 6x6 square in the center and four 7x7 squares in the corners; therefore, a greedy approach based on using the maximum possible square will not give an optimal result.

---

That’s how I got the selection of zones connected by corridors with a maximum width of 3, and the brute force algorithm on smaller grids. If the border does not have an orange zone, adding two more cells does not increase the account of the isolated zone, so these cells can be used unconditionally by the main zone.