mysolver.cs

Sudoku as a CSP: Using algorithms and techniques from CSP to solve an NxN Sudoku puzzle.

using System;
using System.Collections.Generic;
using System.Text;

namespace MySudoku
{
    class MySolver
    {
        #region Delegates Defenitions ... 
        public delegate MyCell[,] AssignType(MyCell[,] branch, Pos p, char v);

        public delegate MyCell[,] EliminateType(MyCell[,] branch, Pos p, char v);

        public delegate char ValueHeuristics(MyCell[,] branch, Pos p);

        public delegate Pos VarHeuristics(MyCell[,] branch);
        #endregion

        #region delegates Variables ...  ( for BT-Search.)
        VarHeuristics SelectUnassignedVariable;

        ValueHeuristics SelectDomainValue;

        AssignType Assign;

        EliminateType Eliminate;
        #endregion

        #region class members ...
        private int m_gridSize ;
        private string m_MaxDomain="";
        private int m_NumOfBacktracking = 0;
        private TimeSpan m_duration;
        #endregion

        #region Properties ...
        public int NumOfBacktracking
        {
            get
            {
                return m_NumOfBacktracking;
            }
        }
        public TimeSpan Duration
        {
            get
            {
                return m_duration;
            }
        }
        #endregion

        #region Constractor ...
        /// <summary>
        /// Initializes a new instance of the <see cref="MySolver"/> class.
        /// </summary>
        /// <param name="size">The size.</param>
        /// <param name="start">The start.</param>
        public MySolver(int size, StartingInfo start)
        {
           m_gridSize = size ;
           SetMaxDomain();

           SetSolvingConditions(start);
        }

        /// <summary>
        /// Sets the solving conditions.
        /// here we set the delegates to be  none\fc\ac3 assignment and eliminate, 
        /// none\mrv\mrv-md  for the SelectUnassignedVariable delegate , 
        /// and lexicographic\LCV  for the SelectDomainValue delegate . 
        /// </summary>
        /// <param name="start">The start.</param>
        private void SetSolvingConditions(StartingInfo start)
        {
            if (start.isAC)
            {
                Assign = AssignWithAc3;
                Eliminate = EliminateWithAc3;
            }
            else
            {
                if (start.isFC)
                {
                    Assign = AssignFC;
                    Eliminate = EliminateFC;
                }
                else
                {
                    Assign = AssignNone;
                    Eliminate = EliminateNone;
                }
            }

            if (start.isLCV)
                SelectDomainValue = LeastConstraintValue;
            else
                SelectDomainValue = LexicographicOrderFirst;

            if (start.isMRV_MD)
                SelectUnassignedVariable = MRV_With_MD;
            else if (start.isMRV)
                SelectUnassignedVariable = MinimumRemainingValues;
            else
                SelectUnassignedVariable = FirstUnassignedCell;
        }

        private void SetMaxDomain()
        {
            switch (m_gridSize)
            {
                case 4:
                    m_MaxDomain = "1234";
                    break;
                case 9:
                    m_MaxDomain = "123456789";
                    break;
                case 16:
                    m_MaxDomain = "123456789ABCDEFG";
                    break;
                case 25:
                    m_MaxDomain = "123456789ABCDEFGHIJKLMNOP";
                    break;
                default:
                    break;
            }
        }
        #endregion

        #region constraint propagation ...
        #region None ...
        MyCell[,] AssignNone(MyCell[,] branch, Pos p, char v)
        {
            string oldval = branch[p.ln, p.col].Value;
            branch[p.ln, p.col].Value = v.ToString();
            branch[p.ln, p.col].assigned = true;
            if (isHavingConflicts(branch, p.ln, p.col))
            {
                return null;
            }
            return branch;
        }

        MyCell[,] EliminateNone(MyCell[,] branch, Pos p, char v)
        {
            branch[p.ln, p.col].Value = branch[p.ln, p.col].Value.Replace(v.ToString(), "");
            return branch;
        }
        #endregion

        #region Forward Checking ...
        MyCell[,] EliminateFC(MyCell[,] branch, Pos p, char val)
        {
            branch[p.ln, p.col].Value = branch[p.ln, p.col].Value.Replace(val.ToString(), "");
            return branch;
        }

        MyCell[,] AssignFC(MyCell[,] branch, Pos p, char val)
        {
            for (int i = 0; i < branch[p.ln, p.col].Peers.Count; i++)
            {
                branch[branch[p.ln, p.col].Peers[i].ln, branch[p.ln, p.col].Peers[i].col].Value = branch[branch[p.ln, p.col].Peers[i].ln, branch[p.ln, p.col].Peers[i].col].Value.Replace(val.ToString(), "");
                if (branch[branch[p.ln, p.col].Peers[i].ln, branch[p.ln, p.col].Peers[i].col].Value.Length == 0)
                    return null;
            }
            branch[p.ln, p.col].Value = val.ToString();
            branch[p.ln, p.col].assigned = true;
            return branch;
        }

