Sudoku algorithm in C#

问题:

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.

回答1:

Lucky for you I built a sudoku solver myself not too long ago :) The whole thing was about 200 lines of C#, and it would solve the toughest puzzles I could find line in 4 seconds or less.

Performance probably isn't that great due to the use of .Count, but it should work:

!a.Any(i => i != 0 && a.Where(j => j != 0 && i == j).Count >  1)

Also, the j != 0 part isn't really needed, but it should help things run a bit faster.

[edit:] kvb's answer gave me another idea:

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

Filter the 0's before grouping. Though based on how IEnumerable works it may not matter any.

Either way, For best performance replace .Count > 1 in either of those with a new IEnumerable extension method that looks like this:

bool MoreThanOne(this IEnumerable<T> enumerable, Predictate<T> pred)
{
    bool flag = false;
    foreach (T item in enumerable)
    {
       if (pred(item))
       {
          if (flag)
             return true;
          flag = true;
       }
    }
    return false;
}

It probably won't matter too much since arrays are limited to 9 items, but if you call it a lot it might add up.

回答2:

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;
}

回答3:

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

回答4:

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.

回答5:

This is an old question, but I recently was pointed to a 1 line solution using Oracle's custom SQL for doing tree-like structures. I thought it would be nice to convert this into Linq.

You can read more on my blog about how to Solve Sudoku in 1 line of Linq

Here is the code:

public static string SolveStrings(string Board)
{
    string[] leafNodesOfMoves = new string[] { Board };
    while ((leafNodesOfMoves.Length > 0) && (leafNodesOfMoves[0].IndexOf(' ') != -1))
    {
        leafNodesOfMoves = (
            from partialSolution in leafNodesOfMoves
            let index = partialSolution.IndexOf(' ')
            let column = index % 9
            let groupOf3 = index - (index % 27) + column - (index % 3)
            from searchLetter in "123456789"
            let InvalidPositions =
            from spaceToCheck in Enumerable.Range(0, 9)
            let IsInRow = partialSolution[index - column + spaceToCheck] == searchLetter
            let IsInColumn = partialSolution[column + (spaceToCheck * 9)] == searchLetter
            let IsInGroupBoxOf3x3 = partialSolution[groupOf3 + (spaceToCheck % 3) +
                (int)Math.Floor(spaceToCheck / 3f) * 9] == searchLetter
            where IsInRow || IsInColumn || IsInGroupBoxOf3x3
            select spaceToCheck
            where InvalidPositions.Count() == 0
            select partialSolution.Substring(0, index) + searchLetter + partialSolution.Substring(index + 1)
                ).ToArray();
    }
    return (leafNodesOfMoves.Length == 0)
        ? "No solution"
        : leafNodesOfMoves[0];
}

回答6:

How about:

var itIsOk = a.Where(x => x > 0).Distinct().Count() == a.Where(x => x > 0).Count();

Reasoning: First create an enumeration without 0s. Out of the remaining numbers, if its distinct list is the same length as the actual list, then there are no repeats.

or: If the list of unique numbers is smaller than the actual list, then you must have a repeated number.

This is the one-liner version. The a.Where(x=>x>0) list could be factored out.

var nonZeroList = a.Where(x => x > 0).ToList();
var itIsOk = nonZeroList.Distinct().Count() == nonZeroList.Count();

回答7:

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);
}

回答8:

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

回答9:

The following is simple and fast.

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