18
$\begingroup$

This puzzle is part of the Puzzling Stack Exchange Advent Calendar 2023. The accepted answer to this question will be awarded a bounty worth 50 reputation.

< Previous Door Next Door >

Mrs. Claus needs help with a gift for Santa. Every year, Santa complains that his legs get too cold when he flies around on Christmas Eve. This year, Mrs. Claus would like to make him a quilt to keep his legs warm. She wants to incorporate the names of all of his reindeer in the quilt's design using an interesting pattern that connects them all.

The quilt is a rectangle made up of individual square cells. Each of these cells can contain at most one letter. Mrs. Claus came up with a rough draft but the resulting quilt would be too big and add too much weight to the sleigh:

Mrs. Claus's first attempt at a quilt

The quilt above satisfies all of the following properties:

  • Contains all 9 reindeer names connected to each other.
  • Each reindeer name appears either horizontally left-to-right or vertically top-to-bottom.
  • Any two letters that appear in horizontally or vertically adjacent cells belong to a common reindeer name.
  • Two horizontal reindeer names can't overlap and two vertical reindeer names can't overlap.

Can Mrs. Claus do better than the 17-by-10, 170-cell design she found? What's the smallest number of squares she can use to sew her rectangular quilt, given all the constraints above?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do the names have to be fully connected or can you have multiple non-touching crosswords? $\endgroup$
    – hexomino
    Commented Dec 8, 2023 at 13:45
  • $\begingroup$ The names have to be fully connected $\endgroup$
    – Aaron Windsor
    Commented Dec 8, 2023 at 14:17

3 Answers 3

Reset to default
14
+50
$\begingroup$

I've been able to do it in

7x13 = 91 Cells

You have to arrange the reindeers like this

enter image description here

I found it by generating and evaluating all possible arrangements. It feels like a really good solution, but I cant proof if this is optimal, there might be errors in my code.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ I confirmed optimality via integer linear programming. $\endgroup$
    – RobPratt
    Commented Dec 9, 2023 at 1:14
  • $\begingroup$ Great job, @Antikeks! You got it. And it happens to be the unique optimal solution (up to transposition). $\endgroup$
    – Aaron Windsor
    Commented Dec 9, 2023 at 2:04
  • 1
    $\begingroup$ My computer agrees with yours :-) $\endgroup$
    – Florian F
    Commented Dec 9, 2023 at 15:15
10
$\begingroup$

The best I've been able to do has area

$7 \times 14 = 98$ cells

As follows

enter image description here

The idea here

is to try to make one of the dimensions small so expanding in the other direction does not cost too much. Frustratingly it looks like it could be made smaller if we move PRANCER to where VIXEN is and CUPID ending on the D in DASHER but then there is no good spot for VIXEN unless we disconnect it from the rest of the crossword.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ You can make it a 7x13 by moving VIXEN one down and left. So the E in VIXEN aligns with the E in BLITZEN $\endgroup$
    – computer_goblin
    Commented Dec 8, 2023 at 14:46
  • 2
    $\begingroup$ Very nice, @hexomino! But unfortunately, Mrs. Claus can make one even smaller. $\endgroup$
    – Aaron Windsor
    Commented Dec 8, 2023 at 14:48
  • 4
    $\begingroup$ @computer_goblin: that still leaves the "N" from BLITZEN hanging over the right edge, making it a 7x14 grid still $\endgroup$
    – Aaron Windsor
    Commented Dec 8, 2023 at 14:48
9
$\begingroup$

I think I can do

96 cells in a 6x16 grid

because there doesn't appear to be a rule preventing me from doing this:

a grid featuring the monstrous reindeer hydra CUPIDANCERUDOLPH across the center

or at least there wasn't at the time I posted this answer :(

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hah! I did not intend to allow vertical-vertical or horizontal-horizontal overlaps in the name, but this is nice. I would begrudgingly call you the winner if this was the minimum size grid you could create, but fortunately for me there's an even smaller packing of the names that follows my intended rules. I'll clarify the rules to disallow horizontal-horizontal or vertical-vertical overlaps. $\endgroup$
    – Aaron Windsor
    Commented Dec 8, 2023 at 17:55
  • $\begingroup$ yeah it definitely felt like it was against the spirit of the rules but at the same time I thought maybe this is the trick needed to solve the puzzle! back to the drawing board ig $\endgroup$
    – juicifer
    Commented Dec 8, 2023 at 18:07
  • $\begingroup$ Another unwritten rule is that each reindeer must appear only once. $\endgroup$
    – Florian F
    Commented Dec 9, 2023 at 15:20
  • $\begingroup$ I don't think either of these variants would actually help you even if they were allowed. I would be interested in seeing a solution that beats the winning entry that either does overlaps like @jucifer's or repeats reindeer. Doesn't seem like either will make the packing tighter. $\endgroup$
    – Aaron Windsor
    Commented Dec 9, 2023 at 17:33

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