        #endregion

        #region Arc Consistency ...
        /// <summary>
        /// Assigns the with ac3.
        /// </summary>
        /// <param name="Cells">The cells.</param>
        /// <param name="assignmentPosition">The assignment position.</param>
        /// <param name="assignmentValue">The assignment value.</param>
        /// <returns></returns>
        MyCell[,] AssignWithAc3(MyCell[,] Cells, Pos assignmentPosition, char assignmentValue)
        {

            for (int i = 0; i < m_gridSize; i++)
                if (m_MaxDomain[i] != assignmentValue)
                {
                    Cells = EliminateWithAc3(Cells, assignmentPosition, m_MaxDomain[i]);
                    if (Cells == null)
                        return null;
                }
            Cells[assignmentPosition.ln, assignmentPosition.col].assigned = true;
            return Cells;
        }

        /// <summary>
        /// Eliminates the with ac3.
        /// </summary>
        /// <param name="Cells">The cells.</param>
        /// <param name="assignmentPosition">The assignment position.</param>
        /// <param name="assignmentValue">The assignment value.</param>
        /// <returns></returns>
        MyCell[,] EliminateWithAc3(MyCell[,] Cells, Pos assignmentPosition, char assignmentValue)
        {
            //Check if already eliminated  : 
            if (!Cells[assignmentPosition.ln, assignmentPosition.col].Value.Contains(assignmentValue.ToString()))
                return Cells;
            //eliminating :
            Cells[assignmentPosition.ln, assignmentPosition.col].Value = Cells[assignmentPosition.ln, assignmentPosition.col].Value.Replace(assignmentValue.ToString(), "");

            //check for inconsistency.
            if (Cells[assignmentPosition.ln, assignmentPosition.col].Value.Length == 0)
                return null;

            if (Cells[assignmentPosition.ln, assignmentPosition.col].Value.Length == 1)
            {
                Cells[assignmentPosition.ln, assignmentPosition.col].assigned = true;
                char val2 = Cells[assignmentPosition.ln, assignmentPosition.col].Value[0];

                for (int i = 0; i < Cells[assignmentPosition.ln, assignmentPosition.col].Peers.Count; i++)
                {
                    Cells = EliminateWithAc3(Cells, Cells[assignmentPosition.ln, assignmentPosition.col].Peers[i], val2);
                    if (Cells == null)
                        return null;
                }
            }

            for (int i = 0; i < 3; i++)
            {
                int n = m_gridSize;
                int m = 0;
                List<Pos> val_place = new List<Pos>();
                for (int j = 0; j < Cells[assignmentPosition.ln, assignmentPosition.col].Units[i].Count; j++)
                {
                    if (Cells[Cells[assignmentPosition.ln, assignmentPosition.col].Units[i][j].ln, Cells[assignmentPosition.ln, assignmentPosition.col].Units[i][j].col].assigned)
                        n--;
                    else
                        m++;
                    if (Cells[Cells[assignmentPosition.ln, assignmentPosition.col].Units[i][j].ln, Cells[assignmentPosition.ln, assignmentPosition.col].Units[i][j].col].Value.Contains(assignmentValue.ToString()))
                    {
                        val_place.Add(new Pos(Cells[assignmentPosition.ln, assignmentPosition.col].Units[i][j].ln, Cells[assignmentPosition.ln, assignmentPosition.col].Units[i][j].col));
                    }
                }
                if (m > n)
                    return null;

                if (val_place.Count == 0)
                    return null;

                if (val_place.Count == 1)
                {
                    Cells = AssignWithAc3(Cells, val_place[0], assignmentValue);
                    if (Cells == null)
                        return null;
                }

            }

            return Cells;
        }
        #endregion
        #endregion

        #region Variable Heuristics  ...

        /// <summary>
        /// gets the First unassigned cell.
        /// </summary>
        /// <param name="branch">The branch.</param>
        /// <returns></returns>
        Pos FirstUnassignedCell(MyCell[,] branch)
        {
            for (int i = 0; i < m_gridSize; i++)
                for (int j = 0; j < m_gridSize; j++)
                    if (!branch[i, j].assigned)
                        return new Pos(i, j);
            return null;
        }

        /// <summary>
        /// gets position of Minimum the remaining values Variable . 
        /// </summary>
        /// <param name="branch">The branch.</param>