# Sudoku Solver - Recursive Solve

Any ideas on making my code a bit more clean and efficient? Any criticism is appreciated.

I don't like that I'm calling my lengthy DeepCopy method so many times, but the BinaryFormatter approach is much much slower. I haven't come up with a better approach than doing a deep copy of the entire SudokuBoard due to all of the interwoven pointers, but I'm sure one exists.

Cell

public class Cell
{
public int value { get; private set; }
public bool isBlank { get; set; }
public List<int> possibilities { get; private set; }

public Section row { get; private set; }
public Section column { get; private set; }
public Section region { get; private set; }

public Cell(int v, bool b)
{
value = v;
isBlank = b;

if (!isBlank)
possibilities = new List<int>();
else
possibilities = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
}

public void SetSections(Section r, Section c, Section reg)
{
row = r;
column = c;
region = reg;
}

public void AssignCellValue()
{
// Only continue if cell isn't a preset value
if (isBlank)
{
// If answer found, block cell from use and modify peer region possibilities
if (possibilities.Distinct().Count() == 1)
{
value = possibilities.First();   // Set value to only possibility
possibilities.Clear();
isBlank = false;

row.RefactorPossibilities();     // In peer regions change each cell's possibilities
column.RefactorPossibilities();  //     to reflect value change
region.RefactorPossibilities();

row.SingleOut();
column.SingleOut();
region.SingleOut();
}
}
}

public void ForceCellValue(int value)
{
if (isBlank)
{
possibilities.Clear();
AssignCellValue();
}
}
}


Section

public enum SectionType { ROW, COLUMN, REGION }
public class Section
{
public List<Cell> items;
public SectionType type;

public Section(SectionType t)
{
type = t;
}

public void AssignCells(List<Cell> cells)
{
items = cells;
}

// Step through each cell, if a hardcoded cell is found then retrace
//      the section and remove that possibility from each cell
public void RefactorPossibilities()
{
for (int i = 0; i < items.Count; i++)
{
if (!items[i].isBlank)                          // if cell has a set value
{
for (int j = 0; j < items.Count; j++)       // retrace each cell in region and remove set value
if (items[j].isBlank)                   // from blank cells possibility list
{
if (items[j].possibilities.Count > 1)
{
items[j].possibilities.Remove(items[i].value);
}

if (items[j].possibilities.Distinct().Count() == 1)     // if cell has only 1 possibility value left
{
if (!items.Any(x => x.value == items[j].possibilities.First()))
{
items[j].AssignCellValue();                         // set cell to that value
}
}
}
}
}
}

// Search the section for possibility values occurring once, and if found set it to specified cell
public void SingleOut()
{
for (int i = 0; i < items.Count; i++)
{
int numSpecificPoss = items.OfType<Cell>()
.Where(x => x.isBlank)
.Where(x => x.possibilities.Contains(i + 1))
.Count();

if (numSpecificPoss == 1)
{
Cell SingledOut = items.OfType<Cell>()
.Where(x => x.isBlank)
.Where(x => x.possibilities.Contains(i + 1))
.Single();

//Console.WriteLine("Singled out");
SingledOut.ForceCellValue(i + 1);
}
}
}

public bool SectionVerified()
{
int allValues = items.OfType<Cell>()
.Where(x => x.value > 0)
.Select(x => x.value).ToArray()
.Count();

int distinctValues = items.OfType<Cell>()
.Where(x => x.value > 0)
.Select(x => x.value).ToArray()
.Distinct()
.Count();

if (allValues == distinctValues)
return true;
else
return false;
}
}


SudokuBoard

