.NET > Algorithm >> Algorithm in CSharp Views : 2161
Rate This Article :

Sudoku Solver in CSharp

The below program will solve Low, Medium and some of the difficult Sudoku puzzle. I am still working on this to make this code to solve any types of Sudoku puzzles. Experience it by testing your puzzle, Go through the code and leave your comments to improve it.

Steps to Test/Execute the code:

1.       Input your puzzle in the “ProblemArray” property.

2.       Input “0” in the empty cell.

namespace Sudoku

{

    public class SolveSudoku

    {

        static void Main(string[] args)

        {

            var sudokuSolver = new SudokuSolver(ProblemArray);

            sudokuSolver.Solve();

            Console.ReadLine();

        }

 

        protected static int[] ProblemArray

        {

            get

            {

                ////== Low Grade

                //return new int[] {

                //                      0, 7, 1, 0, 9, 0, 8, 0, 0,

                //                      0, 0, 0, 3, 0, 6, 0, 0, 0,

                //                      4, 9, 0, 0, 0, 0, 7, 0, 5,

                //                      0, 1, 0, 9, 0, 0, 0, 0, 0,

                //                      9, 0, 2, 0, 0, 0, 6, 0, 3,

                //                      0, 0, 0, 0, 0, 8, 0, 2, 0,

                //                      8, 0, 5, 0, 0, 0, 0, 7, 6,

                //                      0, 0, 0, 6, 0, 7, 0, 0, 0,

                //                      0, 0, 7, 0, 4, 0, 3, 5, 0

                //          };

 

 

                ////== Medium Grade

                //return new int[] {

                //                      0, 0, 0, 0, 4, 0, 0, 0, 0,

                //                      0, 4, 1, 0, 0, 0, 8, 5, 0,

                //                      5, 0, 0, 1, 8, 2, 0, 0, 6,

                //                      6, 8, 0, 0, 0, 7, 0, 4, 5,

                //                      0, 0, 0, 0, 0, 0, 0, 0, 0,

                //                      1, 5, 0, 4, 0, 0, 0, 6, 8,

                //                      4, 0, 0, 3, 6, 8, 0, 0, 2,

                //                      0, 1, 2, 0, 0, 0, 6, 9, 0,

                //                      0, 0, 0, 0, 9, 0, 0, 0, 0,

                //          };

 

                //== Difficult Grade

                return new int[] {

                                      0, 1, 8, 0, 2, 0, 0, 0, 0,

                                      0, 6, 5, 1, 4, 0, 8, 0, 2,

                                      0, 0, 0, 0, 0, 6, 5, 0, 1,

                                      0, 0, 3, 0, 7, 0, 9, 1, 6,

                                      0, 0, 0, 0, 0, 0, 0, 0, 0,

                                      1, 5, 2, 0, 6, 0, 3, 0, 0,

                                      7, 0, 6, 4, 0, 0, 0, 0, 0,

                                      3, 0, 1, 0, 5, 9, 2, 7, 0,

                                      0, 0, 0, 0, 8, 0, 6, 9, 0

                          };

            }

        }

    }

}

 

namespace Sudoku

{

    using System;

    using System.Collections.Generic;

    using System.Linq;

    using System.Text;

 

    public class SudokuSolver : SudokuSource

    {

        public SudokuSolver(int[] ProblemArray)

        {

            FillSudokuGrid(ProblemArray);

 

            Console.WriteLine("====== Source Sudoku ======");

            WriteSudokuGrid();

        }

 

        public void Solve()

        {

            int previousValue;

            int currentValue;

 

            Func<int> SumOfSudokuValue = () => SourceArray.Sum(t => t.Sum());

            do

            {

                previousValue = SumOfSudokuValue();

                SolveArray();

                currentValue = SumOfSudokuValue();

            }

            while (previousValue != currentValue);

 

            Console.WriteLine("====== Solved Sudoku ======");

            WriteSudokuGrid();

        }

 

        private void SolveArray()

