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.
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
(0, 0), (41, 23), (42, 0), (0, 25), (22, 28), (25, 0), (25, 17), (36, 17), (36, 23), (22, 25)
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