Click here to Skip to main content
Click here to Skip to main content

Simple LINQ Sudoku Solver

, 5 Sep 2008 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

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;

License

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

Share

About the Author

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

Comments and Discussions

 
GeneralMy vote of 5 PinmemberAnurag Gandhi13-Dec-11 21:05 
GeneralMy vote of 5 Pinmvpthatraja18-Jan-11 6:00 
GeneralBrute force solution Pinmemberbearskin8-Sep-08 15:09 
GeneralSimplification Pinmemberbearskin8-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.
GeneralRe: Simplification PinmemberPhilippe Mori21-Aug-14 17:08 
GeneralAwesome Pinmembermerlin9815-Sep-08 7:07 
GeneralCool! PinmemberRob Philpott5-Sep-08 2:49 

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

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

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