C#中的数独算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/723213/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sudoku algorithm in C#
提问by Prankster
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).
我需要一个衬里（或接近它）来验证给定的 9 个元素数组不包含重复数字 1,2,3,...,9。重复的零不计数（它们代表空单元格）。
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.
而且，是的，读过这个。
采纳答案by Joel Coehoorn
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.
幸运的是，我不久前自己构建了一个数独求解器 :) 整个过程大约是 200 行 C#，它可以在 4 秒或更短的时间内解决我能找到的最棘手的难题。
Performance probably isn't that great due to the use of .Count, but it should work:
由于使用了 .Count，性能可能不是那么好，但它应该可以工作：
!a.Any(i => i != 0 && a.Where(j => j != 0 && i == j).Count > 1)
Also, the j != 0part isn't really needed, but it should help things run a bit faster.
此外，该j != 0部件并不是真正需要的，但它应该可以帮助事情运行得更快一些。
[edit:] kvb's answer gave me another idea:
[编辑：] kvb 的回答给了我另一个想法：
!a.Where(i => i != 0).GroupBy(i => i).Any(gp => gp.Count() > 1)
Filter the 0's beforegrouping. Though based on how IEnumerable works it may not matter any.
在分组之前过滤 0 。虽然基于 IEnumerable 的工作方式，但它可能无关紧要。
Either way, For best performance replace .Count > 1in either of those with a new IEnumerable extension method that looks like this:
无论哪种方式，为了获得最佳性能.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;
}
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.
这可能不会太重要，因为数组仅限于 9 个项目，但如果你调用它很多，它可能会加起来。
回答by kvb
!a.GroupBy(i => i).Any(gp => gp.Key != 0 && gp.Count() > 1)
!a.GroupBy(i => i).Any(gp => gp.Key != 0 && gp.Count() > 1)
回答by geofftnz
How about:
怎么样：
var itIsOk = a.Where(x => x > 0).Distinct().Count() == a.Where(x => x > 0).Count();
Reasoning: First create an enumeration without 0s. Out of the remaining numbers, if its distinct list is the same length as the actual list, then there are no repeats.
推理：首先创建一个没有 0 的枚举。在剩余的数字中，如果其不同列表与实际列表的长度相同，则没有重复。
or: If the list of unique numbers is smaller than the actual list, then you must have a repeated number.
或：如果唯一编号列表小于实际列表，则您必须有重复编号。
This is the one-liner version. The a.Where(x=>x>0) list could be factored out.
这是单线版。a.Where(x=>x>0) 列表可以被分解。
var nonZeroList = a.Where(x => x > 0).ToList();
var itIsOk = nonZeroList.Distinct().Count() == nonZeroList.Count();
回答by Pete Kirkham
Why do you want a convoluted line of Linq code, rather than wrapping up an efficient implementation of the test in an extension method and calling that?
为什么您需要一行复杂的 Linq 代码，而不是将测试的有效实现包装在扩展方法中并调用它？
var a = new int[9] {1,2,3,4,5,6,7,8,9};
var itIsOk = a.HasNoNonZeroRepeats();
One implementation of NoNonZeroRepeats could be to use the 9 lowest bits of a short to indicate presence of a value in the array, giving an O(length(a)) test with no dynamic memory use. Linq is cute, but unless you're only using it for aesthetic reasons (you don't specifically say that you're writing a sudoku solver using only Linq as an exercise) it seems to be just adding complexity here.
NoNonZeroRepeats 的一种实现可能是使用 short 的 9 个最低位来指示数组中存在某个值，从而在不使用动态内存的情况下进行 O(length(a)) 测试。Linq 很可爱，但除非您只是出于审美原因使用它（您没有明确说您正在编写仅使用 Linq 作为练习的数独求解器），否则它似乎只是在这里增加了复杂性。
回答by Amy B
I usually frown on solutions that involve captured variables, but I had an urge to write this:
我通常不赞成涉及捕获变量的解决方案，但我有冲动写下这个：
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);
}
回答by Guffa
This is about 50-250 times faster than a LINQ solution (depending on how early the duplicate is found):
这比 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;
}
回答by Jason
This is an old question, but I recently was pointed to a 1 line solution using Oracle's custom SQL for doing tree-like structures. I thought it would be nice to convert this into Linq.
这是一个老问题，但最近有人指出我使用 Oracle 的自定义 SQL 进行树状结构的 1 行解决方案。我认为将其转换为 Linq 会很好。
You can read more on my blog about how to Solve Sudoku in 1 line of Linq
你可以在我的博客上阅读更多关于如何在 1 行 Linq 中解决数独
Here is the code:
这是代码：
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];
}
回答by Richard Astle
For brevity if not performance, how about var itIsOk = a.Sum() == a.Distinct().Sum();
为了简洁，如果不是性能， var itIsOk = a.Sum() == a.Distinct().Sum();
回答by Scormer
The following is simple and fast.
下面简单快速。
if a.Select(i => Math.Pow(2, i - 1)).ToArray().Sum()==511 ...
