Алгоритм судоку в C #

Question

Мне нужен один вкладыш (или близкий к нему), который проверяет, что данный массив из 9 элементов не содержит повторяющихся чисел 1,2,3, ..., 9. Повторяющиеся нули не учитываются (они представляют пустые ячейки).

Лучшее, что у меня получилось, это:

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;

Если вы не хотите решать мои проблемы :), могли бы вы хотя бы сказать, правильно ли работает вышеуказанный алгоритм?

И, да, прочитал этот .

Answer 1

Это примерно в 50-250 раз быстрее, чем решение LINQ (в зависимости от того, как рано обнаружен дубликат):

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

Answer 2

К счастью для вас, я сам не так давно построил решатель судоку :) Все это было около 200 строк C #, и это решило бы самые сложные головоломки, которые я мог найти, за 4 секунды или меньше.

Производительность, вероятно, не так велика из-за использования .Count, но она должна работать:

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

Кроме того, j != 0 часть на самом деле не нужна, но она должна помочь вещам работать немного быстрее.

[edit:] Ответ kvb дал мне другую идею:

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

Отфильтруйте 0 перед группировкой . Хотя в зависимости от того, как работает IEnumerable, это может не иметь никакого значения.

В любом случае, для лучшей производительности замените .Count > 1 в любом из них новым методом расширения IEnumerable, который выглядит следующим образом:

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

Вероятно, это не будет иметь большого значения, так как массивы ограничены 9 элементами, но если вы их много называете, это может сложиться.

Answer 3

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

Answer 4

Это старый вопрос, но недавно я указал на однострочное решение, использующее пользовательский SQL Oracle для создания древовидных структур. Я подумал, что было бы неплохо преобразовать это в Linq.

Вы можете прочитать больше в моем блоге о том, как Решить судоку в 1 строке Linq

Вот код:

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

Answer 5

Зачем вам нужна извилистая строка кода Linq, а не завершение эффективной реализации теста в методе расширения и вызов этого?

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

Одной из реализаций NoNonZeroRepeats может быть использование 9 младших битов короткого замыкания для указания наличия значения в массиве, что дает тест O (length (a)) без использования динамической памяти. Linq симпатичен, но если вы используете его только по эстетическим соображениям (вы не говорите, что пишете решатель судоку, используя только Linq в качестве упражнения), он просто добавляет сложности.

Answer 6

Для краткости, если не производительности, как насчет var itIsOk = a.Sum () == a.Distinct (). Sum ();

Answer 7

Я обычно недоволен решениями, в которых используются захваченные переменные, но у меня было желание написать следующее:

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 8

Как насчет:

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

Причина: сначала создайте перечисление без нулей. Из остальных чисел, если его отдельный список имеет ту же длину, что и фактический список, то повторов нет.

или: Если список уникальных номеров меньше, чем фактический список, то у вас должен быть повторный номер.

Это однострочная версия. Список a.Where (x => x> 0) может быть исключен.

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

Answer 9

Это просто и быстро.

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