Just Code‎ > ‎

C# Width/Depth first tree search soduko solver

posted Aug 27, 2009, 2:21 AM by Peter Henell   [ updated Jan 29, 2012, 6:08 AM ]
Program.cs:
using System;
using Sudoku;

/* Felstavat mm */
namespace Sudoku
{
    class Sudukosolver
    {
        static void Main()
        {
            Agent agent = new Agent();
            
            if (agent.solveProblem(new Classes.SudokuProblemItem().getProblemStart()))
            {
                Console.WriteLine("Yay");
                Console.ReadKey();
            }
            else
            {
                Console.WriteLine("Nay :(");
                Console.ReadKey(); 
            }
            
        }
    }


    
    
}


Agent.cs:
using System;
using System.Collections.Generic;
using Sudoku.Interfaces;

namespace Sudoku
{

    /// <summary>
    /// The agent will try to solv any problem that implements ISolvableNode, using tree search algorithms.
    /// </summary>
    class Agent
    {
        private readonly List<ISolvableNode> OPEN;
        private readonly List<ISolvableNode> CLOSED;
        private readonly List<ISolvableNode> NODES;
        private ISolvableNode root;

        public Agent()
        {
            OPEN = new List<ISolvableNode>();
            CLOSED = new List<ISolvableNode>();
            NODES = new List<ISolvableNode>();
        }
        private bool solve(ISolvableProblemItem solvableProblemItem)
        {
            root = solvableProblemItem.getStartNode();
            OPEN.Add(root);
            while (true)
            {
                if (OPEN.Count == 0)
                {
                    Console.WriteLine("Failed after " + CLOSED.Count);
                    return false;
                }

                ISolvableNode N = OPEN[0].createCopy();
                CLOSED.Add(N.createCopy());
                OPEN.RemoveAt(0);

                if (N.isGoal())
                {
                    N.print();
                    return true;
                }

                List<ISolvableNode> tmp = new List<ISolvableNode>();   
                tmp.Clear();
                tmp = N.getChildren();
                NODES.Clear();

                for (short i = 0; i < tmp.Count; i++)
                    NODES.Add(tmp[i]);

                for (int i = 0; i < OPEN.Count; i++)
                {
                    for (int ii = NODES.Count - 1; ii > 0; ii--)
                    {
                        if (OPEN[i].isEqualTo(NODES[ii]))
                        {
                            OPEN[i].print();
                            NODES[ii].print();
                            NODES.RemoveAt(ii);
                        }
                    }
                }
                for (int i = 0; i < CLOSED.Count; i++)
                {
                    for (int ii = NODES.Count - 1; ii > 0; ii--)
                    {
                        if ((CLOSED[i]).isEqualTo(NODES[ii]))
                        {
                            CLOSED[i].print();
                            NODES[ii].print();
                            NODES.RemoveAt(ii);
                        }
                    }
                }

                Expand(NODES);
            }
        }
        private void Expand(IList<ISolvableNode> cNODES)
        {
            for (int i = 0; i < cNODES.Count; i++)
                OPEN.Add(cNODES[i].createCopy());
        }

        public bool solveProblem(ISolvableProblemItem solvableProblemItem)
        {
            return solve(solvableProblemItem);
        }
    }


}


Interfaces used:
namespace Sudoku.Interfaces
{
    interface ISolvableProblemItem
    {
        /// <summary>
        /// Indicates if this Item is the goal of the problem
        /// </summary>
        /// <returns></returns>
        bool isGoal();

        /// <summary>
        /// Should set itself to be the startingpoint of the problem and then return itself or return
        /// </summary>
        /// <returns></returns>
        ISolvableProblemItem getProblemStart();

        ISolvableNode getStartNode();

       

    }
}

using System.Collections.Generic;

namespace Sudoku.Interfaces
{
    /// <summary>
    /// ISolvableNode is a state that can be transformed towards a goal. It is transformed by calling getChildren.
    /// </summary>
    interface ISolvableNode
    {

        /// <summary>
        /// Creates a copy of This Solvable Node
        /// </summary>
        /// <returns></returns>
        ISolvableNode createCopy();

        /// <summary>
        /// If needed to initialize the SolvableNode
        /// </summary>
        void init();

        /// <summary>
        /// Indicates if this Solvable Node is the solution to the problem. The Solvable Node need to define it's own goal.
        /// </summary>
        /// <returns>Should return true if it is the goal, else false</returns>
        bool isGoal();

