ASCII Exact Cover with Rectangles
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
}