Sudoku Solver - Recursive Solve

Question

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();
 possibilities.Add(value);
 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++)
 {
 rowCells.Add(other.board[i, j]); // load up all cells in row
 colCells.Add(other.board[j, i]); // load up all cells in column
 }
 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++)
 regCells.Add(other.board[k, l]); // load up all cells in region
 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++)
 {
 rowCells.Add(board[i, j]); // load up all cells in row
 colCells.Add(board[j, i]); // load up all cells in column
 }
 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++)
 regCells.Add(board[k, l]); // load up all cells in region
 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();
 }
}

• Simon Forsberg: Here's a Sudoku Solver using LINQ heavily which you might be able to get some inspiration from: codereview.stackexchange.com/questions/37448/…

Answer 1

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; }
 values.Add(items[i].Value);
 }
 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

Please check the Naming Guidlines.
- 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.