WPF 中的 KenKen 求解器

• 下载源代码 - 185 KB

(需要 .NET 3.5 SP1)

引言

为了不负此行，我编写了我的第一个 WPF 应用程序，使用了新的 Microsoft WPF 工具包中的免费 Microsoft DataGrid（需要 .NET 3.5 SP1），并用它来解决 KenKen 谜题，同时在此过程中也利用了 LINQ 风格的集合和运算符。

下载该应用程序，然后按“测试”查看示例谜题，然后按“计算”进行求解。

背景

KenKen 谜题由一个 6x6 的方格组成，各种单元格被粗线分组。在每个组中，有一个数字和一个基本的算术运算，例如 6+，这意味着所有单元格的总和为 6。 就像数独一样，每个数字 1 到 6 在每一行和每一列中只能出现一次。

KenKen 求解器

KenKen 求解器使用了一种蛮力方法，逐行尝试数字的每种排列，并在发现问题时回溯：要么一个数字出现在另一行的相同位置，要么违反了某个规则。为了提高效率，我按行对规则进行排序，以便可以尽早尝试它们。

要捕获来自网站或报纸的谜题，必须将谜题转换为字母网格以及与每个字母关联的规则。按“测试”查看示例。

基本求解器的工作方式如下

if (!board.Validate())
    throw new Exception("Grid has letter missing from Rules");
AnalyseRules();
CreateRowPermutations();
solution = null;
TryRowSolution(new int[0][]);

创建排列是通过从一个空的“left”列表和 1-6 的“right”列表开始，然后将“right”列表的每个元素连续且递归地附加到“left”列表来实现的。

private void CreateRowPermutations()
{
    Permute(new int[0], new int[] { 1,2,3,4,5,6} );
}

private void Permute(IEnumerable<int> left, IEnumerable<int> right)
{
    if (left.Count() == 6)
    {
        permutations.Add(left.ToArray());
        return;
    }
    for (int i = 0; i < right.Count(); i++)
        Permute( left.Concat(new int[] { right.ElementAt(i)} ), 
                 right.Where((val, index) => index != i).ToArray());
}

类似地，找到解决方案会递归地添加每一行排列，在递归到下一行之前检查每一行是否正确。我使用 All 谓词来检查是否满足每个规则，并使用 Concat 来附加新行。

bool TryRowSolution(int[][] rows)
{
    if (rows.Count() == 6) //bottom-out 
    {
        solution = rows.ToArray();
        return true;
    }
    int newrow = rows.Count();
    foreach (int[] permute in permutations)
    {
      if (IsValid(rows, permute)) //check new row is consistent 
      {
          int[][] newgrid = rows.Concat(new int[][] { permute }).ToArray();
          if (rulesByRow[rows.Count()].All(r => 
                          r.Eval(board, newgrid.ToArray())))
          //test each rule 
             if (TryRowSolution(newgrid))
                return true;
      }
    }
    return false; 
}

WPF

Microsoft DataGrid 允许极其简单的双向绑定到内存数据结构，例如任何类的列表，甚至可以自动创建列以匹配类的公共属性（注意：不是成员）。

rules = new ObservableCollection<Rule>(solver.board.rules); 
RulesGrid.ItemsSource = rules;

通过在 XAML 中设置适当的属性，它甚至可以向列表中添加新元素（注意：检查你的对象是否有默认构造函数）。

<my:DataGrid Name="RulesGrid" 
    xmlns:my="clr-namespace:Microsoft.Windows.Controls;assembly=WPFToolkit" 
    CanUserAddRows="True" CanUserDeleteRows="True" 
    Margin="40,0,0,0" HorizontalAlignment="Right"> 

就这样了……尽情享受解决你的 KenKen 谜题吧。