简单的 LINQ 数独求解器

• 下载源代码 - 7.18 KB

引言

这是一个使用 LINQ 解决数独网格的简单解决方案。您可以从上面的链接下载使用此方法的 WinForm 示例。

它在不到 1 秒的时间内解决了所有我测试过的网格。

使用代码

求解器接收一个整数列表，并以相同类型返回解决方案。

private List<int> solver(List<int> _cells)
{
  var emptyCell = _cells.Select((val, index) => 
      new { index, val }).FirstOrDefault(cell => cell.val == 0);
  if (emptyCell == null)
    return _cells;
  List<int> grid = new List<int>(_cells);

  foreach (int trying in Enumerable.Range(1, 9).Except(_cells.Where((val, index) => 
               sameRowColBox(index,emptyCell.index)).Distinct()))
  {
    grid[emptyCell.index] = trying;
    if ((_cells = solver(grid)) != null)
      return _cells;
  }
  return null;
}

简而言之，该函数获取一个空单元格，尝试用正确的值填充它，并使用这个新的网格递归调用求解器。

当找到正确填充的网格时，或者当所有可能性都被探索完毕时，递归停止。

if (emptyCell == null)
    return _cells;

选择当前网格中的第一个空单元格，并借助 Enumerable.Select 方法获取其索引。

var emptyCell = _cells.Select((val, index) => 
        new { index, val }).FirstOrDefault(cell => cell.val == 0); 

获取此单元格的所有可能值。

Enumerable.Range(1, 9).Except(_cells.Where((val, index) => 
       sameRowColBox(index,emptyCell.index)).Distinct())

此函数测试两个索引是否“冲突”：相同的行；列或 3x3 框。

private bool sameRowColBox(int i, int j){
  return (i / 9 == j / 9) || (i % 9 == j % 9) || (((i % 9) / 
            3 + (i / 9) / 3 * 3) == ((j % 9) / 3 + (j / 9) / 3 * 3));
}

然后，对于每个可能的值，填充空单元格并再次调用求解器。

grid[emptyCell.index] = trying;
if ((_cells = solver(grid)).Count > 0 )
  return _cells;