Simple LINQ Sudoku Solver

• Download source code - 7.18 KB

Introduction

This is a simple solution to resolve a Sudoku Grid, using LINQ. You can download a WinForm example that uses this method from the above link.

It solves all grids I tested in less than 1 second.

Using the code

The solver takes a list of integers, and returns the solution in the same type.

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;
}

Briefly, the function takes an empty cell, tries to fill it with a correct value, and recursively calls the solver with this new grid.

The recursion stops when a correctly filled grid is found, or when all possibilities have been explored:

if (emptyCell == null)
    return _cells;

Choose the first empty cell in the current grid, and get its index, thanks to the Enumerable.Select method:

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

Take all the possible values for this cell:

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

This function tests if two indexes are 'in conflict": same row; column, or 3*3 box.

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));
}

And then, for each possible value, fills the empty cell and recalls the solver.

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