Алгоритм Судоку в 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; 

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

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

Answer 1

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

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

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

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

[править:] ответ KVB дал мне еще одну идею:

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

Фильтр 0'S перед тем группировки. Хотя на основе того, как работает 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 2

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

Answer 3

Как насчет:

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

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

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

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

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

Answer 4

Почему вы хотите замысловатую линию Linq коды, а не подведению эффективного выполнения теста в методе расширения и вызов, что?

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

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

Answer 5

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

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 6

Это примерно в 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 7

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

Вы можете прочитать на моем блоге о том, как Solve Sudoku in 1 line of 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 8

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

Answer 9

Следующие простые и быстрые.

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