        /// <summary>
        /// Prints the current state of the Solvable Node
        /// </summary>
        void print();

        /// <summary>
        ///  Get all possible transformations of the Solvable Node
        /// </summary>
        /// <returns>A list of all possible solvable Nodes that can be transformed from This </returns>
        List<ISolvableNode> getChildren();

        /// <summary>
        /// Indicates that This have the same state as f
        /// </summary>
        /// <param name="f">The other Solvale Node to compare to</param>
        /// <returns></returns>
        bool isEqualTo(ISolvableNode f);

        /// <summary>
        ///  Some value that indicated uniqeness of the Solvable Node
        /// </summary>
        /// <returns>A long value</returns>
        long getChecksum();


        ISolvableProblemItem SolvableProblemItem
        {
            get;
            set;
        }

    }
}


Implementation of those interfaces to solve Sudoku:
using Sudoku.Interfaces;

namespace Sudoku.Classes
{
    class SudokuProblemItem : ISolvableProblemItem
    {
        private short[,] field;

        public SudokuProblemItem()
        {
            field = new short[9,9];
        }

        public short this[int a, int b]
        {
            get { return Field[a, b]; }
            set
            {
                if(Field == null)
                    Field = new short[9,9];
                Field[a, b] = value;
            }
        }

        public short[,] Field
        {
            get { return field; }
            set { field = value; }
        }

        public bool isGoal()
        {           
            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                    if (Field[j, i] == 0)
                        return false;

            return true;
        }

        public ISolvableProblemItem getProblemStart()
        {
            Field = new short[9, 9]{
                 {0, 9, 0, 0, 0, 6, 1, 0, 0}, 
                 {0, 0, 0, 5, 0, 0, 0, 3, 2}, 
                 {3, 0, 4, 0, 1, 0, 0, 0, 0}, 

                 {0, 0, 0, 8, 5, 0, 0, 1, 0}, 
                 {9, 5, 0, 6, 0, 0, 0, 8, 0}, 
                 {0, 0, 8, 0, 0, 9, 2, 0, 5}, 

                 {0, 0, 0, 0, 9, 0, 3, 0, 7}, 
                 {4, 0, 3, 2, 0, 0, 0, 0, 0}, 
                 {0, 6, 0, 0, 3, 5, 8, 0, 0} 
             };
            return this;
        }

        public ISolvableNode getStartNode()
        {
            return new SudokuNode(getProblemStart());
        }
    }
}

using System;
using System.Collections.Generic;
using Sudoku.Interfaces;
using Sudoku.Classes;

namespace Sudoku
{
    /*
    * Class Node
    *
    * Use as a node in the search tree with lots of fun stuff
    *
    *
    */
    class SudokuNode : ISolvableNode
    {
        private long checksum;
        private SudokuProblemItem problemItem;



        public SudokuNode(ISolvableProblemItem problemItem)
        {
            SolvableProblemItem = new SudokuProblemItem();

            short[,] cf = ((SudokuProblemItem)problemItem).Field;
            // Set the values of things
            ((SudokuProblemItem)SolvableProblemItem).Field = new short[9, 9];
            for (int i = 0; i < 9; i++)
                for (int ii = 0; ii < 9; ii++)
                    ((SudokuProblemItem)SolvableProblemItem)[i, ii] = cf[i, ii];
            init();
        }

        public ISolvableProblemItem SolvableProblemItem
        {
            get { return problemItem; }
            set
            {
                if(problemItem == null)
                    problemItem = new SudokuProblemItem();
                problemItem = (SudokuProblemItem)value;
            }
        }

        public ISolvableNode createCopy()
        {
            return new SudokuNode(SolvableProblemItem);
        }

        public void init()
        {
            calculateChecksum();
        }
        public bool isGoal()   // Indicates if this Node is the solution to the problem
        {
            //for (int i = 0; i < 9; i++)
            //    for (int j = 0; j < 9; j++)
            //        if (((SudokuProblemItem)SolvableProblemItem)[j, i] == 0)
            //            return false;

            //return true;
            return SolvableProblemItem.isGoal();
        }
        public void print()
        {
            printShort();
        }
        private void printShort()
        {
            Console.WriteLine("Checksum is: " + checksum);
            for (short i = 0; i < 9; i++)
            {
                for (short ii = 0; ii < 9; ii++)
                    Console.Write(" " + ((SudokuProblemItem)SolvableProblemItem)[i, ii]);
                Console.WriteLine("");
            }
            Console.WriteLine("");
        }
        private void calculateChecksum()
        {
            // Calculate the checksum of the Field.
            checksum = 0;
            checksum = SolvableProblemItem.GetHashCode();
        }

