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

Here's a Sudoku Solver using LINQ heavily which you might be able to get some inspiration from: codereview.stackexchange.com/questions/37448/… — Simon Forsberg♦, Nov 11 '14 at 19:27

Heslacher · Accepted Answer · 2014-11-11 10:24:50Z

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.

asked	4 years, 7 months ago
viewed	1,731 times
active	4 years, 7 months ago

Stack Exchange Network

current community

your communities

more stack exchange communities

Sudoku Solver - Recursive Solve

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged c# linq sudoku or ask your own question.

Linked

Hot Network Questions

Sudoku Solver - Recursive Solve

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c# linq sudoku or ask your own question.

Linked

Related

Hot Network Questions