分享一个解数独的小程序，继续普及LINQ。
分享一个解数独的小程序，继续普及LINQ。
欢迎更好的算法，有可用分赠送。
数独游戏的规则可以Google下。
感谢反馈，现简要介绍算法和给代码做一点注释：
算法大致是，依次尝试给空格填入数字。首先寻找一个空格（我选择找从上到下，从左到右第一个空格（为0的元素）），作为进行试探的空格。首先看这个空格，对应的行、列、宫已经有的数字，根据它们的并集和0-9的差集求得可以尝试的数字。我们依次试探填入，并且将填入的数字作为已知的盘面求解下一个空格……这样找下去，最终会出现两种可能，一个是对于某个空格，没有可以选择的候选数字了，那么进入死胡同，就需要对上一个空格回溯，选择下一个尝试，如果上一个空格的所有选择用完还不行，就再回溯到上上个……还有一种情况，最后一个空格有且只有一个选择，这种情况下，填入这个数字，数独解算完成。
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication1{ class Program { static void Main(string[] args) { int[] source = { 5, 4, 0, 2, 9, 0, 0, 1, 0, 0, 2, 0, 0, 0, 6, 3, 0, 0, 3, 0, 0, 1, 0, 0, 0, 5, 4, 0, 6, 0, 0, 0, 8, 9, 0, 0, 2, 5, 0, 6, 7, 0, 0, 3, 1, 0, 0, 1, 0, 2, 0, 0, 6, 0, 8, 3, 0, 0, 0, 4, 0, 0, 6, 0, 0, 5, 9, 0, 0, 0, 8, 0, 0, 7, 0, 0, 3, 1, 0, 4, 2 }; // http://www.sudoku.name/index-cn.php #10332 数独来自这个网站 int[] result = source.ToArray(); // result数组保存解算中间数据和结果 Func<bool> IsFinished = () => result.Where(x => x == 0).Count() == 0; // 判断是否解算完成 Func<int> NextNumber = () => result.Select((x, i) => new { x, i }).First(x => x.x == 0).i; // 取下一个空格（这个算法不是唯一的，你也可以从后往前填写，或者别的方法） Func<IEnumerable<int>> TryValues = () => { int pos = NextNumber(); // 获取空格 int col = pos % 9; // 行号 int row = pos / 9; // 列号 int group = (row / 3) * 3 + col / 3; // 宫号 var colnums = Enumerable.Range(1, 9).Except(Enumerable.Range(0, 81).Where(x => x % 9 == col).Select(x => result[x]).Where(x => x != 0)); // 让1-9和本列已有数据对比，求差集，差集是对于列，允许填入的数字，下面类似 var rownums = Enumerable.Range(1, 9).Except(Enumerable.Range(0, 81).Where(x => x / 9 == row).Select(x => result[x]).Where(x => x != 0)); var groupnumbers = Enumerable.Range(1, 9).Except(Enumerable.Range(0, 81).Where(x => ((x / 9) / 3) * 3 + (x % 9) / 3 == group).Select(x => result[x]).Where(x => x != 0)); return colnums.Intersect(rownums).Intersect(groupnumbers); //数据是行、列、宫的交集 }; // 找出填写这个空格的所有可能尝试的数据 Action DisplayResult = () => Console.WriteLine(string.Join("\r\n", result.Select((x, i) => new { x, i }).GroupBy(x => x.i / 9).Select(x => string.Join(" ", x.Select(y => y.x)))) + "\r\n"); // 显示结果 Action Solve = () => { }; // 递归Lambda必须先定义一个空的。 Solve = () => { if (IsFinished()) { DisplayResult(); //如果全部填满，就输出结果（严格地，应该考虑无解的情况，这里忽略） } else { int pos = NextNumber(); // 获取空格位置 foreach (int item in TryValues()) // 依次尝试所有可能的数字 { result[pos] = item; // 将盘面设置为尝试数字 Solve(); //下一层解算 } result[pos] = 0; // 尝试完还不行，恢复盘面，回溯上一层 } }; // 算法主体 Solve(); // 开始解算 } }}static void Main(){ byte[] source = { 5, 4, 0, 2, 9, 0, 0, 1, 0, 0, 2, 0, 0, 0, 6, 3, 0, 0, 3, 0, 0, 1, 0, 0, 0, 5, 4, 0, 6, 0, 0, 0, 8, 9, 0, 0, 2, 5, 0, 6, 7, 0, 0, 3, 1, 0, 0, 1, 0, 2, 0, 0, 6, 0, 8, 3, 0, 0, 0, 4, 0, 0, 6, 0, 0, 5, 9, 0, 0, 0, 8, 0, 0, 7, 0, 0, 3, 1, 0, 4, 2 }; // http://www.sudoku.name/index-cn.php #10332 数独来自这个网站 for (List<byte[]> leaves = new List<byte[]>() { source }; leaves.Count > 0; ) { if (leaves[0].All(n => n > 0)) { leaves.ForEach(result => { string[] numbers = result.Select((b, i) => (i % 9 == 0 ? "\r\n" : " ") + b).ToArray(); Console.WriteLine("------------------" + string.Join("", numbers)); }); break; } leaves = ( from leaf in leaves let index = Array.IndexOf(leaf, (byte)0) let sameRow = Enumerable.Range(0, 9).Select(i => i + index / 9 * 9) let sameCol = Enumerable.Range(0, 9).Select(i => i * 9 + (index % 9)) let sameBox = Enumerable.Range(0, 9).Select(i => index/27*27 + (index%9)/3*3 + i/3*9 + i%3) let affected = sameRow.Concat(sameCol).Concat(sameBox).ToArray() from number in Enumerable.Range(1, 9) where affected.All(i => leaf[i] != number) select leaf.Select((b, i) => (byte)(i != index ? b : number)).ToArray() ).ToList(); }}
[解决办法]
Action DisplayResult = () => Console.WriteLine(string.Join("\r\n", result.Select((x, i) => new { x, i }).GroupBy(x => x.i / 9).Select(x => string.Join(" ", x.Select(y => y.x)))) + "\r\n"); // 显示结果