How should I tile my kitchen?
APL (Dyalog Unicode), 193 bytes

{G←{⍵⊃⍨⊃⍋(+/' '=,)¨⍵}
G{s←,30-⍳,⍨61
G,⊢∘⊂⌺30 30⊢((≢a)/⍪' '~⍨,x)@(B∘.+a)⊢''⍴⍨(⍴b)+⊃⌈/a←(⊢-⌊/)(⊃+/)¨s×⊂⍵}¨o/⍨(⍱/X∊⍨+/,-/)¨o←,∘.,⍨⊂¨∪{⍵/⍨0&lt;2⊥¨×⍵}(,B∘.-⍸b&lt;(1∊⊢)⌺3 3⊢b)~X←,B∘.-B←⍸b←(⍉0,⌽)⍣4⊢' '≠x←⍵}

Try it online!
A monadic dfn that takes a matrix of characters and returns the 30-by-30 matrix of a possible tiling with minimal blanks. Runs in 5 seconds for the smallest test case and in under a minute for the last one.
The idea
The task looks pretty straightforward at first glance, but it was surprisingly hard to derive a valid solution, and even harder to get one that &quot;runs in a reasonable amount of time&quot; (which somewhat explains why it was unanswered so far).
The first obstacle was that there are infinitely many possible tiling vectors. I solved this by limiting the vectors to the ones where the original tile and the moved tile share at least a point. If ab is the given tile, this means the following movements are considered as tiling vector candidates:
                                        AB   AB  AB  AB   AB
ABab    ab   ab  ab  ab   ab    abAB  ab    ab   ab   ab    ab
      AB    AB   AB   AB    AB

Then I filter out redundant ones (keeping only one of \$v\$ or \$w\$ when \$v = -w\$), generate all possible pairs of these candidate tiling vectors, and only keep the ones \$v, w\$ where neither \$v+w\$ nor \$v-w\$ movement overlaps with the original tile.
Reasoning: We know that the pairs of tiles at offsets \$(0, v)\$ and \$(0, w)\$ do not overlap, and therefore \$(v, v+w)\$ and \$(w, v+w)\$. Once it is known that \$(0, v+w)\$ and \$(v, w)\$ (alternatively \$(0, v-w)\$) pairs are safe, we know that \$(0, v, w, v+w)\$ are mutually safe, and by translation in four directions \$v, w, -v, -w\$, the entire infinite tiling is safe.
Given a full list of candidate vector pairs, I chose a naive way: for each vector pair, generate a large enough board of actual tiling, extract all 30-by-30 regions, and choose the one with the smallest number of blanks. For that, I used \$-30 \le a,b \le 30\$ for the formula \$av + bw\$. In order to prevent the memory (and execution time) blowing up, I apply this filtering twice, first within each vector pair, and then across all minimally chosen boards.
Ungolfed
The code changed a lot while golfing, but the core idea remains the same.
f←{
  ⍝ A boolean matrix where 1 means non-blanks, padded once to all directions
  bool←(⍉0,,∘0)⍣2⊢' '≠x←⍵
  ⍝ Spread 1s to adjacent cells (8 directions)
  padded←({1∊⍵}⌺3 3&gt;⊢)bool
  ⍝ Extract the coordinates of ones
  cbool←⍸bool
  cpadded←⍸padded
  ⍝ badoffs: All offsets that move a cell to already occupied cell
  ⍝ offs: All offsets that move a cell to a cell adjacent to the tile,
  ⍝       badoffs removed and (negative, any) and (zero, negative) removed
  offs←∪{⍵/⍨0&lt;2⊥¨×⍵}(,cbool∘.-cpadded)~badoffs←,cbool∘.-cbool
  ⍝ Pairs of valid offsets
  offpairs←,∘.,⍨⊂¨offs
  ⍝ Remove offset pairs (v,w) if v+w or v-w is bad
  filter←{⍱/(⍺+⍵)(⍺-⍵)∊badoffs}/¨offpairs
  pairs←filter/offpairs

  ⍝ Aux. function: Select the matrix with smallest number of blanks
  MinBlanks←{⍵⊃⍨⊃⍋(+/' '=,)¨⍵}
  ⍝ Aux. function: Given an offset pair, tile the floor using them and
  ⍝                extract the 30x30 region with minimum blanks
  GetResults←{
    somepair←⍵
    ⍝ -30 to 30, inclusive (the values of a and b)
    steps←30-⍳61
    ⍝ All values of av + bw, offset to the minimum coordinates of (0,0)
    alloffs←⊃{,(steps×⊂⍺)∘.+steps×⊂⍵}/somepair
    alloffs-←⌊/alloffs
    ⍝ Initialize a big enough blank grid
    dims←(⍴bool)+⊃⌈/alloffs
    grid←dims⍴''
    ⍝ Fill the grid with the tiles' cells moved accordingly
    filled←((≢alloffs)/⍪' '~⍨,x)@(cbool∘.+alloffs)⊢grid
    ⍝ Extract all 30x30 regions and return the one with minimum blanks
    results←,{⊂⍵}⌺30 30⊢filled
    MinBlanks results
  }
  ⍝ Map the above function over each of the pairs, and extract min blanks
  results←GetResults¨pairs
  MinBlanks results
}