# Solving Combinatory Problems with LINQ

By Octavio Hernandez

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:

1. The number should be divisible by 9.
2. If the rightmost digit is removed, the remaining number should be divisible by 8.
3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
4. And so on, until there's only one digit (which will necessarily be divisible by 1).

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/en-us/blogs/2009/12/07/intel-parallel-studio-great-for-serial-code-too-episode-1/

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.