使用 LINQ 解决（基于公式的）数独谜题
4.95/5 (5投票s)
解决基于公式的数独谜题。
引言
我是一个寻宝爱好者。2012 年 1 月的一个周末，我们去了海德堡，在那里发布了一个新的寻宝游戏，需要解决一个基于公式的数独谜题。我们一组人手工解决了它（大约 30 分钟）。回到工作岗位后，我给一位同事（我们称他为 Bob）展示了这个谜题，我们开始讨论是否可以编写一个 LINQ 查询来解决这个谜题。
Bob 向我展示了 MSDN 博客文章，使用 LINQ 解决谜题，我们以此为基础来解决这个数独谜题。
这篇原始文章由我于 2013 年 1 月 25 日发表于此。
背景
这就是基于公式的数独谜题的样子
首先，我想通过简化问题来理解这个 LINQ 查询是如何工作的。
概念验证
我画了一个小的 3x3 网格并输入了一些数字。
我在每个单元格中输入了从 1 到 9 的“随机”数字。在这个阶段，我正在模拟数独谜题的一部分，这样当我编写 LINQ 查询时，我可以更好地理解它。处理 3x3 网格并理解发生了什么是比处理 9x9 网格简单得多的。
一旦我有了数字，我就编写了一些我自己的公式，如下所示
碰巧的是，我输入了三个循环引用。这帮助我理解了后面的“from”和“joins”是如何工作的（见下文）。
我从 MSDN 博客文章中的暴力破解方法开始，我开始使用的代码如下所示
var solveForNumbers =
from a1 in Enumerable.Range(1, 9)
from a2 in Enumerable.Range(1, 9)
from a3 in Enumerable.Range(1, 9)
from b1 in Enumerable.Range(1, 9)
from b2 in Enumerable.Range(1, 9)
from b3 in Enumerable.Range(1, 9)
from c1 in Enumerable.Range(1, 9)
from c2 in Enumerable.Range(1, 9)
from c3 in Enumerable.Range(1, 9)
where (a1 == b3 - 4)
&& (a2 == a3 - b2)
&& (a3 == b2 * c3)
&& (b1 == a3 + a1)
&& (b2 == c2 - a3)
&& (b3 == a1 + a2)
&& (c1 == a3 + c3)
&& (c2 == a2 * b2)
&& (c3 == b3 - b2)
select new
{ a1, a2, a3, b1, b2, b3, c1, c2, c3};
在这个基本谜题上，在我的笔记本电脑上解决它大约需要 110 秒。以这种方式解决大型谜题（9 x 9 网格）所需的时间将会呈指数级增长。
然后，我按照 MSDN 博客文章中的说明，开始将每个“where”子句移动到“join”中。我想看看在此过程中速度的改进情况。
我将第一个条目“c3”移动到 join 中，如下所示
var solveForNumbers1 =
from a1 in Enumerable.Range(1, 9)
from a2 in Enumerable.Range(1, 9)
from a3 in Enumerable.Range(1, 9)
from b1 in Enumerable.Range(1, 9)
from b2 in Enumerable.Range(1, 9)
from b3 in Enumerable.Range(1, 9)
from c1 in Enumerable.Range(1, 9)
from c2 in Enumerable.Range(1, 9)
join c3 in Enumerable.Range(1, 9) on b3 - b2 equals c3
where (a1 == b3 - 4)
&& (a2 == a3 - b2)
&& (a3 == b2 * c3)
&& (b1 == a3 + a1)
&& (b2 == c2 - a3)
&& (b3 == a1 + a2)
&& (c1 == a3 + c3)
&& (c2 == a2 * b2)
select new
{ a1, a2, a3, b1, b2, b3, c1, c2, c3};
我重新运行了测试，现在只花了 12 秒。哇！节省了将近 100 秒。
在 Rankadu 的一些帮助下，我将它们全部移动过来，最终得到了这段代码
var solveForNumbers1 =
from b2 in Enumerable.Range(1, 9)
from a3 in Enumerable.Range(1, 9)
from a1 in Enumerable.Range(1, 9)
join a2 in Enumerable.Range(1, 9) on a3 - b2 equals a2
join b3 in Enumerable.Range(1, 9) on a1 + a2 equals b3
join c3 in Enumerable.Range(1, 9) on b3 - b2 equals c3
join c2 in Enumerable.Range(1, 9) on a2 * b2 equals c2
join b1 in Enumerable.Range(1, 9) on a3 + a1 equals b1
join c1 in Enumerable.Range(1, 9) on a3 + c3 equals c1
where (b2 == c2 - a3)
&& (a3 == b2 * c3)
&& (a1 == b3 - 4)
select new
{ a1, a2, a3, b1, b2, b3, c1, c2, c3};
这里需要一些解释
b2、a3 和 a1 留在“from”部分的原因是，存在对该值的循环引用。
- b2 == c2 - a3
- and c2 == a2 * b2
- and a2 == a3 - b2
- （b2 取决于 c2，而 c2 取决于 b2）
- （b2 取决于 c2，而 c2 包含 a2，而 a2 取决于 b2）
因此，“join”无法可靠地知道该值是什么，因此必须将其留在代码的 from 部分。
Joins 的排序
添加 join 时，公式的值必须在当时（先前定义）已知。由于 c3 == b3 - b2，因此 b3 和 b2 的值必须在 c3 join 之前定义。
一旦我完成了这些并运行了测试，我就知道如何解决 9x9 网格了。
使用代码
当我在 3x3 网格上测试概念验证时，Bob 开始使用 9x9 网格进行暴力破解（或“where 子句”方法）。
这是结果。
var solveForNumbers =
from a1 in Enumerable.Range(1, 9)
from a2 in Enumerable.Range(1, 9)
from a3 in Enumerable.Range(1, 9)
from a4 in Enumerable.Range(1, 9)
from a5 in Enumerable.Range(1, 9)
from a6 in Enumerable.Range(1, 9)
from a7 in Enumerable.Range(1, 9)
from a8 in Enumerable.Range(1, 9)
from a9 in Enumerable.Range(1, 9)
from b1 in Enumerable.Range(1, 9)
from b2 in Enumerable.Range(1, 9)
from b3 in Enumerable.Range(1, 9)
from b4 in Enumerable.Range(1, 9)
from b5 in Enumerable.Range(1, 9)
from b6 in Enumerable.Range(1, 9)
from b7 in Enumerable.Range(1, 9)
from b8 in Enumerable.Range(1, 9)
from b9 in Enumerable.Range(1, 9)
from c1 in Enumerable.Range(1, 9)
from c2 in Enumerable.Range(1, 9)
from c3 in Enumerable.Range(1, 9)
from c4 in Enumerable.Range(1, 9)
from c5 in Enumerable.Range(1, 9)
from c6 in Enumerable.Range(1, 9)
from c7 in Enumerable.Range(1, 9)
from c8 in Enumerable.Range(1, 9)
from c9 in Enumerable.Range(1, 9)
from d1 in Enumerable.Range(1, 9)
from d2 in Enumerable.Range(1, 9)
from d3 in Enumerable.Range(1, 9)
from d4 in Enumerable.Range(1, 9)
from d5 in Enumerable.Range(1, 9)
from d6 in Enumerable.Range(1, 9)
from d7 in Enumerable.Range(1, 9)
from d8 in Enumerable.Range(1, 9)
from d9 in Enumerable.Range(1, 9)
from e1 in Enumerable.Range(1, 9)
from e2 in Enumerable.Range(1, 9)
from e3 in Enumerable.Range(1, 9)
from e4 in Enumerable.Range(1, 9)
from e5 in Enumerable.Range(1, 9)
from e6 in Enumerable.Range(1, 9)
from e7 in Enumerable.Range(1, 9)
from e8 in Enumerable.Range(1, 9)
from e9 in Enumerable.Range(1, 9)
from f1 in Enumerable.Range(1, 9)
from f2 in Enumerable.Range(1, 9)
from f3 in Enumerable.Range(1, 9)
from f4 in Enumerable.Range(1, 9)
from f5 in Enumerable.Range(1, 9)
from f6 in Enumerable.Range(1, 9)
from f7 in Enumerable.Range(1, 9)
from f8 in Enumerable.Range(1, 9)
from f9 in Enumerable.Range(1, 9)
from g1 in Enumerable.Range(1, 9)
from g2 in Enumerable.Range(1, 9)
from g3 in Enumerable.Range(1, 9)
from g4 in Enumerable.Range(1, 9)
from g5 in Enumerable.Range(1, 9)
from g6 in Enumerable.Range(1, 9)
from g7 in Enumerable.Range(1, 9)
from g8 in Enumerable.Range(1, 9)
from g9 in Enumerable.Range(1, 9)
from h1 in Enumerable.Range(1, 9)
from h2 in Enumerable.Range(1, 9)
from h3 in Enumerable.Range(1, 9)
from h4 in Enumerable.Range(1, 9)
from h5 in Enumerable.Range(1, 9)
from h6 in Enumerable.Range(1, 9)
from h7 in Enumerable.Range(1, 9)
from h8 in Enumerable.Range(1, 9)
from h9 in Enumerable.Range(1, 9)
from i1 in Enumerable.Range(1, 9)
from i2 in Enumerable.Range(1, 9)
from i3 in Enumerable.Range(1, 9)
from i4 in Enumerable.Range(1, 9)
from i5 in Enumerable.Range(1, 9)
from i6 in Enumerable.Range(1, 9)
from i7 in Enumerable.Range(1, 9)
from i8 in Enumerable.Range(1, 9)
from i9 in Enumerable.Range(1, 9)
where (a1 == e5 * e8)
&& (a2 == h1 - 2)
&& (a3 == c5 * e8)
&& (a4 == h9 - 1)
&& (a5 == d7 - e2)
&& (a6 == f1 + g7)
&& (a7 == e3 - h2)
&& (a8 == h6 + a9)
&& (a9 == g3 / g6)
&& (b1 == d1 - a9)
&& (b2 == g2 - h1)
&& (b3 == e5 - 4)
&& (b4 == c7 + 1)
&& (b5 == d7 - 7)
&& (b6 == i5 + d6)
&& (b7 == f8 + 1)
&& (b8 == a1 / i5)
&& (b9 == g3 + 3)
&& (c1 == i2 * a7)
&& (c2 == b4 * a7)
&& (c3 == c6 + 6)
&& (c4 == a2 * f5)
&& (c5 == c6 + 7)
&& (c6 == f8 - i3)
&& (c7 == d6 - 1)
&& (c8 == h8 + 1)
&& (c9 == g4 / c1)
&& (d1 == a7 * 3)
&& (d2 == i3 + a7)
&& (d3 == c2 - e2)
&& (d4 == f4 * i2)
&& (d5 == c4 + 2)
&& (d6 == h9 * e8)
&& (d7 == c4 * a2)
&& (d8 == d1 - a7)
&& (d9 == c1 * d4)
&& (e1 == i1 - e3)
&& (e2 == e3 + 3)
&& (e3 == d1 - g9)
&& (e4 == f1 + d1)
&& (e5 == d1 * 3)
&& (e6 == a5 + 4)
&& (e7 == g6 * h7)
&& (e8 == d9 - 7)
&& (e9 == i3 / e3)
&& (f1 == a3 / i2)
&& (f2 == b7 * e8)
&& (f3 == b6 * d3)
&& (f4 == h2 + 1)
&& (f5 == d1 - 2)
&& (f6 == g5 / b5)
&& (f7 == e3 * h3)
&& (f8 == h2 + h9)
&& (f9 == i1 - 3)
&& (g1 == c5 - f5)
&& (g2 == a6 + 2)
&& (g3 == e6 / a9)
&& (g4 == e8 + 7)
&& (g5 == d6 * a7)
&& (g6 == b1 + 1)
&& (g7 == h1 - 2)
&& (g8 == h5 - f4)
&& (g9 == a8 - a4)
&& (h1 == d2 - i2)
&& (h2 == h4 / i9)
&& (h3 == c7 - 2)
&& (h4 == f9 + 4)
&& (h5 == h2 + 6)
&& (h6 == d8 * 2)
&& (h7 == h1 - e9)
&& (h8 == f5 + 7)
&& (h9 == a1 - b8)
&& (i1 == f3 - b1)
&& (i2 == c9 / h7)
&& (i3 == i1 - c1)
&& (i4 == a6 - 6)
&& (i5 == d5 - d8)
&& (i6 == f6 + 2)
&& (i7 == c7 + 2)
&& (i8 == e3 + i2)
&& (i9 == f6 * g7)
select new
{
a1,a2,a3,a4,a5,a6,a7,a8,a9,
b1,b2,b3,b4,b5,b6,b7,b8,b9,
c1,c2,c3,c4,c5,c6,c7,c8,c9,
d1,d2,d3,d4,d5,d6,d7,d8,d9,
e1,e2,e3,e4,e5,e6,e7,e8,e9,
f1,f2,f3,f4,f5,f6,f7,f8,f9,
g1,g2,g3,g4,g5,g6,g7,g8,g9,
h1,h2,h3,h4,h5,h6,h7,h8,h9,
i1,i2,i3,i4,i5,i6,i7,i8,i9
};
这种暴力破解方法需要很长时间才能得到最终答案。
我运行了一个小时，结果当时只有
- a1 到 h9 全部为 1s 和
- i1=1, i3=1, i2=1, i4=1, i5=5, i6=1, i7=5, i8=5, i9=7
这仅仅超过 33 000 次迭代。
我把这段代码带回家，然后花了 4 个多小时将“where”子句重构为“join”，然后重新排序 join，我得到了这段代码
var solveForNumbers =
from i2 in Enumerable.Range(1, 9)
from i5 in Enumerable.Range(1, 9)
from h2 in Enumerable.Range(1, 9)
from e3 in Enumerable.Range(1, 9)
from a9 in Enumerable.Range(1, 9)
join a7 in Enumerable.Range(1, 9) on e3 - h2 equals a7
join d1 in Enumerable.Range(1, 9) on a7 * 3 equals d1
join b1 in Enumerable.Range(1, 9) on d1 - a9 equals b1
join g6 in Enumerable.Range(1, 9) on b1 + 1 equals g6
join d8 in Enumerable.Range(1, 9) on d1 - a7 equals d8
join h6 in Enumerable.Range(1, 9) on d8 * 2 equals h6
join a8 in Enumerable.Range(1, 9) on h6 + a9 equals a8
join e5 in Enumerable.Range(1, 9) on d1 * 3 equals e5
join b3 in Enumerable.Range(1, 9) on e5 - 4 equals b3
join f5 in Enumerable.Range(1, 9) on d1 - 2 equals f5
join h8 in Enumerable.Range(1, 9) on f5 + 7 equals h8
join c8 in Enumerable.Range(1, 9) on h8 + 1 equals c8
join c1 in Enumerable.Range(1, 9) on i2 * a7 equals c1
join e2 in Enumerable.Range(1, 9) on e3 + 3 equals e2
join i8 in Enumerable.Range(1, 9) on e3 + i2 equals i8
join h5 in Enumerable.Range(1, 9) on h2 + 6 equals h5
join f4 in Enumerable.Range(1, 9) on h2 + 1 equals f4
join d4 in Enumerable.Range(1, 9) on f4 * i2 equals d4
join d9 in Enumerable.Range(1, 9) on c1 * d4 equals d9
join e8 in Enumerable.Range(1, 9) on d9 - 7 equals e8
join a1 in Enumerable.Range(1, 9) on e5 * e8 equals a1
join b8 in Enumerable.Range(1, 9) on a1 / i5 equals b8
join h9 in Enumerable.Range(1, 9) on a1 - b8 equals h9
join a4 in Enumerable.Range(1, 9) on h9 - 1 equals a4
join g9 in Enumerable.Range(1, 9) on a8 - a4 equals g9
join f8 in Enumerable.Range(1, 9) on h2 + h9 equals f8
join b7 in Enumerable.Range(1, 9) on f8 + 1 equals b7
join d6 in Enumerable.Range(1, 9) on h9 * e8 equals d6
join b6 in Enumerable.Range(1, 9) on i5 + d6 equals b6
join c7 in Enumerable.Range(1, 9) on d6 - 1 equals c7
join b4 in Enumerable.Range(1, 9) on c7 + 1 equals b4
join c2 in Enumerable.Range(1, 9) on b4 * a7 equals c2
join d3 in Enumerable.Range(1, 9) on c2 - e2 equals d3
join f3 in Enumerable.Range(1, 9) on b6 * d3 equals f3
join i1 in Enumerable.Range(1, 9) on f3 - b1 equals i1
join e1 in Enumerable.Range(1, 9) on i1 - e3 equals e1
join f9 in Enumerable.Range(1, 9) on i1 - 3 equals f9
join h4 in Enumerable.Range(1, 9) on f9 + 4 equals h4
join i3 in Enumerable.Range(1, 9) on i1 - c1 equals i3
join c6 in Enumerable.Range(1, 9) on f8 - i3 equals c6
join c3 in Enumerable.Range(1, 9) on c6 + 6 equals c3
join c5 in Enumerable.Range(1, 9) on c6 + 7 equals c5
join g1 in Enumerable.Range(1, 9) on c5 - f5 equals g1
join a3 in Enumerable.Range(1, 9) on c5 * e8 equals a3
join f1 in Enumerable.Range(1, 9) on a3 / i2 equals f1
join e4 in Enumerable.Range(1, 9) on f1 + d1 equals e4
join d2 in Enumerable.Range(1, 9) on i3 + a7 equals d2
join h1 in Enumerable.Range(1, 9) on d2 - i2 equals h1
join g7 in Enumerable.Range(1, 9) on h1 - 2 equals g7
join a6 in Enumerable.Range(1, 9) on f1 + g7 equals a6
join a2 in Enumerable.Range(1, 9) on h1 - 2 equals a2
join c4 in Enumerable.Range(1, 9) on a2 * f5 equals c4
join d5 in Enumerable.Range(1, 9) on c4 + 2 equals d5
join d7 in Enumerable.Range(1, 9) on c4 * a2 equals d7
join a5 in Enumerable.Range(1, 9) on d7 - e2 equals a5
join i4 in Enumerable.Range(1, 9) on a6 - 6 equals i4
join g2 in Enumerable.Range(1, 9) on a6 + 2 equals g2
join b2 in Enumerable.Range(1, 9) on g2 - h1 equals b2
join e6 in Enumerable.Range(1, 9) on a5 + 4 equals e6
join g3 in Enumerable.Range(1, 9) on e6 / a9 equals g3
join b9 in Enumerable.Range(1, 9) on g3 + 3 equals b9
join b5 in Enumerable.Range(1, 9) on d7 - 7 equals b5
join e9 in Enumerable.Range(1, 9) on i3 / e3 equals e9
join h7 in Enumerable.Range(1, 9) on h1 - e9 equals h7
join e7 in Enumerable.Range(1, 9) on g6 * h7 equals e7
join i7 in Enumerable.Range(1, 9) on c7 + 2 equals i7
join g5 in Enumerable.Range(1, 9) on d6 * a7 equals g5
join f6 in Enumerable.Range(1, 9) on g5 / b5 equals f6
join i9 in Enumerable.Range(1, 9) on f6 * g7 equals i9
join i6 in Enumerable.Range(1, 9) on f6 + 2 equals i6
join h3 in Enumerable.Range(1, 9) on c7 - 2 equals h3
join f7 in Enumerable.Range(1, 9) on e3 * h3 equals f7
join f2 in Enumerable.Range(1, 9) on b7 * e8 equals f2
join g4 in Enumerable.Range(1, 9) on e8 + 7 equals g4
join c9 in Enumerable.Range(1, 9) on g4 / c1 equals c9
join g8 in Enumerable.Range(1, 9) on h5 - f4 equals g8
where
(e3 == d1 - g9) &&
(a9 == g3 / g6) &&
(h2 == h4 / i9) &&
(i2 == c9 / h7) &&
(i5 == d5 - d8)
select new
{
a1, a2, a3, a4, a5, a6, a7, a8, a9,
b1, b2, b3, b4, b5, b6, b7, b8, b9,
c1, c2, c3, c4, c5, c6, c7, c8, c9,
d1, d2, d3, d4, d5, d6, d7, d8, d9,
e1, e2, e3, e4, e5, e6, e7, e8, e9,
f1, f2, f3, f4, f5, f6, f7, f8, f9,
g1, g2, g3, g4, g5, g6, g7, g8, g9,
h1, h2, h3, h4, h5, h6, h7, h8, h9,
i1, i2, i3, i4, i5, i6, i7, i8, i9
};
我运行了代码，然后在仅仅 8 秒内计算出了答案。
结论
- LINQ 可用于解决不同类型的谜题。
- 使用
join可以大大减少找到答案所花费的时间。 - 工作表中引用自身的公式无法添加到
join中，只能在“from”部分中使用。这意味着 LINQ 查询必须 *猜测* 这些值。猜测越少，答案计算得越快。
关注点
使用 LINQ 解决这个谜题很有趣，但我花了大约 8 个小时的时间。只用纸解决这个谜题可能会更快一些。
历史
- 修正了 SoMad 突出显示的类型