1# --------------------------------------------------------------------------
2# Source file provided under Apache License, Version 2.0, January 2004,
3# http://www.apache.org/licenses/
4# (c) Copyright IBM Corp. 2015, 2022
5# --------------------------------------------------------------------------
6
7"""
8The aim of the square example is to place a set of small squares of
9different sizes into a large square.
10
11See https://en.wikipedia.org/wiki/Squaring_the_square for details on this classical problem.
12
13This version is extended and uses matplotlib to draw the result at the end.
14Requires installation of numpy (installer) and following python packages:
15 "pip install matplotlib python-dateutil pyparsing"
16
17Please refer to documentation for appropriate setup of solving configuration.
18"""
19
20from docplex.cp.model import *
21
22
23#-----------------------------------------------------------------------------
24# Initialize the problem data
25#-----------------------------------------------------------------------------
26
27# Size of the englobing square
28SIZE_SQUARE = 112
29
30# Sizes of the sub-squares
31SIZE_SUBSQUARE = [50, 42, 37, 35, 33, 29, 27, 25, 24, 19, 18, 17, 16, 15, 11, 9, 8, 7, 6, 4, 2]
32NB_SUBSQUARE = len(SIZE_SUBSQUARE)
33
34#-----------------------------------------------------------------------------
35# Build the model
36#-----------------------------------------------------------------------------
37
38# Create model
39mdl = CpoModel()
40
41# Create array of variables for subsquares
42vx = [interval_var(size=SIZE_SUBSQUARE[i], name='X{}'.format(i), end=(0, SIZE_SQUARE)) for i in range(NB_SUBSQUARE)]
43vy = [interval_var(size=SIZE_SUBSQUARE[i], name='Y{}'.format(i), end=(0, SIZE_SQUARE)) for i in range(NB_SUBSQUARE)]
44
45# Create dependencies between variables
46for i in range(len(SIZE_SUBSQUARE)):
47 for j in range(i):
48 mdl.add( (end_of(vx[i]) <= start_of(vx[j])) | (end_of(vx[j]) <= start_of(vx[i]))
49 | (end_of(vy[i]) <= start_of(vy[j])) | (end_of(vy[j]) <= start_of(vy[i])))
50
51# To speed-up the search, create cumulative expressions on each dimension
52rx = sum([pulse(vx[i], SIZE_SUBSQUARE[i]) for i in range(NB_SUBSQUARE)])
53mdl.add(always_in(rx, (0, SIZE_SQUARE), SIZE_SQUARE, SIZE_SQUARE))
54
55ry = sum([pulse(vy[i], SIZE_SUBSQUARE[i]) for i in range(NB_SUBSQUARE)])
56mdl.add(always_in(ry, (0, SIZE_SQUARE), SIZE_SQUARE, SIZE_SQUARE))
57
58# Define search phases, also to speed-up the search
59mdl.set_search_phases([search_phase(vx), search_phase(vy)])
60
61
62#-----------------------------------------------------------------------------
63# Solve the model and display the result
64#-----------------------------------------------------------------------------
65
66# Solve model
67print('Solving model...')
68res = mdl.solve(TimeLimit=20, LogPeriod=50000)
69print('Solution: ')
70res.print_solution()
71
72import docplex.cp.utils_visu as visu
73if res and visu.is_visu_enabled():
74 import matplotlib.pyplot as plt
75 import matplotlib.cm as cm
76 from matplotlib.patches import Polygon
77
78 # Plot external square
79 print('Plotting squares...')
80 fig, ax = plt.subplots()
81 plt.plot((0, 0), (0, SIZE_SQUARE), (SIZE_SQUARE, SIZE_SQUARE), (SIZE_SQUARE, 0))
82 for i in range(len(SIZE_SUBSQUARE)):
83 # Display square i
84 sx, sy = res.get_var_solution(vx[i]), res.get_var_solution(vy[i])
85 (sx1, sx2, sy1, sy2) = (sx.get_start(), sx.get_end(), sy.get_start(), sy.get_end())
86 poly = Polygon([(sx1, sy1), (sx1, sy2), (sx2, sy2), (sx2, sy1)], fc=cm.Set2(float(i) / len(SIZE_SUBSQUARE)))
87 ax.add_patch(poly)
88 # Display identifier of square i at its center
89 ax.text(float(sx1 + sx2) / 2, float(sy1 + sy2) / 2, str(SIZE_SUBSQUARE[i]), ha='center', va='center')
90 plt.margins(0)
91 plt.show()