        {

            var list = new List<int>();

 

            for (var row = 0; row < SourceArray.Length; row++)

            {

                for (var column = 0; column < SourceArray.Length; column++)

                {

                    var currentValue = SourceArray[row][column];

 

                    if (currentValue > 0)

                        continue;

 

                    list.Clear();

 

                    for (var i = 1; i <= 9; i++)

                    {

                        if (CheckCurrentFullRow(row, column, i))

                        {

                            if (CheckCurrentFullColumn(row, column, i))

                            {

                                if (CheckCurrentFullSquare(row, column, i))

                                    list.Add(i);

                            }

                        }

                    }

 

                    if (list.Count() == 1)

                    {

                        SourceArray[row][column] = list[0];

                    }

                    else if (list.Count() > 1)

                    {

                        var posValue = CheckNeighbourValue(row, column, list);

                        if (posValue > 0) SourceArray[row][column] = posValue;

 

                    }

                }

            }

        }

 

        //Check Row contains the Assigning Value

        private bool CheckCurrentFullRow(int Row, int Column, int AssignValue)

        {

            for (var i = 0; i <= 8; i++)

            {

                if (SourceArray[Row][i] == AssignValue && Column != i)

                    return false;

            }

            return true;

        }

        //Check Column contains the Assigning value.

        private bool CheckCurrentFullColumn(int Row, int Column, int AssignValue)

        {

            for (var i = 0; i <= 8; i++)

            {

                if (SourceArray[i][Column] == AssignValue && i != Row)

                    return false;

            }

            return true;

        }

        //Check Square Contains the Assigning Value.

        private bool CheckCurrentFullSquare(int Row, int Column, int AssignValue)

        {

            var rowStart = (Row / 3) + 1;

            var rowIndexEnd = (rowStart * 3) - 1;

            if (rowIndexEnd == 0) rowIndexEnd = 3;

            var rowIndexStart = rowIndexEnd - 2;

            var columnStart = (Column / 3) + 1;

            var columnIndexEnd = (columnStart * 3) - 1;

            if (columnIndexEnd == 0) columnIndexEnd = 3;

            var columnIndexStart = columnIndexEnd - 2;

            for (var curRow = rowIndexStart; curRow <= rowIndexEnd; curRow++)

            {

                for (var curColumn = columnIndexStart; curColumn <= columnIndexEnd; curColumn++)

                {

                    if (SourceArray[curRow][curColumn] == AssignValue && curColumn != Column && curRow != Row)

                        return false;

                }

            }

            return true;

        }

        private int CheckNeighbourValue(int CurrentRow, int CurrentColumn, List<int> PossibleIntList)

        {

            var rowStart = (CurrentRow / 3) + 1;

            var rowIndexEnd = (rowStart * 3) - 1;

            if (rowIndexEnd == 0) rowIndexEnd = 3;

            var rowIndexStart = rowIndexEnd - 2;

 

            var columnStart = (CurrentColumn / 3) + 1;

            var columnIndexEnd = (columnStart * 3) - 1;

            if (columnIndexEnd == 0) columnIndexEnd = 3;

            var columnIndexStart = columnIndexEnd - 2;

 

            var applicableRows = new List<int>();

            var currentSquareRows = new List<int>();

            for (var curRow = rowIndexStart; curRow <= rowIndexEnd; curRow++)

            {

                currentSquareRows.Add(curRow);

                if (CurrentRow != curRow)

                {

                    applicableRows.Add(curRow);

                }

            }

            var applicableColumns = new List<int>();

            var currentSquareColumns = new List<int>();

            for (var curColumn = columnIndexStart; curColumn <= columnIndexEnd; curColumn++)

            {

                currentSquareColumns.Add(curColumn);

                if (CurrentColumn != curColumn)

                {

                    applicableColumns.Add(curColumn);

                }

            }

            var resultArray = new List<int>();

            for (int i = 0; i < PossibleIntList.Count(); i++)

            {

                var assignValue = PossibleIntList[i];

                var newIntArray = NewArray;

                //Copy all values from exisiting array

                for (var curRow = rowIndexStart; curRow <= rowIndexEnd; curRow++)

                {

                    for (var curColumn = columnIndexStart; curColumn <= columnIndexEnd; curColumn++)

                    {

                        if (curRow == CurrentRow && curColumn == CurrentColumn)

                            continue;

                        newIntArray[curRow][curColumn] = SourceArray[curRow][curColumn];

                    }

                }

                foreach (var applicableColumn in applicableColumns)

                {

                    for (int row = 0; row <= 8; row++)

                    {

                        if (SourceArray[row][applicableColumn] == assignValue && !currentSquareRows.Contains(row))

                        {

                            if (newIntArray[CurrentRow][applicableColumn] == 0)

                                newIntArray[CurrentRow][applicableColumn] = assignValue;

 

                            foreach (var applicableRow in applicableRows)

                            {

                                if (newIntArray[applicableRow][applicableColumn] == 0)

                                    newIntArray[applicableRow][applicableColumn] = assignValue;

                            }

                            break;

                        }

                    }

                }

                foreach (var applicableRow in applicableRows)

                {

                    for (int column = 0; column <= 8; column++)

                    {

                        if (SourceArray[applicableRow][column] == assignValue && !currentSquareColumns.Contains(column))

                        {

                            if (newIntArray[applicableRow][CurrentColumn] == 0)

                                newIntArray[applicableRow][CurrentColumn] = assignValue;

 

                            foreach (var applicableColumn in applicableColumns)

                            {

                                if (newIntArray[applicableRow][applicableColumn] == 0)

                                    newIntArray[applicableRow][applicableColumn] = assignValue;

                            }

                            break;

                        }

                    }

                }

                //Check all square having values.

                var allHavingValues = true;

                newIntArray[CurrentRow][CurrentColumn] = -1;

                for (var curRow = rowIndexStart; curRow <= rowIndexEnd; curRow++)

                {

                    for (var curColumn = columnIndexStart; curColumn <= columnIndexEnd; curColumn++)

                    {

                        if (newIntArray[curRow][curColumn] == 0)

                        {

                            allHavingValues = false;

                        }

                    }

                }

                if (allHavingValues)

                {

                    resultArray.Add(assignValue);

                }

            }

            var possibleValue = 0;

            if (resultArray.Count() == 1)

                possibleValue = resultArray[0]; 

            return possibleValue;

        }

