Create a LINQ Killer Sudoku Cage Solver

Question

When playing Killer Sudoku I find myself repeatedly writing stuff like this:

12/3
921
831
741
732
651
642
543

and then crossing out the combinations that include say 9, 7, and 6

IE I need a list of any 3 digits between 1 and 9 that add up to 12, excluding 9, 7, and 6 because they are already in the house.

So I wrote a Linq query to run in LinqPad that does this. However its pretty specific. Here is the implementation for 3 numbers:

var num=3;
var target=12;
var exceptions=new List<int>{9,7,6};

var List1 = new List<int>{1,2,3,4,5,6,7,8,9};
var List2 = new List<int>{1,2,3,4,5,6,7,8,9};
var List3 = new List<int>{1,2,3,4,5,6,7,8,9};

// Make a Cartesian join of the three lists
// Filter out the stuff that we want
// Sort the result from highest to lowest
var combo = (from l1 in List1
        from l2 in List2
        from l3 in List3        // Cartesian product    
        where l1 > l2 && l2 > l3    // exclude duplicates
        && l1 + l2 + l3 == target   // add up to the target 
        && !exceptions.Contains(l1) // exclude exceptions
        && !exceptions.Contains(l2)
        && !exceptions.Contains(l3)
        select new List<int>{l1, l2, l3})                       
        .OrderByDescending (c =>c[0] ) 
        .ThenByDescending (d => d[1])
        .ThenByDescending (e => e[2]);

Console.WriteLine(string.Format("{0}/{1}", target, num));
foreach(var item in combo){ 
for (var i=0; i< num;i++){
    Console.Write(item[i]);
}       
Console.WriteLine();
}
Console.Write("excluding");
foreach(var i in exceptions){
    Console.Write(string.Format(" {0} ",i));
}

I have found it pretty useful but is there a better and more general way of implementing this?

Answer 1

Naming

Use camelCase for local variable names. And, use a meaningful name if possible.

//var List1 = new List<int>{1,2,3,4,5,6,7,8,9};
var validNumbers = new List<int>{1,2,3,4,5,6,7,8,9};

Use pluralized noun for variable of collection type.

//var combo = ... /*combo contains all possible combinations, not just one*/
var combos

Code

• You don't need to enumerate the numbers 1 to 9. A Enumerable.Range will do the job.
• The chain of !exceptions.Contains(x) is rather inefficient and redundant. You can avoid them by removing the exceptions from the start with IEnumerable.Except.
• You can reuse the same list in your LINQ.
• You can reuse the same name for your lambdas given they are not within the same parentheses. (Not really a big problem)

Result :

var validNumbers = Enumerable.Range(1, 9).Except(exceptions);
var combos = (from a in validNumbers
              from b in validNumbers
              from b in validNumbers       // Cartesian product    
              where a > b && b > c &&      // exclude duplicates
                    a + b + c == target    // add up to the target 
              select new List<int>{ a, b , c})
             .OrderByDescending(x => x[0]) 
             .ThenByDescending(x => x[1])
             .ThenByDescending(x => x[2]);

---

In the last 2 blocks of the code, Console.Write was repeatedly called within the for loop. You can join them together with String.Join before printing it to the console.

Results :

foreach(var item in combos)
    Console.WriteLine(string.Join("", item));

Console.Write("excluding " + string.Join(" ", exceptions));

---

Final Code

This can be directly copied to LinqPad and ran.

void Main()
{
    string buffer;
    int target, elementCount;

    //get target
    Console.WriteLine(">> Target is ..?");

    while(!int.TryParse(buffer = Console.ReadLine(), out target))
        Console.WriteLine("\tInvalid input : {0}", buffer);
    Console.WriteLine(target);

    //get elementCount
    Console.WriteLine(">> Number of elements is ..?");

    while(!int.TryParse(buffer = Console.ReadLine(), out elementCount) ||
          1 > elementCount || elementCount > 6)
        Console.WriteLine("\tInvalid input : {0}", buffer);
    Console.WriteLine(elementCount);
    Console.WriteLine(/*Empty Line*/);

    //get exceptions
    var validNumbers = Enumerable.Range(1, 9);
    IEnumerable<int?> exceptions;
    Console.WriteLine(">> Exceptions are ..? (separated with comma like : 1,2,3)");

    while(!TryParseExceptions(buffer = Console.ReadLine(), out exceptions))
        Console.WriteLine("\tInvalid input : {0}", buffer);
    Console.WriteLine(string.Join(" ", exceptions.OrderBy(x => x)));

    Console.WriteLine(/*Empty Line*/);
    CalculateCombinations(target, elementCount, exceptions.Select(e => e.Value).Distinct());
}

