ASCII Exact Cover with Rectangles

Question

Challenge

Given a rectangular area arrange a group of rectangles such that they cover the rectangular area entirely.

Input

• An integer denoting the height.

• An integer denoting the width.

• The dimensions of the rectangles consisting of the following form: axb,cxd,... where a,b,c, and d are integers - any reasonable format is acceptable.

Output

An exact cover of the rectangular area.

Rectangles used to cover the area are represented in the following way:

2x3

00
00
00

or

000
000

1x3

0
0
0

or

000

Each rectangle is represented using a character 0-9 where 0 is used for the first rectangle inputted 1 for the second and so on. The max number of rectangles given in input is therefore 10.

Test Cases

Input 1

5
7
4x2,3x2,3x2,5x2,5x1

Output 1

0000111
0000111
2233333
2233333
2244444

Input 2

4
4
3x2,2x1,2x2,2x2

Output 2

0001
0001
2233
2233

Input 3

2
10
4x2,3x2,3x2

Output 3

0000111222
0000111222

Clarifications

• The dimensions of the rectangles used to cover the region are interchangeable e.g. for axb a could be the height or width same goes for b.
• If there are multiple solutions any of them is acceptable (just display 1).
• Assume all inputs are valid.
• You can have a full program or a function (inputs may be treated broadly as 3 separate arguments).
• Output to stdout (or something similar).
• This is code-golf so shortest answer in bytes wins.

Answer 1

APL (Dyalog Unicode), 76 bytes

⎕CY'dfns'
{⍺⍴v+.×(X m)⌿m←⊃⍪/(⍺∘{⍪↑,(⍳⍺)↓¨⊂⌽⊖⍺↑⍵⍴1}¨⊢∘⌽\2/⍵),⍤1¨2/↓∘.=⍨v←⍳≢⍵}

Try it online!

Dyalog APL comes with a built-in Exact Cover solver X, so the main part of the code is construction of the constraint matrix.

A constraint matrix is a boolean matrix where a column indicates a constraint, and a row indicates an action that satisfies some of the constraints. In the case of rectangle cover, an action is positioning of a specific rectangle at certain position and orientation, which satisfies two kinds of constraints: a specific rectangle is consumed, and the certain cells are covered by that rectangle.

For example, consider positioning a 2×3 rectangle in a 4×4 rectangular space. There are 12 ways to place it inside the space:

Horizontally
OOO. .OOO
OOO. .OOO
.... ....
.... ....

.... ....
OOO. .OOO
OOO. .OOO
.... ....

.... ....
.... ....
OOO. .OOO
OOO. .OOO

Vertically
OO.. .OO. ..OO
OO.. .OO. ..OO
OO.. .OO. ..OO
.... .... ....

.... .... ....
OO.. .OO. ..OO
OO.. .OO. ..OO
OO.. .OO. ..OO

If it is the second rectangle out of four rectangle pieces, a part of the constraint matrix would look like this (where type 1 constraints mark the rectangle used, and type 2 mark the cells occupied):

            <--           Type 2           -->
<-Type 1->  <-r1-->  <-r2-->  <-r3-->  <-r4-->
0 1 0 0     1 1 0 0  1 1 0 0  1 1 0 0  0 0 0 0
0 1 0 0     0 1 1 0  0 1 1 0  0 1 1 0  0 0 0 0
0 1 0 0     0 0 1 1  0 0 1 1  0 0 1 1  0 0 0 0
0 1 0 0     0 0 0 0  1 1 0 0  1 1 0 0  1 1 0 0
0 1 0 0     0 0 0 0  0 1 1 0  0 1 1 0  0 1 1 0
0 1 0 0     0 0 0 0  0 0 1 1  0 0 1 1  0 0 1 1
...

In the actual code, the fact that "there will always be a solution" is abused for the sake of golfing. It actually generates a matrix where type 2 comes before type 1, and the rectangle pieces are allowed to be partially overflowed to the top left. It still works since using an overflowed piece will always fail to cover the entire rectangular area.

⍝ Load dfns library to use the function X
⎕CY'dfns'

⍝ An inline function; ⍺←area (w,h), ⍵←n pieces
{
  v←⍳≢⍵    ⍝ Generate 0..n-1
  ↓∘.=⍨    ⍝ Generate Type 1 constraints as a nested array
  2/       ⍝ Two copies of each, to match with two orientations of each rect
  ,⍤1¨     ⍝ Concatenate row-wise with
  (...)    ⍝ the Type 2 constraints:
  2/⍵      ⍝   Two copies of each rectangle
  ⊢∘⌽\     ⍝   Flip the rows and columns at odd (0-based) indices
  ⍺∘{...}¨ ⍝   Generate boolean matrices for each rectangle:
  ⍺↑⍵⍴1    ⍝     Create the rectangle-shaped 1s, 0-filled to the size of the space
  ⌽⊖       ⍝     Reverse in both dimensions, so the 1s go to the bottom right
  (⍳⍺)↓¨⊂  ⍝     The above with leading rows/columns dropped in all possible ways
           ⍝     (all combinations of 0..h-1 rows and 0..w-1 columns dropped)
  ⍪↑,      ⍝     Format the result as Type 2 constraint sub-matrix
  m←⊃⍪/    ⍝ Vertically concatenate all the constraint sub-matrices
           ⍝ generated for each rectangle
  (X m)⌿m  ⍝ Solve the Exact Cover problem, and extract the rows
           ⍝ (the collection of rectangles that actually cover the area)
  v+.×     ⍝ Number the cells by the containing rectangle's 0-based index
  ⍺⍴       ⍝ Reshape the cells to the shape of the area
}

Answer 2

Python 3, 262 bytes

from numpy import*
def g(h,w,t,m,i):
 if[]==t:print(m);return
 u,v=t[0]
 for _ in'12':
  for r,c in argwhere(m<0):
   if(m[r:r+u,c:c+v]<0).all()and u+r<=h and v+c<=w:e=copy(m);e[r:r+u,c:c+v]=i;g(h,w,t[1:],e,i+1)
  u,v=v,u
f=lambda h,w,t:g(h,w,t,zeros((h,w))-1,0)

Called like: f(4,4,[(3,2),(2,1),(2,2),(2,2)]). It uses a brute force, recursive function that prints all solutions (uses fewer bytes).