Making one shape out of dissections of another

Question

Introduction

One question that I have come across recently is the possibility of dissecting a staircase of height 8 into 3 pieces, and then re-arranging those 3 pieces into a 6 by 6 square.

Namely, is it possible to dissect the following into 3 pieces:

x
xx
xxx
xxxx
xxxxx
xxxxxx
xxxxxxx
xxxxxxxx

And rearrange those 3 pieces into the following shape:

xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx

Task

In this challenge, you will be tasked to find out exactly this. Specifically, given two shapes created from adjacent (touching sides, not diagonally) squares of the same size and a natural number n, return whether it is possible to dissect one of the shapes into n pieces, with all cuts along the edges of the squares, and then rearrange those n pieces to form the other shape. Just like the input shapes, each piece also has to be formed from adjacent squares and thus form one contiguous region. The pieces can be moved, rotated, and flipped in any way in order to form the other shape, but nothing else like shrinking or stretching the piece. The shapes can be represented in any reasonable form, including a 2d matrix with one value representing empty space and the other representing the actual shape, or a list of coordinates representing the positions of each individual square.

Additionally, you can assume that both shapes will consist of the same amount of squares, and that n will never exceed the number of squares within either of the shapes.

This is code-golf, so the shortest code in bytes wins!

Test Cases

In these test cases, each square is represented by one #, and an empty space is represented by a space.

I made all the test cases by hand so tell me if there are any mistakes.

Truthy

shape 1
shape 2
n
-------------------------------------
x
xx
xxx
xxxx
xxxxx
xxxxxx
xxxxxxx
xxxxxxxx

xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx

3

xxx
 xxx
xx
x

xxxxx
x xxx

3

xxxx
xxxx
xxxx
xxxx

xxxxx
x   x
x   x
x   x
xxxxx

4

x
x
xxx
 xxx
xx
x

xxxxx
xxxxxx

10

Falsey

shape 1
shape 2
n
-------------------------------------
xxx
xxx

xxxxx
 x

2

xxxx
xxxx
xxxx
xxxx

xxxxx
x   x
x   x
x   x
xxxxx

3

###
###
###

#########

2

#####
 ## #
### #
  ##

#
##
###
####
#
##
 #

3

Answer 1

Python3, 1163 bytes:

import itertools as I
E=enumerate
Q=lambda b:[(x,y)for x,r in E(b)for y,t in E(r)if t]
R=lambda x,f,n=3:[]if 0==n else[(X:=[*zip(*x)])]+R([X[::-1],[i[::-1]for i in X]][f],f,n-1)
D=[(0,1),(0,-1),(1,0),(-1,0)]
def V(t):
 q=[t.pop(0)]
 while q:
  x,y=q.pop(0)
  for X,Y in D:
   if(c:=(x+X,y+Y))in t:q+=[c];t.remove(c)
 return[]==t
def W(a,b):
 for i in b:
  q=[(a[0],i,{*a}-{a[0]},{*b}-{i},[a[0]],[i])]
  while q:
   (x,y),(j,k),A,B,S,s=q.pop()
   if not A:yield B-{*s};break
   F=0
   for X,Y in D:
    c,C=(x+X,y+Y),(j+X,k+Y)
    if c in A and c not in S and C in B:q+=[(c,C,A-{c},B,S+[c],s+[C])]
    elif c in A and c not in S and C not in B:F=1
   if F:break
def f(a,b,n):
 q,G,g,P=[(Q(a),Q(b),n)],eval(str(a)),eval(str(b)),[]
 while q:
  q=sorted(q,key=lambda x:len(x[0]))
  a,b,n=q.pop(0)
  if[]==[*a]+[*b] and n==0:return 1
  if all([a,b,n]):
   for i,_ in[*E(a,1)][::-1]:
    for t in I.combinations(a,i):
     if V([*t]):
      T=[[0 for _ in i]for i in G]
      for X,Y in t:T[X][Y]=1
      for o in[T,*R(T[::-1],0),*R([u[::-1]for u in T],1)]:
       if Q(o):
        for B in W(Q(o),b):
         if str(p:=([*{*a}-{*t}],B,n-1))not in P:q+=[p];P+=[str(p)]

Try it online!

Answer 2

Vyxal, 60 bytes

ƛṖvøṖÞf'L⁰=;'ƛhw"λhn÷:k□ẊṠJ↔";Ẋ≈;A;ƛƛ3(:k+v*Ṙ)Wƛgv-s;g;s;;ƒ↔

Try it Online!

Very slow. Takes input as a list of lists of coordinates of the two shapes and then the number pieces. Outputs truthy value if it is possible and falsy otherwise. Works by finding all possible dissections into \$n\$ connected pieces for both of the shapes and then checking if they have any in common.

Get all dissections into \$n\$ pieces:

ṖvøṖÞf'L⁰=;

Keep only those where all the pieces are connected:

'ƛhw"λhn÷:k□ẊṠJ↔";Ẋ≈;A;

Transform all of the pieces into a unique representation by getting all rotations, sorting the coordinates by dictionary ordering, translating them so the first coordinate is [0, 0] and then taking the smallest one.

ƛƛ3(:k+v*Ṙ)Wƛgv-s;g;s;