6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ For comparison: If we look for sets of two pieces that can cover 15 of the squares on a 4x4 chessboard, there are exactly 2 solutions if we require contiguity, and 3 more solutions if we permit discontiguity. ...Oho, this is a big hint as to some possible solutions to the 8x8 problem! :) However, I still haven't found any contiguous solutions which aren't just a nested series of (similar or dissimilar) ell-shaped pieces. $\endgroup$ – Quuxplusone Jan 29 at 2:52
8
$\begingroup$

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:

enter image description here



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

$6$ sets.

Visually, here are the sets:

enter image description here

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$:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Nice diagrams! Could you add diagrams of a couple of the "asymmetric" cases? I understand your notation, but it would still be nice to see one or two drawn out visually. (And I'm still left wondering if ells of varying thicknesses is all there is.) $\endgroup$ – Quuxplusone Jan 29 at 14:21
  • 1
    $\begingroup$ @Quuxplusone added! :D When I was trying to put them, I got a feeling that I might be wrong but it turns out alright! $\endgroup$ – athin Jan 29 at 15:07
4
$\begingroup$

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]$.

$\endgroup$
  • $\begingroup$ To be clear, that's a solution to the "discontiguous" version of the problem, right? $\endgroup$ – Quuxplusone Jan 29 at 1:52
  • $\begingroup$ Yes. The minuses are the transparent bits. $\endgroup$ – JMP Jan 29 at 2:05
3
$\begingroup$

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)
 

$\endgroup$
  • $\begingroup$ Ah, I just realized it can be flipped! Nice! $\endgroup$ – athin Jan 29 at 6:55
  • $\begingroup$ Solutions 1 and 3 are covered by the @athin solution, but number 2 is interesting in that it can be combined with a 4-length L shape to cover the rest of the board, thus providing another full solution, and suggesting there may be some other asymmetrical ones. (Ignoring the non-contiguous ones for now...) $\endgroup$ – Darrel Hoffman Jan 29 at 14:57
  • $\begingroup$ @DarrelHoffman It's already covered in updated version :) $\endgroup$ – athin Jan 29 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.