【散300分】从n皇后有关问题看Linq的对算法思想的清晰表达力
日期：2014-05-20 浏览次数：20879 次
【散300分】从n皇后问题看Linq的对算法思想的清晰表达力
好久不散分了，只因没有遇到好的题目。
因为今天看到下午有一个关于n皇后问题的帖子，我忽然想到了这种循环、递归、查找、分析之类的软件，很适合我们来了解Linq。
首先请看原帖：http://topic.csdn.net/u/20100411/14/df813a56-1465-4ec5-9afb-fd78b6a42424.html?47334
我大致用Linq写了一遍，不知道对不对，还请各位来验证。
先来看看我们要输出的结构：皇后棋子是我们要求求解的具体对象
每一个棋盘，就是一个n皇后的列表，即IEnumerable<Queen>。而对于n皇后，有多种解答，因此要表达所有可能的解答，就需要结构 IEnumerable<IEnumerable<Queen>>。确定静态结构，就可以直接看懂下面的算法了：
由于是递归，我们给出递归停止的条件，即n为1时直接给出1个皇后的初始可行解。
OK，一切结束。如果要求8皇后问题，我们调用Queens(8，8）就可以得到全部92个棋盘的列表了。
不过写两个8觉得不好看，我们重载这个求解方法：
现在可以测试了：如果要打印8皇后问题前10个解，可以这样输出：
大家可以试一试，想一想，回味一下Linq是怎么“只用一句话来表达”计算方法的。
另外我也推荐大家看一下微软的一个名叫 LINQRayTracer 的小demo，它本是用来演示多核计算的功能的，里边的核心也只用一句Linq语句来表达一个完整的系统功能，贴在这里参考：
好久不散分了，只因没有遇到好的题目。
因为今天看到下午有一个关于n皇后问题的帖子，我忽然想到了这种循环、递归、查找、分析之类的软件，很适合我们来了解Linq。
首先请看原帖：http://topic.csdn.net/u/20100411/14/df813a56-1465-4ec5-9afb-fd78b6a42424.html?47334
我大致用Linq写了一遍，不知道对不对，还请各位来验证。
先来看看我们要输出的结构：皇后棋子是我们要求求解的具体对象
- C# code
public class Queen
{
public int line;
public int column;
}
每一个棋盘，就是一个n皇后的列表，即IEnumerable<Queen>。而对于n皇后，有多种解答，因此要表达所有可能的解答，就需要结构 IEnumerable<IEnumerable<Queen>>。确定静态结构，就可以直接看懂下面的算法了：
- C# code
static IEnumerable<IEnumerable<Queen>> Queens(int n, int maxN)
{
if (n > 1)
return from x in Queens(n - 1, maxN)
from y in GetNums(maxN)
where !x.Any(q => q.column == y || Math.Abs(n - q.line) == Math.Abs(y - q.column))
select x.Union(new List<Queen> { new Queen { line = n, column = y } });
else if (n == 1)
return from q in GetNums(maxN)
select (IEnumerable<Queen>)new List<Queen> { new Queen { line = 1, column = q } };
else
throw new InvalidOperationException();
}
由于是递归，我们给出递归停止的条件，即n为1时直接给出1个皇后的初始可行解。
OK，一切结束。如果要求8皇后问题，我们调用Queens(8，8）就可以得到全部92个棋盘的列表了。
不过写两个8觉得不好看，我们重载这个求解方法：
- C# code
static IEnumerable<IEnumerable<Queen>> Queens(int maxN)
{
return Queens(maxN, maxN);
}
现在可以测试了：如果要打印8皇后问题前10个解，可以这样输出：
- C# code
Queens(8).Take(10)
.ToList()
.ForEach(result =>
{
result.ToList().ForEach(q => { Console.Write("{0} ", q.column); });
Console.WriteLine();
});
大家可以试一试，想一想，回味一下Linq是怎么“只用一句话来表达”计算方法的。
另外我也推荐大家看一下微软的一个名叫 LINQRayTracer 的小demo，它本是用来演示多核计算的功能的，里边的核心也只用一句Linq语句来表达一个完整的系统功能，贴在这里参考：
- C# code
var pixelsQuery = from y in Enumerable.Range(0, screenHeight).AsParallel().WithDegreeOfParallelism(parallel ? 2 : 1)
let recenterY = -(y - (screenHeight / 2.0)) / (2.0 * screenHeight)
select from x in Enumerable.Range(0, screenWidth)
let recenterX = (x - (screenWidth / 2.0)) / (2.0 * screenWidth)
let point =
Vector.Norm(Vector.Plus(scene.Camera.Forward,
Vector.Plus(Vector.Times(recenterX, scene.Camera.Right),
Vector.Times(recenterY, scene.Camera.Up))))
let ray = new Ray() { Start = scene.Camera.Pos, Dir = point }
let computeTraceRay = (Func<Func<TraceRayArgs, Color>, Func<TraceRayArgs, Color>>)
(f => traceRayArgs =>
(from isect in
from thing in traceRayArgs.Scene.Things
select thing.Intersect(traceRayArgs.Ray)
where isect != null
orderby isect.Dist
let d = isect.Ray.Dir
let pos = Vector.Plus(Vector.Times(isect.Dist, isect.Ray.Dir), isect.Ray.Start)
let normal = isect.Thing.Normal(pos)
let reflectDir = Vector.Minus(d, Vector.Times(2 * Vector.Dot(normal, d), normal))
let naturalColors =
from light in traceRayArgs.Scene.Lights
let ldis = Vector.Minus(light.Pos, pos)
let livec = Vector.Norm(ldis)
let testRay = new Ray() { Start = pos, Dir = livec }
let testIsects = from inter in
from thing in traceRayArgs.Scene.Things
select thing.Intersect(testRay)
where inter != null
orderby inter.Dist
select inter
let testIsect = testIsects.FirstOrDefault()
let neatIsect = testIsect == null ? 0 : testIsect.Dist
let isInShadow = !((neatIsect > Vector.Mag(ldis)) || (neatIsect == 0))
where !isInShadow
let illum = Vector.Dot(livec, normal)
let lcolor = illum > 0 ? Color.Times(illum, light.Color) : Color.Make(0, 0, 0)
let specular = Vector.Dot(livec, Vector.Norm(reflectDir))
let scolor = specular > 0
? Color.Times(Math.Pow(specular, isect.Thing.Surface.Roughness),
light.Color)
: Color.Make(0, 0, 0)
select Color.Plus(Color.Times(isect.Thing.Surface.Diffuse(pos), lcolor),
Color.Times(isect.Thing.Surface.Specular(pos), scolor))
let reflectPos = Vector.Plus(pos, Vector.Times(.001, reflectDir))
let reflectColor = traceRayArgs.Depth >= MaxDepth
? Color.Make(.5, .5, .5)
: Color.Times(isect.Thing.Surface.Reflect(reflectPos),
f(new TraceRayArgs(new Ray()
{
Start = reflectPos,
Dir = reflectDir
},
traceRayArgs.Scene,
traceRayArgs.Depth + 1)))
select naturalColors.Aggregate(reflectColor,
(color, natColor) => Color.Plus(color, natColor))
).DefaultIfEmpty(Color.Background).First())
let traceRay = Y(computeTraceRay)
select new { X = x, Y = y, Color = traceRay(new TraceRayArgs(ray, scene, 0)) };
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