public class SudokuBoard
{
private Cell[,] board;
private List<Section> rows;
private List<Section> columns;
private List<Section> regions;

public static SudokuBoard DeepCopy(SudokuBoard copy)
{
SudokuBoard other = (SudokuBoard) copy.MemberwiseClone();
other.board = new Cell[9,9];
other.rows = new List<Section>();
other.columns = new List<Section>();
other.regions = new List<Section>();

for (int i = 0; i < 9; i++)
{
other.rows.Add(new Section(SectionType.ROW));                     // initialize each Row
other.columns.Add(new Section(SectionType.COLUMN));                  // initalize each Column
other.regions.Add(new Section(SectionType.REGION));                  // initialize each Region
}

// Initalize each cell with it's preset value and whether or not it's a blank (modifiable) square
for (int i = 0; i < other.board.GetLength(0); i++)
{
for (int j = 0; j < other.board.GetLength(1); j++)
{
if ((copy.board[i, j].value > 0) && (copy.board[i, j].value <= 9))              // if coordinate is a preset cell, set it to value and isBlank false
other.board[i, j] = new Cell(copy.board[i, j].value, false);
else                                                        // else set it to zero and isBlank true
other.board[i, j] = new Cell(0, true);
}
}

//  Assign each row and column it's group of cells
List<Cell> rowCells = new List<Cell>();
List<Cell> colCells = new List<Cell>();
for (int i = 0; i < other.board.GetLength(0); i++)
{
for (int j = 0; j < other.board.GetLength(1); j++)
{
}
other.rows[i].AssignCells(rowCells);          // set each rows cells
other.columns[i].AssignCells(colCells);       // set each columns cells
rowCells = new List<Cell>();           // generate new List after each row as to not delete from memory
colCells = new List<Cell>();           // generate new List after each column as to not delete from memory
}

// Assign each region it's group of cells
List<Cell> regCells = new List<Cell>();
int reg = 0;
for (int i = 0; i < other.board.GetLength(0); i += 3)
{
for (int j = 0; j < other.board.GetLength(1); j += 3)
{
for (int k = i; k < i + 3; k++)
for (int l = j; l < j + 3; l++)

other.regions[reg].AssignCells(regCells);  // set each regions cells
++reg;                              // increment counter for List of regions
regCells = new List<Cell>();        // generate new List after each region as to not delete from memory
}
}

//  Assign each cell their sections
int regNum = 0;
for (int i = 0; i < other.board.GetLength(0); i++)
{
for (int j = 0; j < other.board.GetLength(1); j++)
{
if ((j % 3 == 0) && (j != 0))   // step over one region horizontally every 3 cells
regNum++;

other.board[i, j].SetSections(other.rows[i], other.columns[j], other.regions[regNum]);
}
if (i < 2)                          // bring region back to 0
regNum = 0;
else if (i < 5)                     // bring region back to 3
regNum = 3;
else if (i < 8)                     // bring region back to 6
regNum = 6;
}

other.Refactor();
return other;
}

public SudokuBoard(int[,] presets)
{
if ((presets.GetLength(0) > 9) || (presets.GetLength(1) > 9))
throw new Exception("Error - Sudoku board size too large");
else
{
board = new Cell[9,9];
rows = new List<Section>();
columns = new List<Section>();
regions = new List<Section>();

// Initialize each section
for (int i = 0; i < 9; i++)
{
rows.Add(new Section(SectionType.ROW));                     // initialize each Row
columns.Add(new Section(SectionType.COLUMN));                  // initalize each Column
regions.Add(new Section(SectionType.REGION));                  // initialize each Region
}

// Initalize each cell with it's preset value and whether or not it's a blank (modifiable) square
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if ((presets[i, j] > 0) && (presets[i, j] <= 9))              // if coordinate is a preset cell, set it to value and isBlank false
board[i, j] = new Cell(presets[i, j], false);
else                                                        // else set it to zero and isBlank true
board[i, j] = new Cell(0, true);
}
}

//  Assign each row and column it's group of cells
List<Cell> rowCells = new List<Cell>();
List<Cell> colCells = new List<Cell>();
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
}
rows[i].AssignCells(rowCells);          // set each rows cells
columns[i].AssignCells(colCells);       // set each columns cells
rowCells = new List<Cell>();           // generate new List after each row as to not delete from memory
colCells = new List<Cell>();           // generate new List after each column as to not delete from memory
}

// Assign each region it's group of cells
List<Cell> regCells = new List<Cell>();
int reg = 0;
for (int i = 0; i < board.GetLength(0); i += 3)
{
for (int j = 0; j < board.GetLength(1); j += 3)
{
for (int k = i; k < i + 3; k++)
for (int l = j; l < j + 3; l++)

regions[reg].AssignCells(regCells);  // set each regions cells
++reg;                              // increment counter for List of regions
regCells = new List<Cell>();        // generate new List after each region as to not delete from memory
}
}

