Constraint Programming Part IV - LINQ

LINQ is a set of operators to query enumerable data. To query even numbers from set of 1 to 10, you may write:

var even = from x in 1.To(10)
           where x % 2 == 0
           select x;
//even = {2, 4, 6, 8, 10}

With using of LINQ, you can also do constraint programming. You can use "from" operator to join next member. You can append constraint by using "where" operator. And you can declare new variables by using "let" operator.

As an example, if you want to solve SEND + MORE = MONEY. Each letter represents a digit and there is no duplicated number among the letters. To solve this question, you may write:

var solutions = from d in 0.To(9)
                from e in 0.To(9).Except(new[] { d })
                from y in 0.To(9).Except(new[] { d, e })
                where (d + e) % 10 == y

                from n in 0.To(9).Except(new[] { d, e, y })
                from r in 0.To(9).Except(new[] { d, e, y, n })
                let nd = n * 10 + d
                let re = r * 10 + e
                let ey = e * 10 + y
                where (nd + re) % 100 == ey

                from o in 0.To(9).Except(new[] { d, e, y, n, r })
                let end = e * 100 + nd
                let ore = o * 100 + re
                let ney = n * 100 + ey
                where (end + ore) % 1000 == ney

                from s in 1.To(9).Except(new[] { d, e, y, n, r, o })
                from m in 1.To(9).Except(new[] { d, e, y, n, r, o, s })
                where s * 1000 + end + m * 1000 + ore == m * 10000 + o * 1000 + ney
                select new { s, e, n, d, m, o, r, y };
solutions.ForEach(Console.WriteLine);
//{ s = 9, e = 5, n = 6, d = 7, m = 1, o = 0, r = 8, y = 2 }

The code above solves from last digit to the first digit. To translate the code, first block is to process last digit. D, E, and Y is a number in 0 to 9. Except method makes all letters are not duplicated. And there is a contraint that, D + E last digit must be Y. Upto this point, all solutions that D + E, last digit is not Y, will be filtered out.

Second block is to process last 2 digits, N and R is a number in 0 to 9 with no duplication. And now 3 variables are declared ND, RE, and EY. ND represents 2 digit number N and D, and the same for RE and EY. And there is a constraint ND + RE, last 2 digits must be EY.

Third block, is the same as second block, but is to precess last 3 digit. O is a number in 0 to 9 with no duplication. END + ORE, last 3 digits must be NEY.

Fourth block is to find the solution. S and M is a number in 1 to 9, first digit cannot be 0. And SEND + MORE must be equal to MONEY. Then select the result.

Now compare LINQ code with using arranger class.

Func<int, int, int, int, int> mix = (a, b, c, d) => a * 1000 + b * 100 + c * 10 + d;
int D = 0, E = 1, Y = 2, N = 3, R = 4, O = 5, S = 6, M = 7;
var sol = 0.To(9).Arrange(8);
sol.ArrangementModel = ArrangementModel.Permutation;
sol.AppendConstraint(set => set.Length == Y, set => y => (set[D] + set[E]) % 10 == y);

sol.AppendConstraint(set => set.Length == R, set => r => (mix(0, 0, set[N], set[D]) + mix(0, 0, r, set[E])) % 100 == mix(0, 0, set[E], set[Y]));
sol.AppendConstraint(set => set.Length == O, set => o => (mix(0, set[E], set[N], set[D]) + mix(0, o, set[R], set[E])) % 1000 == mix(0, set[N], set[E], set[Y]));

sol.AppendConstraint(set => set.Length == S, set => s => s != 0);
sol.AppendConstraint(set => set.Length == M, set => m => m != 0);
sol.AppendConstraint(set => set.Length == M, set => m => mix(set[S], set[E], set[N], set[D]) + mix(m, set[O], set[R], set[E]) == m * 10000 + mix(set[O], set[N], set[E], set[Y]));

sol.SelectResults(set => new { s = set[S], e = set[E], n = set[N], d = set[D], m = set[M], o = set[O], r = set[R], y = set[Y] })
    .ForEach(Console.WriteLine);
//{ s = 9, e = 5, n = 6, d = 7, m = 1, o = 0, r = 8, y = 2 }

The code is much more confusing. To translate code above, mix function is function to join digits together. Arragement model is permutation, because each letter cannot be duplicated. First constraint, processed when get Y, D + E, last digit is Y.

Second constraint, processed when get R, ND + RE, last 2 digits must be EY. Third constraint, processed when get O, END + ORE, last 3 digits must be NEY.

Fouth and fifth constraint, processed when get S and M, S and M must not equal to 0. Last constraint, processed when get the last member M. SEND + MORE must be equal to MONEY.

To solve a constraint satisfaction problem, sometimes, when each constraint is applied to only one member, solving the problem using LINQ is better. But if constraints are applied to all members like 8 queens or sudoku, using Arranger class is better.

Next, we will solve problem with using LINQ and arranger in combination. The problem is Einstein's puzzle.