Square tiling

Problem

The problem is to pack a set of squares into a larger rectangle so that no squares overlap. Each square has an integer size and must be placed so that the square’s borders are parallel to the rectangle’s. The total surface area of the squares equal the surface area of the rectangle, so all have to be used.

Code

 1 require 'rubygems'
 2 require 'gecoder'
 3 
 4 # Solves the square tiling problem. The objective is to pack supplied squares 
 5 # into a bigger rectangle so that there is no overlap.
 6 class SquareTiling
 7   include Gecode::Mixin
 8 
 9   # Takes the width and height of the rectangle to pack the squares into. Then
10   # the sizes of the squares that should be packed into the rectangle. The sizes
11   # must be sorted.
12   def initialize(width, height, square_sizes)
13     @sizes = square_sizes
14     @square_count = @sizes.size
15     
16     # The coordinates of the placed squares.
17     @xs = int_var_array(@square_count, 0..(width - @sizes.min))
18     @ys = int_var_array(@square_count, 0..(height - @sizes.min))
19     
20     # The essential constraints of the problem.
21     @square_count.times do |i|
22       # Each square must be placed within the bounds
23       @xs[i].must <= width - @sizes[i]
24       @ys[i].must <= height - @sizes[i]
25       
26       # Pairwise conditions, no pair of squares may overlap.
27       0.upto(i - 1) do |j|
28         # That the two squares don't overlap means that i is left of j, 
29         # or j is left of i, or i is above j, or j is above i.
30         ((@xs[j] - @xs[i]).must >= @sizes[i]) | 
31           ((@xs[i] - @xs[j]).must >= @sizes[j]) | 
32           ((@ys[j] - @ys[i]).must >= @sizes[i]) | 
33           ((@ys[i] - @ys[j]).must >= @sizes[j])
34       end
35     end
36     
37     # A couple of implied constraints that only serve to make the solving 
38     # faster:
39 
40     # The combined size of all squares occupying a column must be equal to the 
41     # total height.
42     occupied_length_must_equal_total_length(height, width, @xs)
43     # The combined size of all squares occupying a row must be equal to the 
44     # total width.
45     occupied_length_must_equal_total_length(width, height, @ys)
46 
47     # Symmetry-breaking constraint: Order squares of the same size.
48     @square_count.times do |i|
49       @xs[i].must <= @xs[i+1] if @sizes[i] == @sizes[i+1]
50     end
51 
52     # Place the squares left to right on the x-axis first, then the y-axis.
53     branch_on @xs, :variable => :smallest_min, :value => :min
54     branch_on @ys, :variable => :smallest_min, :value => :min
55   end
56   
57   # Constrains the combined length of the squares in the same row or column to
58   # equal +total_length+ in the axis of the specified coordinates +coords+, 
59   # which is +axist_length+ long.
60   def occupied_length_must_equal_total_length(total_length, axis_length, coords)
61     axis_length.times do |i|
62       # We create an array of boolean variables and constrain it so that element
63       # +j+ is true iff square +j+ occupies +i+ (+i+ being a row or column).
64       occupied = bool_var_array(@square_count)
65       occupied.each_with_index do |is_occupying, j|
66         coords[j].must_be.in((i - @sizes[j] + 1)..i, :reify => is_occupying)
67       end
68       
69       # Constrain the combined length of squares that are occupying +i+ to equal
70       # the total length. We multiply the sizes with the boolean variables 
71       # since a boolean in linear equation is 0 if assigned false and 1 if 
72       # assigned true. Hence we will mask out the sizes of any squares not in 
73       # +i+.
74       occupied_sizes = occupied.zip(@sizes).map{ |bool, size| bool*size }
75       occupied_sizes.inject(0){ |sum, x| x + sum }.must.equal(total_length, 
76         :strength => :domain)
77     end
78   end
79   
80   # Displays the coordinates of the squares.
81   # TODO: Something more impressive. 
82   def to_s
83     @xs.values.zip(@ys.values).map{ |x,y| "(#{x}, #{y})"}.join(', ')
84   end
85 end
86 
87 puts SquareTiling.new(65, 47, [25, 24, 23, 22, 19, 17, 11, 6, 5, 3]).solve!.to_s

Output

(0, 0), (41, 23), (42, 0), (0, 25), (22, 28), (25, 0), (25, 17), (36, 17), (36, 23), (22, 25)

Notes

It can also handle larger problems. The following one takes about a minute.
puts(SquareTiling.new(112, 112, [50, 42, 37, 35, 33, 29, 27, 25, 24, 19, 18, 
  17, 16, 15, 11, 9, 8, 7, 6, 4, 2]).solve! || 'Failed').to_s