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

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.

Answer 2

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

Answer 3

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