C语言中的数独算法#

这比LINQ解决方案快约50-250倍(取决于发现副本的时间):

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

幸运的是,不久前我自己制作了一个数独解算器:)整个过程大约有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 之前 分组。尽管基于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;
}

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

为什么您想要一行复杂的Linq代码,而不是将测试的有效实现封装在扩展方法中并调用它?

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

非onzero重复的一个实现可以是使用short的9个最低位来指示数组中是否存在值,从而在不使用动态内存的情况下进行O(长度(a))测试。Linq很可爱,但除非你只是出于审美的原因使用它(你并没有特别说你是在用Linq作为练习来编写数独解算器),否则它似乎只是增加了这里的复杂性。

这是一个老问题,但最近有人向我提出了一个使用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];
}

为了简洁起见,如果不是性能,那么 var itIsOk=a.Sum()==a.Distinct().Sum();

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

推理:首先创建一个不带0的枚举。在剩余的数字中,如果其不同列表的长度与实际列表的长度相同,则不存在重复。

或: 如果唯一编号列表小于实际列表,则必须有一个重复编号。

这是单行程序版本。a.Where(x=>x>0)列表可以分解出来。

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

我通常不赞成包含捕获变量的解决方案,但我有一种强烈的欲望写下以下内容:

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

下面是简单而快速的。

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