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.

Renewal

Meaning that you don't want to help me :) – Renewal

The community helps those who help themselves – Neckwear

"Run the code and find out" is not an acceptable methodology for verifying correctness. – Benford

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

Silicosis

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

Shing

+1 By far the best answer. Concise, fast, readable, reusable, testable. – Samite

Since there wasn't a lot of explanation with this solution, here's what's going on for those who aren't sure: #5111934 – Neel

Answer 3

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

Googolplex

Answer 4

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

Diphtheria

Answer 5

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.

Wendell

I don't think that solutions proposed by Joel Coehoorn are convoluted. (I cannot say the same about mine :). – Renewal

They are significantly more complicated than a single method call, both in terms of what is written and what is executed, and require to be cut and paste wherever you need to perform the test, which is very poor software engineering. – Wendell

It doesn't mean that you cannot wrap this one-liner into a function with a descriptive name. – Renewal

At which point it becomes irrelevant whether it's a one liner or not. Unless you have some weird 'no more than one line of code in each method' rule. – Wendell

Actually, there is "no more than 3 lines per method" rule (M.Fawler et al) :) But the point of using LINQ is its composability, where you can chain queries togeter to form new queries – Renewal

And what new queries do you want to chain, once you have your boolean result, that cannot be chained from the boolean result obtained if you do follow Martin Fowler's advice to "refactor repeated fragments into a method which explains the purpose of the [fragment]" (Refactoring, p 110)? – Wendell

We are going in circles. You are very welcome to refactor one-liner into method, but the moment you decide to look at the implementation, you will find out that it takes much less time to understand Joel's solution than, for example, Guffas. – Renewal

The point of having the name reflect the purpose is so you don't care about the implementation. Having it in a method means it can be made 100 times faster without repetition if required, and it can be unit tested in isolation (rather than testing and hoping nothing goes wrong when cut&pasted) – Wendell

Answer 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();

Stewardson

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

Neb

Answer 8

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

Helaine

Answer 9

The following is simple and fast.

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

Boys