        private void WriteSudokuGrid()

        {

            var objString = new StringBuilder();

            foreach (var t in SourceArray)

            {

                for (var j = 0; j < SourceArray.Length; j++)

                {

                    objString.Append(t[j] + " ");

                }

                objString.Append("\n");

            }

            Console.WriteLine(objString.ToString());

        }

    }

    public abstract class SudokuSource

    {

        protected int[][] SourceArray { get; set; }

        protected void FillSudokuGrid(int[] ProblemArray)

        {

            SourceArray = new int[9][];//Row Declaration.          

            for (var i = 0; i < SourceArray.Length; i++)

            {

                SourceArray[i] = new int[9];//Column Declaration

            }

            Func<int, int, int> FindCurrentCell = (Row, Column) => (Row * 9) + Column;

            //Push the values into the array.

            for (var i = 0; i < SourceArray.Length; i++)

            {

                for (var j = 0; j < SourceArray.Length; j++)

                {

                    SourceArray[i][j] = ProblemArray[FindCurrentCell(i, j)];

                }

            }

        }

        protected int[][] NewArray

        {

            get

            {

                var newArrray = new int[9][];

                for (var i = 0; i < newArrray.Length; i++)

                {

                    newArrray[i] = new int[9];

                }

                foreach (var t in newArrray)

                {

                    for (var j = 0; j < newArrray.Length; j++)

                    {

                        t[j] = 0;

                    }

                }

                return newArrray;

            }

        }

    }

}

Program Output:

SudokuSolverInCSharp.JPG

About Author
Raj Kumar
Total Posts 31
Developer in .Net!
Comment this article
Name*
Email Address* (Will not be shown on this website.)
Comments*
Enter Image Text*
   
View All Comments
Prathyusha Dwibhashi
Omg..Great work..Thanks Raj.I'm not sure how many days it will take for me to understand this.Thanks a ton.. :)
Murali
Great gob Raj.
SENTHAMILSELVAN
Raj.... Really Superb.. Great work
Praveen Kumar V C
Great work. keep introducing us the many more solved algorthim
Karthik
Good work..Its working. Trying to understand this code.. Thanks..
  Privacy   Terms Of Use   Advertise With Us   Contact Us
© 2016 Developerin.Net. All rights reserved.
Trademarks and Article Images mentioned in this site may belongs to Microsoft and other respective trademark owners.
Articles, Tutorials and all other content offered here is for educational purpose only and its author copyrights.