Sudoku Solver by Razali

using System;
using System.Collections.Generic;

namespace Sudoku_Solver
{
    public  class Constraint
    {
        public Constraint(int row, int col, List<int> possibleValues)
        {
            Row = row;
            Column = col;
            PossibleValues = possibleValues;
        }
        public int Row { get; set;}
        public int Column { get; set;}

        public List<int> PossibleValues { get; set; }

        public int Count() { return PossibleValues.Count;}

    }

    static class Program
    {
        #region Variables
        //Hard Difficulty Sudoku Puzzle
        private static int[,] grid = new int[,]{
                {0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,3,0,8,5},
                {0,0,1,0,2,0,0,0,0},
                {0,0,0,5,0,7,0,0,0},
                {0,0,4,0,0,0,1,0,0},
                {0,9,0,0,0,0,0,0,0},
                {5,0,0,0,0,0,0,7,3},
                {0,0,2,0,1,0,0,0,0},
                {0,0,0,0,4,0,0,0,9}
            };



        private static List<Constraint> constraints;

        #endregion


        static void Main(string[] args)
        {
            Console.WriteLine("Solving Sudoku...");
            DateTime start = DateTime.UtcNow;

            GetConstraints();
            SolveSudokuGrid(0);

            DateTime end = DateTime.UtcNow;

            DisplayGrid();

            Console.WriteLine("\nTook a total of " + end.Subtract(start).TotalSeconds.ToString() + " seconds to solve");
            Console.Read();

        }


        #region Methods
        private static bool SolveSudokuGrid(int constraintIndex)
        {

            if (IsGameOver() == true)
                return true;

            //Get constraint
            Constraint constraint = constraints[constraintIndex];


            for (int i = 0; i < constraint.Count(); i++)
            {
                if (HasConflicts(constraint.Row, constraint.Column, constraint.PossibleValues[i]))
                    continue;
                //Assume correct number by adding a constraint
                grid[constraint.Row, constraint.Column] = constraint.PossibleValues[i];

                if (SolveSudokuGrid(constraintIndex + 1) == true)
                    return true;

                //Cant solve. Backtrack
                grid[constraint.Row, constraint.Column] = 0;
            }

            return false;
        }


        private static void DisplayGrid()
        {
            Console.WriteLine("-------------------------");
            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    if (col == 0 || col % 3 == 0)
                        Console.Write("| ");

                    if (grid[row,col] == 0)
                        Console.Write("- ");
                    else
                        Console.Write(grid[row,col] +" ");
                }
                Console.WriteLine("|");

                if ((row + 1) % 3 == 0 && row != 0)
                    Console.WriteLine("-------------------------");
            }

        }


        /// <summary>
        /// Determines if sudoku is solved by finding for
        /// '0' zeroes in the grid
        /// </summary>
        /// <returns>
        /// True if Sudoku is solved
        /// False otherwise
        /// </returns>
        private static bool IsGameOver()
        {
            for(int r = 0; r < 9; r++)
               for(int c = 0; c < 9; c++)
                 if (grid[r, c] == 0)
                    return false;

            return true;
        }

        /// <summary>
        /// Determines all valid values that can be put
        /// into the unfilled squares
        /// </summary>
        private static void GetConstraints()
        {
            constraints = new List<Constraint>();

            for(int row = 0; row < 9; row++)
                for(int col = 0; col < 9; col++)
                    if(grid[row,col] == 0)
                        constraints.Add(ComputeConstraint(row, col));

            constraints.Sort(delegate(Constraint c1, Constraint c2) { return c1.Count().CompareTo(c2.Count()); });
        }

        /// <summary>
        /// Given an unsolved square in a puzzle,
        /// determines all possible valid values
        /// from 1 to 9
        /// </summary>
        /// <param name="row">Row of square</param>
        /// <param name="col">Col of square</param>
        /// <returns>List of valid values</returns>


        private static Constraint ComputeConstraint(int row, int col)
        {
            List<int> possibleValues = new List<int>();

            for (int i = 1; i <= 9; i++)
                if (HasConflicts(row, col, i) == false)
                    possibleValues.Add(i);

            Constraint constraint = new Constraint(row, col, possibleValues);
            return constraint;
        }


        private static bool usedInRow(int row, int num)
        {
            /*
            * Scans through that "row" till a match is found.
            */
            for (int col = 0; col < 9; col++)
                if (grid[row,col] == num)
                   return true;

            return false;
        }

        private static bool usedInCol(int col, int num)
        {
            /*
            * Scans through that "col" till a match is found.
            */
            for (int row = 0; row < 9; row++)
               if (grid[row,col] == num)
                   return true;

            return false;
        }

        private static bool usedInBox(int boxStartRow, int boxStartCol, int num)
        {
            /*
            * Scans through the mini 3x3 box, looking for a duplicate number
            */
            for (int row = boxStartRow; row < boxStartRow + 3; row++)
                  for (int col = boxStartCol; col < boxStartCol + 3; col++)
                     if (grid[row,col] == num)
                        return true;

            return false;
        }

        private static bool HasConflicts(int row, int col, int num)
        {
            int startRow = (row / 3) * 3;
            int startCol = (col / 3) * 3;


            return (usedInRow(row, num) || usedInCol(col, num) || usedInBox(startRow, startCol, num));
        }

        #endregion
    }
}