LukeH's WebLog

Using LINQ to solve puzzles

A couple months ago, I had a great time participating in Microsoft's PuzzleHunt event along with our team "Cup<T>".  Normally, the puzzles in puzzle hunt are designed to limit the value of writing programs to help solve them.  But this year, I did end up writing some code to help with one of the puzzles - and it happened to be a simple LINQ query that helped.  Since this is an example of using LINQ in a problem domain that's pretty different than the usual querying examples, I thought it might be worth sharing.

The Puzzle

Here's a puzzle similar to the one in the puzzle hunt.  The diagram below is a bunch of weights (A-M) hanging from a system of bars.  Each weight has an integer value between 1 and 13, and the goal is to figure out what each weight must be for the the diagram below to balance correctly as shown: 

                          |
                          |
              +--+--+--+--+--+--+--+
              |                    |
              |                    |
           +--+--+--+--+--+        |
           |     L        M        |
           |                       |
  +--+--+--+--+--+--+     +--+--+--+--+--+
  H              |  I     |  J        K  |
                 |        |              |
        +--+--+--+--+--+  |     +--+--+--+--+--+
        E              F  |     G              |
                          |                    |
              +--+--+--+--+--+  +--+--+--+--+--+--+
              A              B  C                 D

The rules for this kind of puzzle are: (1) The weights on either side of a given pivot point must be equal, when weighted by the distance from the pivot, and (2) a bar hanging beneath another contributes it's total weight as through it were a single weight.  For instance, the bar on the bottom right must have 5*C=D, and the one above it must have 3*G=2*(C+D).

A First Solution

Here's what I tried first.  Note that it's not really much different than a bunch of for loops with an if statement inside:

using System;
using System.Linq;

class WeighsAndMeans
{
  static void Main(string[] args)
  {
    var solveForWeights =
      from a in Enumerable.Range(1, 13)
      from b in Enumerable.Range(1, 13)
      from c in Enumerable.Range(1, 13)
      from d in Enumerable.Range(1, 13)
      from e in Enumerable.Range(1, 13)
      from f in Enumerable.Range(1, 13) 
      from g in Enumerable.Range(1, 13)
      from h in Enumerable.Range(1, 13)
      from i in Enumerable.Range(1, 13) 
      from j in Enumerable.Range(1, 13)
      from k in Enumerable.Range(1, 13) 
      from l in Enumerable.Range(1, 13)
      from m in Enumerable.Range(1, 13) 
      where (4 * a == b)
         && (5 * c == d)
         && (3 * e == 2 * f)
         && (3 * g == 2 * (c + d))
         && (3 * (a + b) + 2 * j == k + 2 * (g + c + d))
         && (3 * h == 2 * (e + f) + 3 * i)
         && ((h + i + e + f) == l + 4 * m)
         && (4 * (l + m + h + i + e + f) == 3 * (j + k + g + a + b + c + d))
      select new { a, b, c, d, e, f, g, h, i, j, k, l, m, 
                   Total = a + b + c + d + e + f + g + h + i + j + k + l + m };

    solveForWeights.ToList().ForEach(result => Console.WriteLine(result));
  }
}

A More Efficient Solution

Part way through writing the code above, I recognized that it wasn't going to be very fast.  It's not too hard to see that it'll execute the body of the where clause 13^13 times.  That's more than 300 trillion times!  Turns out this is exactly what join can help with, and in contrast to the for loop case, it's pretty easy to turn the query above into one which uses joins.  The following code solves the puzzle right away:

using System;
using System.Linq;

class WeighsAndMeans
{
  static void Main(string[] args)
  {
    var solveForWeights =
      from a in Enumerable.Range(1, 13)
      join b in Enumerable.Range(1, 13) on 4 * a equals b
      from c in Enumerable.Range(1, 13)
      join d in Enumerable.Range(1, 13) on 5 * c equals d
      from e in Enumerable.Range(1, 13)
      join f in Enumerable.Range(1, 13) on 3 * e equals 2 * f
      join g in Enumerable.Range(1, 13) on 2 * (c + d) equals 3 * g
      from h in Enumerable.Range(1, 13)
      join i in Enumerable.Range(1, 13) on 3 * h - 2 * (e + f) equals 3 * i
      from j in Enumerable.Range(1, 13)
      join k in Enumerable.Range(1, 13) on 3 * (a + b) + 2 * j - 2 * (g + c + d) equals k
      from l in Enumerable.Range(1, 13)
      join m in Enumerable.Range(1, 13) on (h + i + e + f) - l equals 4 * m
      where (4 * (l + m + h + i + e + f) == 3 * (j + k + g + a + b + c + d))
      select new { a, b, c, d, e, f, g, h, i, j, k, l, m, 
                   Total = a + b + c + d + e + f + g + h + i + j + k + l + m };

    solveForWeights.ToList().ForEach(result => Console.WriteLine(result));
  }
}

Conclusion

It turns out this is an example of using LINQ to solve integer constraints problems.  In the general case, special purpose libraries built to solve these problems are almost certainly more efficient, but the LINQ example using joins is sufficiently quick at least for this case.  More importantly, the LINQ solution is not too hard to arrive at, and doesn't require knowledge of some special purpose Integer Programming framework.  I see this as an example of one of the great benefits of LINQ - that I can do all sorts of query and transformation in C# without resorting to special purpose frameworks for each different domain I need to work with.