Arranging arbitrary shapes to fill a rectangular space A while ago, I posted a challenge asking to determine whether or not it's possible to arrange arbitrary rectangles to fill a rectangular space, here. That got answers, so clearly it was too easy. (Just kidding, it was fairly challenging, congrats to the answerers :D)

Challenge

Given a bunch of arbitrary shapes (consisting of 1x1 square tiles) (up to 100 with a combined area of at most 1000), can you arrange them to fill a rectangular space, without rotations or reflections?

A shape is valid as input if it has at least 1 tile and all tiles are connected to each other by edges. For example:

Valid:

XXX
X X
XXX


Invalid:

XXX
X
 XX


The shapes will be represented in input by using a non-whitespace character X, spaces, and newlines. Individual shapes will be separated by two newlines (i.e. split on \n\n). You can choose to use LF, CR, or CRLF as a newline. Alternatively, you can choose to use LF or CR as a single newline and CRLF as a double-newline for separating shapes. Please specify in your answer what you choose.

For example, this would be the input format for a 2x2 square and a 3x3 "donut":

XX
XX

XXX
X X
XXX
(Optional trailing newline or double-newline)


The output should be either any truthy value or a consistent falsy value (but not an error). For example, you may output the valid arrangement if one exists or false, but you cannot error if there is no valid arrangement, neither can you output different values for having no valid arrangement.

Test Cases

Test Case 1

XXXX
X  X
XX X

X
X

X

TRUE


Valid Arrangement:

XXXX
XYYX
XXYX


Test Case 2

XXXX
XX

X

FALSE


Test Case 3

XXXXXX
X X  X
X XXX

XX

X
X

X

TRUE


Valid Arrangement:

XXXXXX
XYXZZX
XYXXXA


Test Case 4

XX
X

 X
XX

XXX

X
X
X

TRUE


Valid Arrangement:

XXYZ
XYYZ
AAAZ


Notes


Each shape must be used exactly once in the arrangement
Shapes may not be rotated or reflected
The input can contain multiple identical shapes; in this case, each of those still needs to be used exactly once; that is, if two 5x3 rectangles are given in the input, two 5x3 rectangles must appear in the arrangement
Python 2, 434 bytes



lambda s:F([[' ']*sum(map(lambda s:len(s[0]),s)) for _ in' '*sum(map(len,s))],s)
L=len
R=range
def F(a,s):
 if not s:return len(set(tuple(l)for l in a if'X'in l))==len(set(tuple(l)for l in zip(*a)if'X'in l))==1
 c=s[0];h,w=L(c),L(c[0])
 for i in R(L(a)-h):
&#9;for j in R(L(a[0])-w):
&#9; T=1;A=[l[:]for l in a]
&#9; for y in R(h):
&#9;&#9;for x in R(w):
&#9;&#9; C=c[y][x]
&#9;&#9; if C&gt;' ':T&amp;=A[y+i][x+j]&lt;'!';A[y+i][x+j]=C
&#9; r=T and F(A,s[1:])
&#9; if r:return r


Try it online!

Takes input as a list of lists.

Returns True or None

Assumes that each line in a shape is padded to the length of that shape.

(based on my answer to Do the figures fit?)