mysolver.cs

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

        /// <returns></returns>
        Pos MinimumRemainingValues(MyCell[,] branch)
        {
            int min = m_gridSize + 1;
            Pos p=new Pos() ;

            for (int i = 0; i < m_gridSize; i++)
                for (int j = 0; j < m_gridSize; j++)
                {
                    if ((!branch[i, j].assigned) && (branch[i, j].Value.Length < min))
                    {
                        p.ln = i;
                        p.col = j;
                        min = branch[i, j].Value.Length;
                    }
                }
            return p; 
        }

        Pos MRV_With_MD(MyCell[,] branch)
        {
            return MaxDegree(branch, MinimumRemainingValuesList(branch));
        }

        /// <summary>
        /// gets a list of Minimum the remaining values Variables positions .
        /// </summary>
        /// <param name="branch">The branch.</param>
        /// <returns></returns>
        List<Pos> MinimumRemainingValuesList(MyCell[,] branch)
        {
            int min = m_gridSize + 1;
            List<Pos> list = new List<Pos>(); 
            for (int i = 0; i < m_gridSize; i++)
                for (int j = 0; j < m_gridSize; j++)
                {
                    if ((!(branch[i, j].assigned)) && (branch[i, j].Value.Length == min))
                    {
                        list.Add(new Pos(i, j));
                        continue;
                    }
                    if ((!(branch[i, j].assigned))&& (branch[i, j].Value.Length < min))
                    {
                        list.Clear();
                        min = branch[i, j].Value.Length;
                        list.Add(new Pos(i, j)); 
                    }

                }
            return list;
        }

        /// <summary>
        /// get position of the variable it the maxumum degree from the positions in MRVS.
        /// </summary>
        /// <param name="branch">The branch.</param>
        /// <param name="MRVS">The MRVS.</param>
        /// <returns></returns>
        Pos MaxDegree(MyCell [,]branch, List<Pos> MRVS)
        {
            int deg = -1;
            Pos p =null;
            for (int i = 0; i < MRVS.Count; i++)
            {
                int count = 0; 
                for (int k = 0; k < branch[MRVS[i].ln ,MRVS[i].col].Peers.Count; k++)
                    if (!branch[branch[MRVS[i].ln ,MRVS[i].col].Peers[k].ln,branch[MRVS[i].ln ,MRVS[i].col].Peers[k].col].assigned)
                        count++;
                if (count > deg)
                {
                    deg = count;
                    p = MRVS[i]; 
                }
            }
            return p;
        }
        #endregion

        #region Value Heuristics  ...
        /// <summary>
        /// gets the Leasts the constraint value.
        /// </summary>
        /// <param name="branch">The branch.</param>
        /// <param name="variablePosition">The variable position.</param>
        /// <returns></returns>
        char LeastConstraintValue(MyCell[,] branch, Pos variablePosition)
        {
            int[] arr = new int[branch[variablePosition.ln, variablePosition.col].Value.Length];
            for (int i = 0; i < arr.Length; i++)
                arr[i] = 0;
            for (int i = 0; i < branch[variablePosition.ln, variablePosition.col].Value.Length; i++)
                for (int j = 0; j < branch[variablePosition.ln, variablePosition.col].Peers.Count; j++)
                {
                    if (branch[branch[variablePosition.ln, variablePosition.col].Peers[j].ln, branch[variablePosition.ln, variablePosition.col].Peers[j].col].Value.Contains(branch[variablePosition.ln, variablePosition.col].Value[i].ToString()))
                        arr[i]++;
                }
            return branch[variablePosition.ln, variablePosition.col].Value[GetMinIndex(arr)];
        }

        /// <summary>
        /// gets the first Lexicographics the ordered value from the Domain.
        /// </summary>
        /// <param name="branch">The branch.</param>
        /// <param name="variablePosition">The variable position.</param>
        /// <returns></returns>
        char LexicographicOrderFirst(MyCell[,] branch, Pos variablePosition)
        {
            return branch[variablePosition.ln, variablePosition.col].Value[0];
        }
        #endregion

        #region Backtracking Search ...
        /// <summary>
        /// Doing Backtracking search.
        /// </summary>
        /// <param name="branch">The branch.</param>
        /// <returns></returns>
        MyCell[,] backtrackingSearch(MyCell[,] branch)
        {
             MyCell[,] ret;
             if (branch == null) return null; 
            if (isFinish(branch))  return branch;

            Pos s = SelectUnassignedVariable(branch);
            while (branch[s.ln, s.col].Value.Length > 0)
            {
                char c = SelectDomainValue(branch, s);
                ret = backtrackingSearch(Assign(Clone(branch), s, c));
                if (ret != null)
                    return ret;
                m_NumOfBacktracking++;
               
                branch = Eliminate(branch, s, c);
                if (branch == null) return null; 
              
            }
            return null;
        }
        #endregion

        #region Assistence Methods ...
        /// <summary>
        /// Determines whether [is having conflicts] [the specified branch].
        /// </summary>
        /// <param name="branch">The branch.</param>
        /// <param name="ln">The ln.</param>
        /// <param name="col">The col.</param>
        /// <returns>
        /// 	<c>true</c> if [is having conflicts] [the specified branch]; otherwise, <c>false</c>.
        /// </returns>
        bool isHavingConflicts(MyCell[,] branch, int ln, int col)
        {
            //Line  : 
            for (int i = 0; i < m_gridSize; i++)
            {
                if (i == col) continue;
                if (branch[ln, i].Value == branch[ln, col].Value)
                    return true;
            }

            //Column : 
            for (int i = 0; i < m_gridSize; i++)
            {
                if (i == ln) continue;
                if (branch[i, col].Value == branch[ln, col].Value)
                    return true;
            }

            //Square  : 
            int dx = col - (col % (int)Math.Sqrt(m_gridSize));
            int dy = ln - (ln % (int)Math.Sqrt(m_gridSize));

            for (int r = dy; r < dy + (int)Math.Sqrt(m_gridSize); r++)
                for (int s = dx; s < dx + (int)Math.Sqrt(m_gridSize); s++)
                {
                    if ((r == ln) || (s == col)) continue;
                    if (branch[r, s].Value == branch[ln, col].Value)
                        return true;
                }

            return false;
        }



        /// <summary>
        /// Clones the specified source.
        /// </summary>
        /// <param name="source">The source.</param>
        /// <returns></returns>
        MyCell[,] Clone(MyCell[,] source)
        {
            MyCell[,] ret = new MyCell[m_gridSize, m_gridSize];
            for (int i = 0; i < m_gridSize; i++)
                for (int j = 0; j < m_gridSize; j++)
                    ret[i, j] = new MyCell(source[i, j]);

            return ret;
        }

        /// <summary>
        /// Parses the grid.
        /// </summary>
        /// <param name="grid">The grid.</param>
        /// <returns></returns>
        public MyCell[,] ParseGrid(string grid)
        {
            MyCell[,] Cells = new MyCell[m_gridSize, m_gridSize];
            for (int i = 0; i < m_gridSize; i++)
                for (int j = 0; j < m_gridSize; j++)
                    Cells[i, j] = new MyCell(m_MaxDomain, i, j, m_gridSize);

            for (int i = 0; i < m_gridSize; i++)
                for (int j = 0; j < m_gridSize; j++)
                    if ((char.IsDigit(grid[i * m_gridSize + j])) ||
                        ((grid[i * m_gridSize + j] >= 'A' && (grid[i * m_gridSize + j] <= m_MaxDomain[m_MaxDomain.Length - 1]))))
                    {

                        Cells = Assign(Cells, new Pos(i, j), grid[i * m_gridSize + j]);
                        if (Cells == null)
                            return null;
                    }
            return Cells;
        }

        /// <summary>
        /// Determines whether the specified branch is finish.
        /// </summary>
        /// <param name="branch">The branch.</param>
        /// <returns>
        /// 	<c>true</c> if the specified branch is finish; otherwise, <c>false</c>.
        /// </returns>
        bool isFinish(MyCell[,] branch)
        {
            for (int i = 0; i < m_gridSize; i++)
                for (int j = 0; j < m_gridSize; j++)
                    if (!branch[i, j].assigned)
                        return false;

            return true;
        }

        /// <summary>
        /// Gets the index of the min.
        /// </summary>
        /// <param name="indexesArray">The indexes array.</param>
        /// <returns></returns>
        int GetMinIndex(int[] indexesArray)
        {
            int min = indexesArray[0];
            int index = 0;
            for (int i = 1; i < indexesArray.Length; i++)
            {
                if (indexesArray[i] < min)
                {
                    min = indexesArray[i];
                    index = i;
                }
            }
            return index;
        }
        #endregion

        /// <summary>
        /// Solves the specified grid.
        /// </summary>
        /// <param name="grid">The grid.</param>
        /// <returns></returns>
        public MyCell[,] Solve(string grid)
        {
            MyCell[,] result;
            DateTime now = DateTime.Now; 
            result = backtrackingSearch(ParseGrid(grid));
            m_duration = DateTime.Now - now;
            return result; 
        }
       
    }
}