Solving Combinatory Problems with LINQBy April 2010 The other day I ran into a very interesting blog post by Intel engineer James Cownie, Intel Parallel Studio: Great for Serial Code Too (Episode 1). The article uses as an example an application that solves the following problem (I quote): Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

While the C++ solution proposed by the author in that article runs along more “conventional” lines, I (having the enormous luck of being a C# developer) was immediately drawn to applying LINQ to tackle this problem. I find LINQ an ideal tool for solving this type of exploratory problem, where one needs to traverse a full tree of possible combinations, backtracking from unsuccessful branches as soon as they are encountered.
With LINQ queries, cascaded from clauses serve as the generators of combinations, while where clauses determine the failure points that trigger backtracking. The first time I saw this technique used was in the blog post Using LINQ to solve puzzles, by Luke Hoban, a member of the Microsoft Languages Team. I was inspired to write about the approach in my book C# 3.0 and LINQ (C# 3.0 y LINQ, Krasis Press, 2007 (in Spanish)), and then occasionally in my blog, the last time to solve a puzzle involving the generation of a magic square similar to the Dührer square mentioned in the latest Dan Brown bestseller, The Lost Symbol. The post, Buscando el símbolo perdido con LINQ, is in Spanish.
The code that follows shows my implementation of the solution to the problem, which I find a good example of the enormous expressive power of LINQ.
// C# and LINQ solution to the numeric problem presented in:
// http://software.intel.com/enus/blogs/2009/12/07/intelparallelstudiogreatforserialcodetooepisode1/
int[] oneToNine = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// the query
var query =
from i1 in oneToNine
from i2 in oneToNine
where i2 != i1
&& (i1 * 10 + i2) % 2 == 0
from i3 in oneToNine
where i3 != i2 && i3 != i1
&& (i1 * 100 + i2 * 10 + i3) % 3 == 0
from i4 in oneToNine
where i4 != i3 && i4 != i2 && i4 != i1
&& (i1 * 1000 + i2 * 100 + i3 * 10 + i4) % 4 == 0
from i5 in oneToNine
where i5 != i4 && i5 != i3 && i5 != i2 && i5 != i1
&& (i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5) % 5 == 0
from i6 in oneToNine
where i6 != i5 && i6 != i4 && i6 != i3 && i6 != i2 && i6 != i1
&& (i1 * 100000 + i2 * 10000 + i3 * 1000 + i4 * 100 + i5 * 10 + i6) % 6 == 0
from i7 in oneToNine
where i7 != i6 && i7 != i5 && i7 != i4 && i7 != i3 && i7 != i2 && i7 != i1
&& (i1 * 1000000 + i2 * 100000 + i3 * 10000 + i4 * 1000 + i5 * 100 + i6 * 10 + i7) % 7 == 0
from i8 in oneToNine
where i8 != i7 && i8 != i6 && i8 != i5 && i8 != i4 && i8 != i3 && i8 != i2 && i8 != i1
&& (i1 * 10000000 + i2 * 1000000 + i3 * 100000 + i4 * 10000 +
i5 * 1000 + i6 * 100 + i7 * 10 + i8) % 8 == 0
from i9 in oneToNine
where i9 != i8 && i9 != i7 && i9 != i6 && i9 != i5 && i9 != i4 && i9 != i3 && i9 != i2 && i9 != i1
let number = i1 * 100000000 +
i2 * 10000000 +
i3 * 1000000 +
i4 * 100000 +
i5 * 10000 +
i6 * 1000 +
i7 * 100 +
i8 * 10 +
i9 * 1
where number % 9 == 0
select number;
// run it!
foreach (int n in query)
Console.WriteLine(n);
Note that no attempt at all has been made to optimize the code (for instance, applying individual divisibility criteria for the different positions). I firmly believe in Don Knuth's statement that “premature optimization is the root of all evil,” and the program as it stands perfectly satisfied my expectations. On my laptop, it finds the only solution to the problem (the number 381654729) in much less than a second.
About the author: