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();
    }
}

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.