15
$\begingroup$

I tried to find non-trivial solutions on a deficient 8×8 grid covered with trominoes and I regret to say that after extensive efforts I found only two non-trivial solutions:

diagram:two non-trivial solutions

The conditions of covering such a grid with trominoes are the following: In total we have 21 L-shaped trominoes with 3 different colors. There are equal numbers of trominoes of each color. Placing the trominoes on the grid, no 2 trominoes of the same color are allowed to touch each other anywhere, except only once, corner to corner (highlighted by red lines in the diagram).

Solutions from rotations and reflections are trivial. Does anyone know how to obtain more non-trivial solutions? Please include the full 8X8 grid in your answers.

$\endgroup$
  • $\begingroup$ Welcome to Puzzling SE, please take The Tour (you'll also earn a badge). This is a neat puzzle, but however, it may be too open ended for our community. $\endgroup$ – North Apr 11 '18 at 0:00
  • $\begingroup$ This would fit well in a computer science forum. You are looking for a "map" (2-d graph) that is 3 colorable. All maps are 4-colorable, and it is an NP Problem to determine if a map is 3-colorable. You have additional constraints here which may be able to reduce the complexity to a polynomial algorithm to determine if a map is 3-colorable (I'm not convinced it would be). Since we are talking about trominoes I doubt any sort of symmetry analysis would help either. Then there is also the tiling problem that needs to be solved, which is NP in general, but might be simpler for some shapes. $\endgroup$ – wolfram42 Apr 11 '18 at 0:13
  • 3
    $\begingroup$ Though 3-coloring is NP-complete, it's entirely feasible at this scale. Two clarifications, though: first,, may two L's of the same color surround the 'hole' so they contact each other corner-to-corner at two points? Second, aside from rotations/reflections/color swaps, are any other solutions considered 'trivial'? $\endgroup$ – Zomulgustar Apr 11 '18 at 1:33
  • $\begingroup$ @Andy Juell; Meeting corner to corner twice is not acceptable. No other trivial solutions. $\endgroup$ – john Apr 11 '18 at 2:55
  • $\begingroup$ You understand that the empty square can be anywhere on the grid and that this is exactly what I am looking for? From the 8X8 grid I would like to get 64 non-trivial solutions. $\endgroup$ – john Apr 11 '18 at 2:59
3
$\begingroup$

I wrote a program to check every possibility. Lo and behold... those two squares (plus rotations/reflections) that you have removed in your example are the only ones that admit solutions at all! There are 2 solutions to the the first kind of hole, and 6 solutions to the second kind of hole - mostly small adjustments.

enter image description here

I guess I'll just briefly overview my program here. My code can be found here.

More accurately, I used PolySolver to generate all of the possibilities, then wrote a program to go through each of these possibilities, verifying for the conditions. I inquired about how to go about getting a list of solutions in a text format, and as it turns out you can save the list of solutions to a file in a reasonably parsable form. Indeed, line 3, 4, and 105 extract out the list of solutions, line by line. Initially, we have something on the order of 100000 solutions to go through. Clearly too many to do it by hand.
A solution looks like this:

['solution (1 (6,6|2), 2 (5,6|0), 3 (3,6|2), 4 (2,6|0), 5 (0,6|1), 6 (0,5|3), 7 (3,4|1), 8 (1,4|2), 9 (0,3|3), 10 (0,1|1), 11 (0,0|3), 12 (6,4|2), 13 (5,4|0), 14 (6,2|2), 15 (5,2|0), 16 (6,0|2), 17 (5,0|0), 18 (2,0|3), 19 (3,0|1), 20 (3,2|1), 21 (2,2|3))', 'solution (1 (6,6|2), 2 (5,6|0), 3 (3,6|2), 4 (2,6|0), 5 (0,6|1), 6 (0,5|3), 7 (3,4|1), 8 (1,4|2), 9 (0,3|3), 10 (0,1|1), 11 (0,0|3), 12 (6,4|2), 13 (5,4|0), 14 (6,2|2), 15 (5,2|0), 16 (6,0|2), 17 (5,0|0), 18 (2,0|3), 19 (3,0|1), 20 (3,2|2), 21 (2,2|0))']

Next, we transform the solution to a board of trominos, which we can then do stuff with it. I looked at exactly how the trominos mapped to the grid, and thanks to the color gradient, I think I got it pretty reasonably well, maybe modulo switching the axes - enter image description here.
Line 5 defines the list of grid offsets to add to the base coordinates, given each of the 4 orientations. Then function boardgen (lines 6-16) actually places the trominoes, doing some additional hacky string processing to get the values easily. (It would break for, say, two digit numbers. Good thing none of the numbers we care about are two digits long.)
Ok. Now we can check whether our board satisfies the condition. That's the bulk of the program, function verify (lines 18-71). The first check (lines 19-28) is just for performance. I want to ensure that there only exists at most one point where four different trominoes meet. This is a necessary condition because at each of these points, there must exist at least one pair of trominoes that are painted the same color, diagonally touching. This cuts down our searchspace immensely - I estimate that maybe 95-96% of the cases can be swept aside from this condition alone. Still ~5000 cases to go. I wisely decide that hand-coloring things would be more work.
.
Next I proceed to actually begin 3-coloring the pieces. This covers the bulk of the code. First I construct an adjacency matrix of touching trominoes (lines 30-40), and do some other initial setup (lines 41-43). Then I essentially perform a DFS to check every possible coloring, creating a separate function backtracker (lines 73-95). I also keep track of recursion depth for the sole purpose of noting which region I touch first (which I believe is always tromino number 1) and which region I touch second (since I always pick a tromino with the fewest colors available, this always touches tromino number 1). So I force color number 1 to the first tromino, and color number 2 to the second tromino. This cuts down the number of colorings found by a factor of 6, which would have been essentially equivalent colorings anyway. But yeah, mostly standard DFS - take the vertex with the fewest colors available, try all colors, by looking at the adjacency matrix and removing that color from the available set of colors from its neighbors, and so on. I guess about ~500 tilings actually can be 3-colored. I code my DFS so that I collect every possible coloring (divided by 6), so we can do the next checks easier.
.
Now we perform some additional checks. First, checking that a coloring uses 7 of each of the three colors is quite easy to code, and culls the number of tilings significantly. (lines 47-56). And finally, we recheck the bridge condition. I realized that a common failure case was to color in a junction alternating colors, which would result in two such "bridges". (Also, bridges could occur with respect to the empty square as well.) Anyway, a neat trick is to realize that each L tromino naturally gives one diagonal pair of identical colors, as well as each bridge. So we can encode our 1 bridge maximum condition as "<=22 diagonal identical colors", and save having to check whether two diagonally touching squares belong to the same tromino. (lines 57-71) These checks finally narrow down our pool to the 8 displayed above.
.
I then printed out all valid boards, tab-spaced, along with the corresponding colorings, and wrote some spreadsheet formulas/conditional formatting to generate the pictures above. You still have to manually change the filename to switch between files (I made 10 files, one for each position (up to rotation/reflection) of hole in the 8x8 board), but yeah.

$\endgroup$

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.