//  Assign each cell their sections
int regNum = 0;
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if ((j % 3 == 0) && (j != 0))   // step over one region horizontally every 3 cells
regNum++;

board[i, j].SetSections(rows[i], columns[j], regions[regNum]);
}
if (i < 2)                          // bring region back to 0
regNum = 0;
else if (i < 5)                     // bring region back to 3
regNum = 3;
else if (i < 8)                     // bring region back to 6
regNum = 6;
}
}
}

public List<Cell> GetPossibleGuesses()
{
var guesses = board.OfType<Cell>()
.Where(x => x.isBlank)
.ToList();
return guesses;
}

public Section GetSection(int position, SectionType type)
{
Section section = null;
if (type == SectionType.ROW)
section = rows[position];
else if (type == SectionType.COLUMN)
section = columns[position];
else if (type == SectionType.REGION)
section = regions[position];
return section;
}

public int GetNumberOfBlank()
{
return board.OfType<Cell>().Count(x => x.isBlank);
}

public bool Finished()
{
if( board.OfType<Cell>().All(x => (!x.isBlank) ))
return true;
else
return false;
}

public void Refactor()
{
for (int i = 0; i < 9; i++)             // Initialize each cell's potential values
{
rows[i].RefactorPossibilities();
columns[i].RefactorPossibilities();
regions[i].RefactorPossibilities();
}
}

public void PrintEverything()
{
Console.WriteLine();
int row = 0;

for (int j = 0; j < 9; j++)
{
for(int z = 0; z < 3; z++)
{
for (int k = 0; k < 9; k++)
{
if ((k % 3 == 0) && ( k!= 0))
Console.Write(" █ ");
else if( k!= 0 )
Console.Write(" | ");
for (int l = row; l < row + 3; l++)
{
if (board[j, k].isBlank)
if (board[j, k].possibilities.Contains(l+1))
Console.Write(board[j, k].possibilities.Find(x => x == l+1));
else
Console.Write(" ");
else if (!board[j, k].isBlank)
{
Console.ForegroundColor = ConsoleColor.Green;
if (l == 4)
Console.Write(board[j, k].value);
else
Console.Write(" ");
Console.ForegroundColor = ConsoleColor.White;
}
else
Console.Write(" ");
}
}
if (row == 0)
row = 3;
else if (row == 3)
row = 6;
else if (row == 6)
row = 0;
Console.WriteLine();
}
if (((j+1) % 3 == 0) && j != 8)
Console.WriteLine("▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄");
else if( j != 8)
Console.WriteLine("----+-----+-----█-----+-----+-----█-----+-----+----");

}
}

public bool Solved()
{
int regionSum = 0;
int columnSum = 0;
int rowSum = 0;
bool legitimateSolution = true;

for (int i = 0; i < 9; i++)
{
regionSum = regions[i].items.Sum(x => x.value);
columnSum = columns[i].items.Sum(x => x.value);
rowSum = rows[i].items.Sum(x => x.value);

if ((regionSum != 45) || (columnSum != 45) || (rowSum != 45))
{
legitimateSolution = false;
break;
}
}

if (legitimateSolution)
return true;
else
return false;
}

public bool CurrentlyVerified()
{
for (int i = 0; i < 9; i++)
{
if (!rows[i].SectionVerified())
return false;
else if (!columns[i].SectionVerified())
return false;
else if (!regions[i].SectionVerified())
return false;
}
return true;
}
}


Solve

