Solving Combinatory Problems with LINQ

Originally published by MSDN in 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.

using System;
using System.Linq;
 
namespace Geeks
{
  // 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/
  class MainClass
  {
    static void Main()
    {
      int[] oneToNine = new int[] { 123456789 };

      // 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.

Octavio Hernandez

Desarrollador y consultor en tecnologías .NET. Microsoft C# MVP entre 2004 y 2010.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *