Ed Pegg Jr wrote on 8/31/2010:
Put numbers 1-9 in a 4x7 grid so that all combinations appear as a domino [doubles included] somewhere in the grid.
c corner e edge i interior
1 ccee, 6 eei, 2 iic -- this is a possible distribution solving the 4x7. A careful search proves there are no solutions.
I think that 1 ccci, 7 eei, 1 iic is the only other possible distribution. My program agrees, no solutions with either one.
I've found 387 solutions, so far, for the 5x6 grid with holes (0). Here are some of them. [...]
For the four distinct locations A..D of a single hole, x x x x x x A B x x x C D x x x x x x x x x x x x x x x x x my program finds 108, 50, 81 and 206 solutions respectively. I think the solutions in each class are distinct; if so, that's a grand total of 445 distinct solutions.
For the 0-9 case without doubles, there is a simpler non-existence proof for the 4x7. An interior square can be surrounded by 4 other numbers. 4+4=8. Each number has to touch 9 other numbers. Each number must therefore be in at least 3 positions of the grid. 30 positions cannot be fit into 28 places.
Nice!
I wouldn't be surprised if I (that is, my computer) was the first to solve the tightly packed domino problem. [...]
So maybe these are new results? Great! "Tightly packed" suggests calling these "domino clusters". With caramel and a chocolate covering -- delicious. :-) If we allow holes, I like the 5x6 with two holes. There's only one distinct such pattern, and (my program says) there is a unique (under rotation and label permutation) solution! Allowing holes opens up a huge space of possible patterns. I like to focus on elementary, un-holey shapes. An alternative is Allan Wechsler's generalization to just planarity. Allan says,
(As a map coloring problem, this asks for the smallest number of countries in an n-color map so that every color pair occurs on some boundary.)
Do we also need to specify whether each color occurs paired with itself, like we specify whether domino doubles are included or excluded? SPOILER ALERT: solution to 5x6 with 2 holes 0 1 2 2 3 4 1 5 4 3 6 7 7 4 8 6 8 2 9 8 3 1 6 5 5 7 9 9 3 0 -- Mike