class Solve
{
SudokuBoard initialBoard;
SudokuBoard currentBoard;
List<Cell> blankCells;
Stopwatch sw;
int solutions;

public Solve(SudokuBoard initial)
{
initialBoard = initial;
solutions = 0;
sw = new Stopwatch();
sw.Start();
}

public void Restart()
{
currentBoard = SudokuBoard.DeepCopy(initialBoard);
blankCells = currentBoard.GetPossibleGuesses();
Start();
}

public void Start()
{
initialBoard.Refactor();
currentBoard = SudokuBoard.DeepCopy(initialBoard);
blankCells = currentBoard.GetPossibleGuesses();

Console.WriteLine("\n\tSolving....");
while (!currentBoard.Solved())
{
int numBlankCells = currentBoard.GetNumberOfBlank();

TrySolving();

// if TrySolving had no effect, brute force all solutions with RecursiveGuess
if (numBlankCells == currentBoard.GetNumberOfBlank())
RecursiveGuess(currentBoard, 0);

if (currentBoard.Finished() && !currentBoard.Solved())
Restart();
}

if (currentBoard.Finished() && currentBoard.Solved())
{
sw.Stop();
Console.Clear();
Console.WriteLine("\n\tElapsed: {0}", sw.Elapsed);
Console.WriteLine("\t{0} SOLUTION'S FOUND", solutions);
currentBoard.PrintEverything();
}
}

public bool TrySolving()
{
for (int i = 0; i < 9; i++)
{
currentBoard.GetSection(i, SectionType.ROW).SingleOut();
currentBoard.GetSection(i, SectionType.COLUMN).SingleOut();
currentBoard.GetSection(i, SectionType.REGION).SingleOut();
}

if (currentBoard.Solved())
return true;
else
return false;
}

public void RecursiveGuess(SudokuBoard previous, int previousGuess)
{
bool blocked = false;
bool fullyBlocked = false;
int currentGuess = 0;
SudokuBoard tempBoard = null;

double seconds = sw.Elapsed.TotalSeconds;

if (seconds % 5 < 0.001)
{
Console.WriteLine("\n\tElapsed: {0}", sw.Elapsed);
Console.WriteLine("\t{0} solutions", solutions);
}

if (previous.CurrentlyVerified())
{
if (!previous.Finished())
{
tempBoard = SudokuBoard.DeepCopy(previous);

blankCells = tempBoard.GetPossibleGuesses();
if (previousGuess != 0)
{
currentGuess = blankCells.First().possibilities.Find(x => x > previousGuess);
if (currentGuess == 0)
fullyBlocked = true;
}
else if (currentGuess < blankCells.First().possibilities.First())
{
currentGuess = blankCells.First().possibilities.First();
}

if (currentGuess != 0)
blankCells.First().ForceCellValue(currentGuess);
else
blocked = true;

if (tempBoard.Finished() && !tempBoard.Solved())
blocked = true;

if (!blocked)
RecursiveGuess(tempBoard, 0);
}
else if (previous.Solved())
{
fullyBlocked = true;

if (!previous.Equals(tempBoard))
currentBoard = SudokuBoard.DeepCopy(previous);

solutions++;
}
}
else
fullyBlocked = true;

if (!fullyBlocked)
RecursiveGuess(previous, currentGuess);
}
}


Main

class Program
{
static void Main(string[] args)
{
int[,] board = new int[9, 9];

board[0, 2] = 2;
board[0, 4] = 3;
board[0, 5] = 6;
board[0, 8] = 5;
board[1, 3] = 9;
board[2, 1] = 6;
board[2, 4] = 2;
board[2, 7] = 4;
board[3, 7] = 1;
board[4, 0] = 1;
board[4, 3] = 5;
board[4, 5] = 7;
board[4, 8] = 6;
board[5, 0] = 3;
board[6, 4] = 6;
board[6, 7] = 8;
board[7, 1] = 1;
board[7, 5] = 2;
board[8, 0] = 6;
board[8, 3] = 4;
board[8, 4] = 1;
board[8, 6] = 2;

SudokuBoard sudokuBoard = new SudokuBoard(board);
sudokuBoard.Refactor();
sudokuBoard.PrintEverything();
Solve solve = new Solve(sudokuBoard);
solve.Start();
}
}


At a really quick glance at the Section.RefactorPossibilities() method I can give you some general suggestions

• be consitent with the style you use. Here the first for loop encloses the body in braces {} but the second loop doesn't.

• your comments here seems pointless, as they aren't commenting on why something is done.

public void RefactorPossibilities()
{
for (int i = 0; i < items.Count; i++)
{
if (!items[i].isBlank)                          // if cell has a set value
{
for (int j = 0; j < items.Count; j++)       // retrace each cell in region and remove set value
if (items[j].isBlank)                   // from blank cells possibility list
{
if (items[j].possibilities.Count > 1)
{
items[j].possibilities.Remove(items[i].value);
}

if (items[j].possibilities.Distinct().Count() == 1)     // if cell has only 1 possibility value left
{
if (!items.Any(x => x.value == items[j].possibilities.First()))
{
items[j].AssignCellValue();                         // set cell to that value
}
}
}
}
}
}


