Simple Linq Sudoku Solver

• Download LinqSudokuSolver - 7.18 KB

Introduction

A simple solution to resolve a Sudoku Grid, using Linq.

You can download a winform example using this method

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

Using the code 

The solver take a list of integer, and return the solution in 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 take an empty cell, try 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 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 test 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, foreach possible value, fills the empty cell and recall the solver.

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

History

You must Sign In to use this message board.

FAQ  Noise Tolerance Very HighHighMediumLowVery Low  Search Messages    Layout Expand All MessagesThread ViewNo Javascript (slow)No Javascript Preview    Per page 102550

Msgs 1 to 4 of 4 (Total in Forum: 4) (Refresh) FirstPrevNext

Brute force solution bearskin 15:09 8 Sep '08   This code does a brute force solution. It essentially tries every combination in the solution space. It's a good demonstration of Linq code but not a good sudoku solver. For example, try it on this problem: 3...8.... ...7....5 1........ ......36. ..2..4... .7....... ....6.13. .452..... ......8.. I got that problem here. Sign In·View Thread·PermaLink Simplification bearskin 14:49 8 Sep '08   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. Sign In·View Thread·PermaLink Awesome merlin981 7:07 5 Sep '08   Excellent use of LINQ and recursion. Great job. 5 from me ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ LINQ Exchange - Learn about LINQ and Lambda Expressions Web SEO Specialists - The SEO Expert Joke of the Day and Random Jokes - ReallyFunnyQuickJokes.com ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Sign In·View Thread·PermaLink Cool! Rob Philpott 2:49 5 Sep '08   Quite an achievement to solve the puzzle in a single function like that. Ah, LINQ. It's still looks a bit strange to me but you've got to love it... Regards, Rob Philpott. Sign In·View Thread·PermaLink

Last Visit: Thursday, November 20, 2008 2:42 AM     Last Update:Thursday, November 20, 2008 2:42 AM