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

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

Answer 2

幸运的是,我不久前自己建造了一个数独求解器:)整个事情大约是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;
}

它可能无关紧要,因为数组限制为9个项目,但如果你调用它很多,它可能会加起来.