The same method refactored into two methods.

public void RefactorPossibilities()
{
IList<int> values = GetCurrentValues();

for (int i = 0; i < items.Count; i++)
{
if (!items[i].isBlank) { continue; }

foreach (int value in values)
{
items[i].possibilities.Remove(value);
}

if (items[i].possibilities.Distinct().Count() == 1)
{
if (!items.Any(x => x.value == items[i].possibilities.First()))
{
items[i].AssignCellValue();
}
}
}
}
private IList<int> GetCurrentValues()
{
IList<int> values = new List<int>(item.Count);
for (int i = 0; i < items.Count; i++)
{
if (items[i].isBlank) { continue; }
}

return values;
}


The GetCurrentValues() iterates over each item and if the item has a value it will be added to the list. The RefactorPossibilities() method takes these values and if a item doens't have a value it will remove each value from the possibilities.

As you see I have added guard clauses to the loops, to improve readability.

You should consider to add a RemovePosibilities(IList<int> posibilities) to the Cell class. This would simplifiy the RefactorPossibilities() method and has the advantage that you could return a ReadOnlyCollection by the possibilities property of the Cell class.

Section.SingleOut() method

// Search the section for possibility values occurring once, and if found set it to specified cell
public void SingleOut()
{
for (int i = 0; i < items.Count; i++)
{
int numSpecificPoss = items.OfType<Cell>()
.Where(x => x.isBlank)
.Where(x => x.possibilities.Contains(i + 1))
.Count();

if (numSpecificPoss == 1)
{
Cell SingledOut = items.OfType<Cell>()
.Where(x => x.isBlank)
.Where(x => x.possibilities.Contains(i + 1))
.Single();

//Console.WriteLine("Singled out");
SingledOut.ForceCellValue(i + 1);
}
}
}


You can refactor the linq query to

IEnumerable<Cell> cells = items.OfType<Cell>()
.Where(x => x.isBlank)
.Where(x => x.possibilities.Contains(i + 1));

if (cells.Count() == 1)
{
cells.Single().ForceCellValue(i + 1);
}


You can refactor the SectionVerified() method in a similiar way

public bool SectionVerified()
{
IEnumerable<Cell> cells = items.OfType<Cell>()
.Where(x => x.value > 0)
.Select(x => x.value);

return  (cells.Count() == cells.Distinct().Count());
}


SudokuBoard.Solved() method

public bool Solved()
{
int regionSum = 0;
int columnSum = 0;
int rowSum = 0;
bool legitimateSolution = true;

for (int i = 0; i < 9; i++)
{
regionSum = regions[i].items.Sum(x => x.value);
columnSum = columns[i].items.Sum(x => x.value);
rowSum = rows[i].items.Sum(x => x.value);

if ((regionSum != 45) || (columnSum != 45) || (rowSum != 45))
{
legitimateSolution = false;
break;
}
}

if (legitimateSolution)
return true;
else
return false;
}


Issues

• You are using magic numbers here. You should hide them behind a const.
• If regionSum != 45 you won't need to sum columns and rows.

private const int solvedSum = 45;
public bool Solved()
{
for (int i = 0; i < 9; i++)
{
if (regions[i].items.Sum(x => x.value) != solvedSum) { return false; }
if (columns[i].items.Sum(x => x.value) != solvedSum) { return false; }
if (rows[i].items.Sum(x => x.value) != solvedSum) { return false; }
}

return true;
}


Naming

- Properties should use PascalCasing for their names.
- Classes should be named using nouns. So Solve isn't a good name here. A better name would be SudokuSolver

General

• Avoid single letter variable names like public Cell(int v, bool b). Single letters can be used as loop iterators and are usually i,j,k.
• Again, be consitent with the your coding style. At first I thought, ok, for single if and else statements no braces {} are used but they are used for single else if statment. But, after reading more of the code I also found single else if statments without braces and also single if statements using braces.
• Use guard clauses to save horizontal space
• If you throw an exception based on an if condition, you don't need the else like

if ((presets.GetLength(0) > 9) || (presets.GetLength(1) > 9))
throw new Exception("Error - Sudoku board size too large");
else

• A construct like

if (allValues == distinctValues)
return true;
else
return false;


can be simplified by

return (allValues == distinctValues);

• Don't use public fields! Use properties instead.