|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Announcements
Chapters
Services
Feature Zones
|
Note: This is an unedited contribution. If this article is inappropriate,
needs attention or copies someone else's work without reference then please
Report This Article
IntroductionA 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 codeThe 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
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||