# 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. Tags

Comments (15)
1. Fabrice's weblog says:

Do you want to see LINQ used for something else than querying a database for customers or for querying

2. Linq in Action News says:

Do you want to see LINQ used for something else than querying a database for customers or for querying

3. Ernst Kuschke says:

Luke Hoban recently blogged about how he used LINQ to solve a physics problem . Could it be that C#,

4. DotNetKicks.com says:

You’ve been kicked (a good thing) – Trackback from DotNetKicks.com

5. Charlie Calvert's Community Blog says:

Recently my time has been taken up with a series of internal issues involving Beta1, C# Samples and various

6. paulsta says:

Will there be a more efficient way of writing

Enumerable.Range(1, 13)

in C# 3.0? A suggestion would be

1..13

7. Sobre C#, LINQ y algo más... says:

Hasta el momento, cada vez que alguien menciona los peligros potenciales que comenzarán a “rondar” al

8. Sobre C#, LINQ y algo más... says:

(This post is a slightly-edited English translation of a previous one in Spanish , with some added comments

9. Anders Norås' Blog says:

Earlier this year the program manager for the C# compiler, Luke Hoban showed how he used LINQ to solve

10. Valium. says:

Valium withdrawal. Canada valium. Vicoden valium. Side effects of valium. Valium.

11. Effexor have any side effects. says:

Effexor alcohol abuse. Effexor xr.

12. Meridia without prescriptions. says:

Meridia sibutramine. Buy meridia online. Meridia overnight. Meridia.

13. BlueCoder says:

Can anyone explain WHY the JOIN make this puzzle’s solution faster in finding? How does JOIN differ than FROM deep down inside?

One book I read said JOIN in ‘keyed’ and FIND is not at in-memory searches. But the book does not explain what it means by ‘keyed’. Does JOIN build an index for the 13 numbers (seems silly)?

LINQ Newbie.

14. Denis says:

<—-Can anyone explain WHY the JOIN make this puzzle’s solution faster in finding? How does JOIN differ than FROM deep down inside?

One book I read said JOIN in ‘keyed’ and FIND is not at in-memory searches. But the book does not explain what it means by ‘keyed’. Does JOIN build an index for the 13 numbers (seems silly)?

LINQ Newbie. —->

It significantly reduces execution of where clause 🙂

15. Joe Albahari says:

BlueCoder: Join loads the inner sequence into something similar to a dictionary (Hashtable) and then able is able to do an efficient lookup for each outer element.

Joe

Skip to main content