Sudoku.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SudokuSolver
{
    class Program
    {
        public static Grid Sudoku = new Grid();

        static void Main(string[] args)
        {
            string[] Lines = new string[9]
            {
                "800000000",
                "003600000",
                "070090200",
                "050007000",
                "000045700",
                "000100030",
                "001000068",
                "008500010",
                "090000400"
            };

            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                    if (Lines[i][j] != '0')
                        Sudoku[i, j] = int.Parse(Lines[i][j].ToString());

            long startTime = Environment.TickCount;

            // For simple sudoku.
            /*
            Sudoku.UpdateValues();

            if (Sudoku.SolvedCount == 81)
                Console.Write(Sudoku.ToString());
            else
            */
            Resolve(Sudoku.GetNextPosition(), Sudoku);

            Console.WriteLine();
            Console.Write("Elapsed time: {0}ms", Environment.TickCount - startTime);

            Console.ReadLine();
        }

        static bool Resolve(Grid.Position position, Grid state)
        {
            int x = position.X, y = position.Y;
            Grid stateCopy = new Grid(state);
            List<int> possibilities = stateCopy.Possibilities[x, y];
            for (int i = 0; i < possibilities.Count; i++)
            {
                state[x, y] = possibilities[i];
                state.UpdateValues();

                if (state.SolvedCount == 81)
                {
                    Console.Write(state.ToString());
                    return true;

                    // All answers.
                    /*
                    state = new Grid(stateCopy);
                    continue;
                    */
                }

                Grid.Position nextPosition = state.GetNextPosition();
                if (nextPosition != null && Resolve(nextPosition, state))
                    return true;
                state = new Grid(stateCopy);
            }
            return false;
        }
    }

    class Grid : ICloneable
    {
        public static List<int> Numbers = new List<int>();

        int[,] values = new int[9, 9];
        void setValue(int x, int y, int value)
        {
            values[x, y] = value;

            for (int i = 0; i < 9; i++)
            {
                if (i != y)
                    Possibilities[x, i].Remove(value);
                if (i != x)
                    Possibilities[i, y].Remove(value);
            }
            int rectX = x / 3 * 3, rectY = y / 3 * 3;
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                    Possibilities[rectX + i, rectY + j].Remove(value);

            SolvedCount++;
        }
        public void UpdateValues()
        {
            bool changed;
            do
            {
                changed = false;
                for (int i = 0; i < 9; i++)
                    for (int j = 0; j < 9; j++)
                        if (values[i, j] == 0 && Possibilities[i, j].Count == 1)
                        {
                            setValue(i, j, Possibilities[i, j][0]);
                            changed = true;
                        }
            }
            while (changed);
        }
        public int this[int x, int y]
        {
            get { return values[x, y]; }
            set { setValue(x, y, value); }
        }

        public List<int>[,] Possibilities = new List<int>[9, 9];

        public class Position
        {
            public int X, Y;
            public override string ToString()
            {
                return string.Format("({0}, {1})", X, Y);
            }
        }

        public Position GetNextPosition()
        {
            int x = 0, y = 0;
            int nextCount = 10;
            int currentCount;
            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                {
                    if (values[i, j] == 0)
                    {
                        currentCount = Possibilities[i, j].Count;
                        if (currentCount == 0)
                            return null;
                        if (currentCount < nextCount)
                        {
                            nextCount = currentCount;
                            x = i;
                            y = j;
                        }
                    }
                }
            return new Position() { X = x, Y = y };
        }

        public int SolvedCount = 0;

        public Grid()
        {
            Numbers = new List<int>();
            for (int i = 1; i < 10; i++)
                Numbers.Add(i);

            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                    Possibilities[i, j] = new List<int>(Numbers);
        }
        public Grid(Grid another)
        {
            values = (int[,])another.values.Clone();

            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                    Possibilities[i, j] = new List<int>(another.Possibilities[i, j]);

            SolvedCount = another.SolvedCount;
        }

        public object Clone()
        {
            return new Grid(this);
        }

        public override string ToString()
        {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < 9; i++)
            {
                builder.AppendLine();
                for (int j = 0; j < 9; j++)
                {
                    builder.Append(values[i, j]);
                    builder.Append(" ");
                }
            }
            builder.AppendLine();
            builder.Append(SolvedCount);
            return builder.ToString();
        }
    }
}

喵喵><