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