Click here to Skip to main content
13,191,877 members (32,623 online)
Click here to Skip to main content
Add your own
alternative version


38 bookmarked
Posted 4 Sep 2008

Simple LINQ Sudoku Solver

, 4 Sep 2008
Rate this:
Please Sign up or sign in to vote.
A simple way to resolve a Sudoku grid, in 10 lines of code.


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) => 
    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) => 

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;


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


About the Author

Mickael Magniez
Software Developer (Junior)
France France
No Biography provided

You may also be interested in...

Comments and Discussions

GeneralMy vote of 5 Pin
Anurag Gandhi13-Dec-11 20:05
memberAnurag Gandhi13-Dec-11 20:05 
GeneralMy vote of 5 Pin
thatraja18-Jan-11 5:00
mvpthatraja18-Jan-11 5:00 
GeneralBrute force solution Pin
bearskin8-Sep-08 14:09
memberbearskin8-Sep-08 14:09 
GeneralSimplification Pin
bearskin8-Sep-08 13:49
memberbearskin8-Sep-08 13:49 
GeneralRe: Simplification Pin
Philippe Mori21-Aug-14 16:08
memberPhilippe Mori21-Aug-14 16:08 
GeneralAwesome Pin
merlin9815-Sep-08 6:07
membermerlin9815-Sep-08 6:07 
GeneralCool! Pin
Rob Philpott5-Sep-08 1:49
memberRob 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.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.171017.2 | Last Updated 5 Sep 2008
Article Copyright 2008 by Mickael Magniez
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid