# visu/squaring_square.py example¶

 ``` 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``` ```# -------------------------------------------------------------------------- # Source file provided under Apache License, Version 2.0, January 2004, # http://www.apache.org/licenses/ # (c) Copyright IBM Corp. 2015, 2022 # -------------------------------------------------------------------------- """ The aim of the square example is to place a set of small squares of different sizes into a large square. See https://en.wikipedia.org/wiki/Squaring_the_square for details on this classical problem. This version is extended and uses matplotlib to draw the result at the end. Requires installation of numpy (installer) and following python packages: "pip install matplotlib python-dateutil pyparsing" Please refer to documentation for appropriate setup of solving configuration. """ from docplex.cp.model import * #----------------------------------------------------------------------------- # Initialize the problem data #----------------------------------------------------------------------------- # Size of the englobing square SIZE_SQUARE = 112 # Sizes of the sub-squares SIZE_SUBSQUARE = [50, 42, 37, 35, 33, 29, 27, 25, 24, 19, 18, 17, 16, 15, 11, 9, 8, 7, 6, 4, 2] NB_SUBSQUARE = len(SIZE_SUBSQUARE) #----------------------------------------------------------------------------- # Build the model #----------------------------------------------------------------------------- # Create model mdl = CpoModel() # Create array of variables for subsquares vx = [interval_var(size=SIZE_SUBSQUARE[i], name='X{}'.format(i), end=(0, SIZE_SQUARE)) for i in range(NB_SUBSQUARE)] vy = [interval_var(size=SIZE_SUBSQUARE[i], name='Y{}'.format(i), end=(0, SIZE_SQUARE)) for i in range(NB_SUBSQUARE)] # Create dependencies between variables for i in range(len(SIZE_SUBSQUARE)): for j in range(i): mdl.add( (end_of(vx[i]) <= start_of(vx[j])) | (end_of(vx[j]) <= start_of(vx[i])) | (end_of(vy[i]) <= start_of(vy[j])) | (end_of(vy[j]) <= start_of(vy[i]))) # To speed-up the search, create cumulative expressions on each dimension rx = sum([pulse(vx[i], SIZE_SUBSQUARE[i]) for i in range(NB_SUBSQUARE)]) mdl.add(always_in(rx, (0, SIZE_SQUARE), SIZE_SQUARE, SIZE_SQUARE)) ry = sum([pulse(vy[i], SIZE_SUBSQUARE[i]) for i in range(NB_SUBSQUARE)]) mdl.add(always_in(ry, (0, SIZE_SQUARE), SIZE_SQUARE, SIZE_SQUARE)) # Define search phases, also to speed-up the search mdl.set_search_phases([search_phase(vx), search_phase(vy)]) #----------------------------------------------------------------------------- # Solve the model and display the result #----------------------------------------------------------------------------- # Solve model print('Solving model...') res = mdl.solve(TimeLimit=20, LogPeriod=50000) print('Solution: ') res.print_solution() import docplex.cp.utils_visu as visu if res and visu.is_visu_enabled(): import matplotlib.pyplot as plt import matplotlib.cm as cm from matplotlib.patches import Polygon # Plot external square print('Plotting squares...') fig, ax = plt.subplots() plt.plot((0, 0), (0, SIZE_SQUARE), (SIZE_SQUARE, SIZE_SQUARE), (SIZE_SQUARE, 0)) for i in range(len(SIZE_SUBSQUARE)): # Display square i sx, sy = res.get_var_solution(vx[i]), res.get_var_solution(vy[i]) (sx1, sx2, sy1, sy2) = (sx.get_start(), sx.get_end(), sy.get_start(), sy.get_end()) poly = Polygon([(sx1, sy1), (sx1, sy2), (sx2, sy2), (sx2, sy1)], fc=cm.Set2(float(i) / len(SIZE_SUBSQUARE))) ax.add_patch(poly) # Display identifier of square i at its center ax.text(float(sx1 + sx2) / 2, float(sy1 + sy2) / 2, str(SIZE_SUBSQUARE[i]), ha='center', va='center') plt.margins(0) plt.show() ```