Linq puzzle solver

Question

I was bored and decided to try my hand at using Linq to solve a logic puzzle. I found a puzzle here.

The linq I created is as follows:

  IEnumerable<int> values = Enumerable.Range(1, 9);

  var result = from A in values
               from B in values
               from C in values
               from D in values
               from E in values
               from F in values
               from G in values
               from H in values
               from I in values
               where A != B && A != C && A != D && A != E && A != F && A != G && A != H && A != I
               where B != C && B != D && B != E && B != F && B != G && B != H && B != I
               where C != D && C != E && C != F && C != G && C != H && C != I
               where D != E && D != F && D != G && D != H && D != I
               where E != F && E != G && E != H && E != I
               where F != G && F != H && F != I
               where G != H && G != I
               where H != I
               where A + B == 11
               where B + C + D == 11
               where D + E + F == 11
               where F + G + H == 11
               where H + I == 11
               select new { A, B, C, D, E, F, G, H, I };

  result.ToList().ForEach(x => Console.WriteLine("A: {0}, B: {1}, C: {2}, D: {3}, E: {4}, F: {5}, G: {6}, H: {7}, I: {8}", x.A, x.B, x.C, x.D, x.E, x.F, x.G, x.H, x.I));

I expected this to print all the answers fairly easily, but it just seems to calculate forever. If I was to write this the standard way then it would take microseconds to calculate the answer. Why is it so slow in linq?

Answer 1

Well for one thing, you're only filtering after you've generated the whole set of 9 values. You can make it more efficient like this:

from A in values
from B in values
where B != A
where A + B == 11
from C in values
where C != A && C != B
from D in values
where D != A && D != B && D != C
where B + C + D == 11
from E in values
where E != A && E != B && E != C && E != D
from F in values
where F != A && F != B && F != C && F != D && F != E
where D + E + F == 11
from G in values
where G != A && G != B && G != C && G != D && G != E && G != F
from H in values
where H != A && H != B && H != C && H != D && H != E && H != F && H != G
where F + G + H == 11
from I in values
where I != A && I != B && I != C && I != D && I != E && I != F && I != G && H != I
where H + I == 11
select new { A, B, C, D, E, F, G, H, I };

Answer 2

You are computing the cartesian product over 9 value sequences so you have 9⁹ = 387420489 input elements. That would be very slow. Instead you should do the pruning earlier, so you don't have to compute unnecessary input values in the first place.