Click here to Skip to main content
15,867,594 members
Articles / Programming Languages / C#

Simple LINQ Sudoku Solver

Rate me:
Please Sign up or sign in to vote.
4.88/5 (30 votes)
4 Sep 2008CPOL 47.2K   816   39   7
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.

sudoku.png

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.

C#
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:

C#
if (emptyCell == null)
    return _cells;

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

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

Take all the possible values for this cell:

C#
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.

C#
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.

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Junior)
France France
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 5 Pin
Anurag Gandhi13-Dec-11 20:05
professionalAnurag Gandhi13-Dec-11 20:05 
GeneralMy vote of 5 Pin
thatraja18-Jan-11 5:00
professionalthatraja18-Jan-11 5:00 
GeneralBrute force solution Pin
bearskin8-Sep-08 14:09
bearskin8-Sep-08 14:09 
GeneralSimplification Pin
bearskin8-Sep-08 13:49
bearskin8-Sep-08 13:49 
GeneralRe: Simplification Pin
Philippe Mori21-Aug-14 16:08
Philippe Mori21-Aug-14 16:08 
GeneralAwesome Pin
merlin9815-Sep-08 6:07
professionalmerlin9815-Sep-08 6:07 
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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

GeneralCool! Pin
Rob Philpott5-Sep-08 1:49
Rob Philpott5-Sep-08 1:49 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.