C#中的数独算法 [英] Sudoku algorithm in C#

问题描述

我需要一个衬套(或接近衬套)来验证给定的9个元素数组不包含重复的数字1,2,3，...，9.重复的零不计数(它们代表空单元格).

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.

推荐答案

很幸运，我不久前自己建立了一个数独求解器:)整个过程大约是200行C#，它将解决我遇到的最棘手的难题可以在4秒或更短的时间内找到行.

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.

由于使用.Count，性能可能不太好，但它应该可以工作:

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)

此外，确实不需要j != 0部分，但是它应该可以帮助事情更快地运行.

Also, the j != 0 part isn't really needed, but it should help things run a bit faster.

[edit:] kvb的回答给了我另一个主意:

[edit:] kvb's answer gave me another idea:

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

在分组之前过滤0的 .尽管基于IEnumerable的工作方式，但这可能没关系.

Filter the 0's before grouping. Though based on how IEnumerable works it may not matter any.

无论哪种方式，为了获得最佳性能，请使用以下新的IEnumerable扩展方法替换其中的.Count > 1:

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

由于数组限于9个项目，因此可能没什么大不了的，但是如果您多次调用它，则可能加起来.

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.

这篇关于C#中的数独算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！