Friday, June 15, 2012

BackTracking c#

 class Program
    {

        static int[] a;
        static int k;
        static int SIZE = 4;
        static void Main(string[] args)
        {
            a = new int[20];
            bkp();
            System.Console.ReadLine();


        }

        static void bkp()
        {
            k = 1;
            a[k] = 0;
            bool getSuccesor;
            while (k > 0)
            {
                do
                {
                    getSuccesor = HaveSuccesor();
                }
                while (getSuccesor && !IsValid());

                if (getSuccesor)
                {
                   
                    if (IsValidSolution())
                    {
                        ShowSolution();
                    }
                    else
                    {
                        k++;
                        a[k] = 0;
                    }
                }
                else
                {
                    a[k] = 0;
                    k--;
                }

            }
        }

        static bool HaveSuccesor()
        {
            if (a[k] < SIZE)
            {
                a[k]++;
                return true;
            }
            else
                return false;
        }

        public static bool IsValid()
        {
           if (k > 1)
                if (a[k] < a[k - 1]) return false;
            for (int i = 1; i < k; i++)
                if (a[i] == a[k]) return false;
           
            return true;
        }

        public static bool IsValidSolution()
        {
            if(k==SIZE) return true;
            return false;
        }

        static void ShowSolution()
        {
            for (int i = 1; i < = SIZE; i++)
                System.Console.Write(a[i] + " ");
            System.Console.Write(Environment.NewLine);
        }

        static void ShowTowers()
        {
            for (int i = 1; i < = SIZE; i++)
            {
                for (int j = 1; j < = SIZE; j++)
                {
                    if(a[i]==j)
                        System.Console.Write("T");
                    else
                        System.Console.Write("*");
                }
                System.Console.Write(Environment.NewLine);
             }
            System.Console.Write(Environment.NewLine);
          
        }


    }
}

No comments:

Post a Comment