4
$\begingroup$

Let's have two 8x8 grids. By visual inspection we see they are filled with trominoes of three different colors. There are 7 trominoes of each color. On the grids the trominoes are not allowed to touch anywhere side to side with the same color. As you can see the position A4 has two pairs marked with red ink and the position B2 has 8 pairs. Can you rearrange the trominoes on the grids, so that you have one pair on the grid with position A4 empty and 9 pairs on the grid with position B2 empty? A pair is a 2X3 or 3X2 rectangle made with trominoes.

Dec9a Dec9b

Transcription of left-side image (B = blue, R = red, T = teal)

|B |R |R |T |T |B |T |T |
|B |B |R |T |B |B |R |T |
|R |R |B |B |T |R |R |B |
|A4|R |B |R |T |T |B |B |
|B |B |T |R |R |B |R |R |
|B |R |T |T |B |B |T |R |
|T |R |R |B |R |T |T |B |
|T |T |B |B |R |R |B |B |

Transcription of right-side image:

|T |T |R |R |B |B |R |R |
|T |B2|R |T |T |B |T |R |
|B |B |T |B |T |R |T |T |
|B |T |T |B |B |R |R |B |
|T |B |B |R |R |T |B |B |
|T |T |B |R |T |T |R |R |
|R |R |T |B |R |R |B |R |
|R |T |T |B |B |R |B |B |
$\endgroup$
5
  • $\begingroup$ Related. The definition of a "pair" can be found there too (in my comment). $\endgroup$
    – Bubbler
    Dec 10, 2020 at 2:25
  • $\begingroup$ @ Bubbler I already edited the question $\endgroup$ Dec 10, 2020 at 3:57
  • $\begingroup$ Funnily enough, I can do the first one if we allow four colours but not three (not yet at least) which really highlights that the problem goes beyond being just a tiling problem. $\endgroup$
    – hexomino
    Dec 10, 2020 at 18:03
  • $\begingroup$ When you say "Can you rearrange", do you mean the count of each color should remain the same as in the example? $\endgroup$
    – Florian F
    Dec 11, 2020 at 10:39
  • $\begingroup$ @Florian The count of each should remain the same. $\endgroup$ Dec 11, 2020 at 17:56

1 Answer 1

6
$\begingroup$

Answers to parts 1 and 2.

Part 1:

Exactly two essentially different solutions

Part 2:

No solutions for 9. Probably a parity related issue since there are solutions for 8 and 10.

My method. I used my solver with a few new tweaks as follows:

  1. I already had "use a maximum of N no-touch colours" which I set to 3. I also set what I call "non-strict neighbours" to allow the same colours to touch at corners.
  2. This gave about 1.2 million solutions for the first one which I call 'problem A'. So I added some "Max per colour" code and set it for 7 colours. Now we are at around 120k solutions. Some of these are the same layout with a different colouring.
  3. I turned on "similar pattern rejection" which tracks solutions found and rejects any which have the same layout, independent of colouring. Now we are at 11243 tilings found. This means there are on average around 10 ways to colour each tiling. There are other tilings not 3-colourable as well but I already filtered those out.
  4. I added code to count the number of occurrences of a new piece being added sharing exactly N neighbouring cells with a piece already placed. I set N to 3. I believe all 2x3 rectangles formed from a pair have this characteristic, and all non-rectangular placements do not. I also specified a maximum and minimum count for these occurrences. Now I get tiling counts as follows for number of rectangles 0 through 10: 0-0, 1-2, 2-18, 3-36, 4-85, 5-282, 6-1362, 7-1046, 8-895, 9-1683, 10-5834. And if you sum these you get 11243 which is encouraging.

However... When I do the same for 'problem B' the situation is complicated by the fact that the empty square is in a symmetric position, which means I get double the tilings unless I turn on a different sort of symmetry rejection, which is not proven with the new code I added. So I just divide the counts by 2 instead, then I get 0-1.5, 1-2, 2-26, 3-5, 4-54, 5-127, 6-598, 7-126, 8-191, 9-0, 10-3007. Which sums to 4137.5. Solving without regard to rectangles gives 8275/2=4137.5 as well. Alert readers will question the half tiling which is caused by a symmetric tiling with zero rectangles, apparently the only such tiling. The correct counts are 2 tilings with zero rectangles and 4138 total.

Now I turned my solver onto the other posted problem like this which I call "Problem C", although I believe it was posted earlier. The empty square is asymmetrically placed which avoids symmetry rejection issues, and I get counts as follows: 0-2, 1-4, 2-44, 3-10, 4-121, 5-225, 6-1185, 7-252, 8-373, 9-0, 10-5911. Sum is 8127. When I run the solver to find tilings without regard to rectangles, I get 8127 as well.

If there is indeed a 9-rectangle tiling for "Problem B" then I have a bug affecting both ways of counting, which is not that unlikely with the new code I added yesterday.

I fixed the symmetry rejection in the symmetric cases and ran the solver on all possible empty cell positions. Using OP's naming for empty square position I get these counts, all match with the counts from the solver when omitting the 'find a specific number of rectangles' code. When omitting the 3-colouring requirement for case B2 I still get zero 9-rectangle tilings.

Rectangles A4 B2 A2 A1 A3 B3 B4 C3 C4 D4
0 0 2 2 1 0 1 0 0 4 1
1 2 2 4 2 0 0 0 0 0 0
2 18 26 44 26 14 24 22 4 21 16
3 36 5 10 47 46 19 16 21 50 19
4 85 54 121 83 247 65 129 110 266 51
5 282 127 225 411 296 201 219 247 401 249
6 1362 598 1185 1181 1148 532 1146 297 837 504
7 1046 126 252 912 2014 406 551 693 1514 421
8 895 191 373 1375 1631 178 164 2268 1055 495
9 1683 0 0 1249 3498 1370 1264 0 3412 941
10 5834 3007 5911 2936 0 0 3997 0 0 1900
sum 11243 4138 8127 8223 8894 2796 7508 3640 7560 4597
count 11243 4138 8127 8223 8894 2796 7508 3640 7560 4597
$\endgroup$
6
  • $\begingroup$ Good job. Keep trying to find the other. $\endgroup$ Dec 11, 2020 at 18:07
  • $\begingroup$ @Vassilis There is no other. $\endgroup$ Dec 12, 2020 at 1:22
  • $\begingroup$ @ Daniel.The position B2 is not solved.. $\endgroup$ Dec 12, 2020 at 3:28
  • $\begingroup$ @Vassilis There is no solution. With B2 empty, nine pairs is not possible. $\endgroup$ Dec 12, 2020 at 9:29
  • $\begingroup$ The proof that there are no 9-rectangle tilings is surprisingly simple. 1. The piece in the corner next to the empty cell has only one possible position. 2. The rest are in pairs for a 10-rectangle tiling. If you can't move the fixed corner piece, then you can't disrupt any one of the 10 rectangles without disrupting at least two. $\endgroup$ Dec 12, 2020 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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