12,696,092 members (30,715 online)
alternative version

33K views
38 bookmarked
Posted

# Simple LINQ Sudoku Solver

, 5 Sep 2008 CPOL
 Rate this:
A simple way to resolve a Sudoku grid, in 10 lines of code.

## 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;```

## Share

 Software Developer (Junior) France
No Biography provided

## You may also be interested in...

 First Prev Next
 My vote of 5 Anurag Gandhi13-Dec-11 21:05 Anurag Gandhi 13-Dec-11 21:05
 My vote of 5 thatraja18-Jan-11 6:00 thatraja 18-Jan-11 6:00
 Brute force solution bearskin8-Sep-08 15:09 bearskin 8-Sep-08 15:09
 Simplification bearskin8-Sep-08 14:49 bearskin 8-Sep-08 14:49
 I'd change this code:```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)); }```To this:```private bool sameRowColBox(int i, int j){ int irow = i / 9, icol = i % 9; int jrow = j / 9, jcol = j % 9; return (irow == jrow) || (icol == jcol) || (boxNum(irow, icol) == boxNum(jrow, jcol)); }```And implement boxNum() as either:```private int boxNum (int row, int col) { return col / 3 + row / 3 * 3; }```or:```private int boxNum (int row, int col) { int [] colBox = {0,0,0, 1,1,1, 2,2,2}; int [] rowBox = {0,0,0, 3,3,3, 6,6,6}; return rowBox[row] + colBox[col]; }```The intent is a bit clearer.
 Re: Simplification Philippe Mori21-Aug-14 17:08 Philippe Mori 21-Aug-14 17:08
 Awesome merlin9815-Sep-08 7:07 merlin981 5-Sep-08 7:07
 Cool! Rob Philpott5-Sep-08 2:49 Rob Philpott 5-Sep-08 2:49
 Last Visit: 31-Dec-99 19:00     Last Update: 19-Jan-17 19:55 Refresh 1