        /// <summary>
        /// Get all children that can be transformed from this node.
        /// </summary>
        /// <returns></returns>
        public List<ISolvableNode> getChildren()
        {
            // Return all posible children for the 'next' position in the grid
            int[] next = getNextFreeSpot();

            if (next == null)
                return null; // We could not find a free spot. Thus, we cannot return any children

            List<ISolvableNode> possible = new List<ISolvableNode>();
            int counter = 0;
            for (short i = 1; i < 10; i++)
            {
                if (!(isInCol(i, next) || isInRow(i, next) || isInSquare(i, next)))
                {
                    possible.Add(new SudokuNode(SolvableProblemItem));
                    ((SudokuProblemItem)((SudokuNode)possible[counter]).SolvableProblemItem)[next[0], next[1]] = i;
                    possible[counter].init();
                    counter++;
                }
            }
            return possible;
        }

        /// <summary>
        /// Is this node equal to f?
        /// </summary>
        /// <param name="f">The other node to compare to</param>
        /// <returns></returns>
        public bool isEqualTo(ISolvableNode f)
        {
            calculateChecksum();
            f.init();
            if (checksum == f.getChecksum())
                return true;
            return false;
        }

        /// <summary>
        /// Returns the checksum, some value that is unique to the current state
        /// </summary>
        /// <returns></returns>
        public long getChecksum()
        { return checksum; }

        /// <summary>
        /// Gets the location of the next free spot in the 9*9 (the big) grid
        /// </summary>
        /// <returns></returns>
        private int[] getNextFreeSpot()
        {
            // Finds the next spot in field in wich we can put a number
            // If this is used those spots who are assigned a number att start will not be evaluated with the getchildren, its ok since it would only have one children.
            // Save some memory....
            // Can this function be altered in a way so that the next spot will be picked at random? And would that increase the overall performance of the solution?
            for (int i = 0; i < 9; i++)
            {
                for (int ii = 0; ii < 9; ii++)
                {
                    if (((SudokuProblemItem)SolvableProblemItem)[i, ii] == 0)
                    {
                        int[] r = new int[] { i, ii };
                        return r;
                    }
                }
            }
            Console.WriteLine("Found no spot to put the next number in. Is the playfield full?");
            return null; // Found no spot, is it full?
        }

        /// <summary>
        /// Checks if n is in the current Row
        /// </summary>
        /// <param name="n">The number to look for</param>
        /// <param name="pos">The row to search in</param>
        /// <returns></returns>
        private bool isInRow(short n, int[] pos)
        {
            // true om finns i raden
            for (int i = 0; i < 9; i++)
                if (((SudokuProblemItem)SolvableProblemItem)[pos[0], i] == n)
                    return true;

            return false;

        }
        
        /// <summary>
        /// Checks if n is in the current column
        /// </summary>
        /// <param name="n">The number to look for</param>
        /// <param name="pos">The row to search in</param>
        /// <returns></returns>
        private bool isInCol(short n, int[] pos)
        {
            // true om finns i columnen
            for (int i = 0; i < 9; i++)
                if (((SudokuProblemItem)SolvableProblemItem)[i, pos[1]] == n)
                    return true;
            return false;
        }
    
        /// <summary>
        /// Checks if n is in the current 3*3 square
        /// </summary>
        /// <param name="n">The number to search for</param>
        /// <param name="pos">The square</param>
        /// <returns></returns>
        private bool isInSquare(short n, int[] pos)
        {
            // true om finns i raden
            short h = Convert.ToInt16(pos[0] / 3);
            short b = Convert.ToInt16(pos[1] / 3);

            for (short x = Convert.ToInt16(3 * b); x < Convert.ToInt16(3 * (b + 1)); x++)
                for (short y = Convert.ToInt16(3 * h); y < Convert.ToInt16(3 * (h + 1)); y++)
                    if (((SudokuProblemItem)SolvableProblemItem)[y, x] == n)
                        return true;
            return false;
        }

  
    }
}
ċ
TreeSearchAgentAndExamples.zip
(231k)
Peter Henell,
Jan 29, 2012, 6:08 AM
Comments