Cover 63 squares of a chess board, differently

Question

In this other puzzle, ThomasL asks for three similar pieces which can be arranged to exactly cover all of an 8x8 chessboard, except for a single square — for any of the 64 possible single squares.

I follow this up by asking: Suppose we don't require the pieces to be similar in shape. Can you find another set of three pieces that can be rearranged, rotated, and flipped to exactly cover any 63 of the squares on an 8x8 chessboard?

How many such sets are there? Prove it.

Does the answer change if we permit the pieces to be discontinuous? (That is, if you're allowed to draw the shapes on transparencies and overlay them, does the problem admit more solutions?)

EDIT: I've just found Universal dissection which seems to be this same problem with a very slightly different question as the puzzle.

Answer 1

Update: Please read below (under the double underlines) explanation first before coming back here.

I just realized from user65284's answer that we can flip the pieces. Thus, the lowerbound can be increased to:

$21$ sets, named all configuration thickness of each pieces:

- (Red $4,4$) (Yellow $2,2$) (Green $1,1$)
- (Red $4,4$) (Yellow $2,1$) (Green $2,1$)
- (Red $4,4$) (Yellow $1,1$) (Green $2,2$)

- (Red $4,2$) (Yellow $4,2$) (Green $1,1$)
- (Red $4,2$) (Yellow $4,1$) (Green $2,1$)
- (Red $4,2$) (Yellow $2,1$) (Green $4,1$)
- (Red $4,2$) (Yellow $1,1$) (Green $4,2$)

- (Red $4,1$) (Yellow $4,2$) (Green $2,1$)
- (Red $4,1$) (Yellow $4,1$) (Green $2,2$)
- (Red $4,1$) (Yellow $2,2$) (Green $4,1$)
- (Red $4,1$) (Yellow $2,1$) (Green $4,2$)

- (Red $2,2$) (Yellow $4,4$) (Green $1,1$)
- (Red $2,2$) (Yellow $4,1$) (Green $4,1$)
- (Red $2,2$) (Yellow $1,1$) (Green $4,4$)

- (Red $2,1$) (Yellow $4,4$) (Green $2,1$)
- (Red $2,1$) (Yellow $4,2$) (Green $4,1$)
- (Red $2,1$) (Yellow $4,1$) (Green $4,2$)
- (Red $2,1$) (Yellow $2,1$) (Green $4,4$)

- (Red $1,1$) (Yellow $4,4$) (Green $2,2$)
- (Red $1,1$) (Yellow $4,2$) (Green $4,2$)
- (Red $1,1$) (Yellow $2,2$) (Green $4,4$)

And here are some illustrations in action:

---

---

Here I will give a lowerbound for (original) contiguous case, which is there are at least:

$6$ sets.

Visually, here are the sets:

The three pieces are colored red, yellow, and green; and:

The red one must be the outermost part (having a length of $8$), yellow must be in the middle (with the same implication), and the green must be in the innermost. They are all having a thickness of $1$, $2$, and $4$; thus leading there are $3! = 6$ sets.

To show that they are valid sets:

We can do binary! And we can solve independently between the row and column!

Practically speaking:

W.L.O.G. we solve the row first. Let's say that we will not cover the hole in $x$-th row. That means we want to cover $x-1$ cells above it. This $x-1$ ranges from $0$ to $7$ which can be written as a subset sum of $\{1,2,4\}$ (a.k.a. binary). We can then rotate each pieces such that if its thickness is required then one of its side must be put above the hole. We can solve the column with the same technique. As an example, putting the piece in "L" shape will cover the left side of the hole but not above it.

Just to illustrate, here are some examples to not cover cell at row $4$ column $2$:

Answer 2

On 4x4 chessboard with two pieces, I found

3 contiguous solutions and 6 discontiguous solutions

by exhaustive search.

 .BAA  B.AA  BBAA
 BBAA  BBAA  B.AA
 AAAA  AAAA  AAAA
 AAAA  AAAA  AAAA  (A : 12, B : 3, contiguous)
 
 .BBA  A.BB  AAAA
 BBBA  ABBB  B.AA
 AAAA  AAAA  BBAA
 AAAA  AAAA  BBAA  (A : 10, B : 5, contiguous)
 
 .AAB  B.AA  BBBB
 AAAB  BAAA  B.AA
 AAAB  BAAA  BAAA
 BBBB  BBBB  BAAA  (A : 8, B : 7, contiguous)
 
 .ABA  A.AB  AAAA
 AAAA  AAAA  A.AB
 BABA  ABAB  AAAA
 AAAA  AAAA  ABAB  (A : 12, B : 3)
 
 .ABA  A.AB  ABAB
 BABA  ABAB  A.AB
 AAAA  AAAA  AAAA
 AAAA  AAAA  AAAA  (A : 12, B : 3)
 
 .ABA  A.AB  AAAA
 ABAA  AABA  A.AB
 BABA  ABAB  AABA
 AAAA  AAAA  ABAB  (A : 11, B : 4)
 
 .BBA  A.BB  AAAA
 AAAA  AAAA  A.BB
 BBBA  ABBB  AAAA
 AAAA  AAAA  ABBB  (A : 10, B : 5)
 
 .BBA  A.BB  AAAA
 ABAA  AABA  A.AB
 BBBA  ABBB  ABBB
 AAAA  AAAA  ABAB  (A : 9, B : 6)
 
 .BBA  A.BB  AAAA
 BABA  ABAB  A.BB
 BBBA  ABBB  ABAB
 AAAA  AAAA  ABBB  (A : 8, B : 7)
 

Answer 3

These three discontinuous tiles remove $48$ then $12$ then $3$ squares. The first layer pattern leaves a $4\times4$ replica of the original board, the second layer leaves a $2\times2$.

 XXXXXXXX    --------    --------
 XOXOXOXO    -X-X-X-X    --------
 XXXXXXXX    --------    --------
 XOXOXOXO    -X-O-X-O    ---X---X
 XXXXXXXX    --------    --------
 XOXOXOXO    -X-X-X-X    --------
 XXXXXXXX    --------    --------
 XOXOXOXO    -X-O-X-O    ---X---O

 XXXXXXXX    --------    --------
 XXXXXXXX    --------    --------
 XXOOXXOO    --XX--XX    --------
 XXOOXXOO    --XO--XO    ---X---X
 XXXXXXXX    --------    --------
 XXXXXXXX    --------    --------
 XXOOXXOO    --XX--XX    --------
 XXOOXXOO    --XO--XO    ---X---O
 

These two come from making a block from coordinates $(1,1),(1,2),(2,1),(5,5)$ and $(1,1),(1,3),(3,1),(5,5)$ (from the L-solution) respectively, and using this mapping as a tiling. The second one uses a neat rotation trick with the second layer.

Also,

 XXXXXXXX    --------    --------
 XXXXXXXX    --------    --------
 XXOOXXOO    --XX--XX    --------
 XXOOXXOO    --XX--XX    --------
 XXXXXXXX    --------    --------
 XXXXXXXX    --------    --------
 XXOOXXOO    --XX--OO    ------XX
 XXOOXXOO    --XX--OO    ------XO 

If we label the two mappings given as $[2,2]$ and $[3,3]$, the remaining mappings are $[2,3], [2,5]$ and $[3,5]$.