Sudoku algorithm in C#

Question

I need one liner (or close to it) that verifies that given array of 9 elements doesn't contain repeating numbers 1,2,3,...,9. Repeating zeroes do not count (they represent empty cells).

The best I have came out so far is:

var a = new int[9] {1,2,3,4,5,6,7,8,9};
var itIsOk = a.Join(a, i => i, j => j, (x, y) => x)
    .GroupBy(y => y).Where(g => g.Key > 0 && g.Count() > 1).Count() == 0;

If you don't want to solve my problems :), could you at least tell if the above algorithm works correctly?

And, yes, a have read this one.

Answer 1

For brevity if not performance, how about var itIsOk = a.Sum() == a.Distinct().Sum();

Answer 2

!a.GroupBy(i => i).Any(gp => gp.Key != 0 && gp.Count() > 1)

Answer 3

Why do you want a convoluted line of Linq code, rather than wrapping up an efficient implementation of the test in an extension method and calling that?

var a = new int[9] {1,2,3,4,5,6,7,8,9};
var itIsOk = a.HasNoNonZeroRepeats();

One implementation of NoNonZeroRepeats could be to use the 9 lowest bits of a short to indicate presence of a value in the array, giving an O(length(a)) test with no dynamic memory use. Linq is cute, but unless you're only using it for aesthetic reasons (you don't specifically say that you're writing a sudoku solver using only Linq as an exercise) it seems to be just adding complexity here.

Answer 4

I usually frown on solutions that involve captured variables, but I had an urge to write this:

bool hasRepeating = false;
int previous = 0;

int firstDuplicateValue = a
  .Where(i => i != 0)
  .OrderBy(i => i)
  .FirstOrDefault(i => 
  {
    hasRepeating = (i == previous);
    previous = i;
    return hasRepeating;
  });

if (hasRepeating)
{
  Console.WriteLine(firstDuplicateValue);
}

Answer 5

The following is simple and fast.

if a.Select(i => Math.Pow(2, i - 1)).ToArray().Sum()==511 ...

Answer 6

This is about 50-250 times faster than a LINQ solution (depending on how early the duplicate is found):

public static bool IsValid(int[] values) {
    int flag = 0;
    foreach (int value in values) {
        if (value != 0) {
            int bit = 1 << value;
            if ((flag & bit) != 0) return false;
            flag |= bit;
        }
    }
    return true;
}