int? ToNullableInt(string value)
{
    int number;
    return int.TryParse(value.Trim(), out number) ? (int?)number : null;
}
bool TryParseExceptions(string value, out IEnumerable<int?> exceptions)
{
    //const int MinValue = 1, MaxValue = 9;
    exceptions = value == ""
        ? Enumerable.Empty<int?>()
        : value.Split(',').Select(ToNullableInt);

    return exceptions.All(e => e.HasValue && (1 <= e.Value && e.Value <= 9)); //less verbose but magical...
    //return exceptions.All(e => e.HasValue && (MinValue <= e.Value && e.Value <= MaxValue));
}

// Define other methods and classes here
void CalculateCombinations(int target, int elementCount, IEnumerable<int> exceptions)
{
    var validNumbers = Enumerable.Range(1, 9).Except(exceptions);

    // Make a Cartesian join of the three lists
    // Filter out the stuff that we want
    // Sort the result from highest to lowest
    var combos = validNumbers.CartesianProduct(elementCount)     // Cartesian product 
                            .Where(x => x.GreaterThanNext() &&   // exclude duplicates
                                        x.Sum(y => y) == target) // add up to the target 
                            .OrderByDescending(x => x.First());  // sort from the 1st number to...

    for(int i = 1; i < elementCount; i++)
    {
                    ///i would be incremented when the ienumerable unfolds
        var index = i;
        combos = combos.ThenByDescending(x => x.ElementAt(index));   // ... the [n]th
    }

    Console.WriteLine(string.Format("{0}/{1}", target, elementCount));

    foreach(var item in combos)
        Console.WriteLine(string.Join("", item));

    Console.Write("excluding : " + string.Join(" ", exceptions.OrderBy(x => x)));
}

//credit : http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/
//slightly altered to reuse the same sequence

public static class Extensions
{
    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<T> sequence, int repeat) 
    {
        IEnumerable<IEnumerable<T>> result =  new[] { Enumerable.Empty<T>() };

        for(int i = 0; i < repeat; i++)
        { 
            // don't close over the loop variable (fixed in C# 5 BTW)
            var s = sequence; 
            // recursive case: use SelectMany to build 
            // the new product out of the old one 
            result = from seq in result 
                    from item in s 
                    select seq.Concat(new[] {item}); 
        }

        return result; 
    }

    public static bool GreaterThanNext(this IEnumerable<int> sequence)
    {
        if (sequence.Count() < 2) return true;

        var previous = int.MaxValue;
        foreach(var item in sequence)
            if(previous <= item)
                return false;
            else previous = item;

        return true;
    }
}

Example of result :

>> Target is ..?
25
>> Number of elements is ..?
4

>> Exceptions are ..? (separated with comma like : 1,2,3)
1

25/4
9862
9853
9763
9754
8764
excluding : 1

Answer 2

In order to make the number of elements variable, you're probably going to have to go beyond a single Linq expression. This is basically an adaptation of the standard problem of finding partitions of an integer, but you have addition constraints: no repetition, no use of the excluded values, and no exceeding 9.

IEnumerable<IEnumerable<int>> GenerateCage(int num, int target, params int[] excluded)
{
    return GenerateCageInner(num, target, 1, 9, new HashSet<int>(excluded));
}

private IEnumerable<IEnumerable<int>> GenerateCageInner(int num, int target, int min, int max, HashSet<int> excluded)
{
    // Base case
    if (num == 0)
    {
        if (target == 0) yield return new int[0];
        yield break;
    }

    // Recursive case
    for (int i = min; i <= max && i <= target; i++)
    {
         if (excluded.Contains(i)) continue;

         foreach (var subsoln in GenerateCageInner(num - 1, target - 1, min + 1, max, excluded))
         {
             var soln = new List<int>();
             soln.Add(i);
             soln.AddRange(subsoln);
             yield return soln;
         }
    }
}

This code aims to be simple over being efficient, although there are some efficiency considerations. It uses a HashSet for testing membership of the excluded set rather than iterating through it, and it uses min to avoid duplicates. The next efficiency complication to add would be using num and min to quick-reject cases where we will certainly exceed target.