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

namespace TileGame
{
    class Game
    {
        public long total_count = 0;
        public Tile[,] Board;
        public bool Solved;
        public int[] RotationSolution;

        public void Solve()
        {
            int i;
            Tile[] WorkingSet = new Tile[9];
            for (i = 0; i < 9; i++)
            {
                WorkingSet[i] = new Tile(i);
            }

            Solved = false;
            PermuteRecurse(WorkingSet, 0, WorkingSet.Length-1);
        }

        private void swap(ref Tile a, ref Tile b)
        {
            Tile temp = a;
            a = b;
            b = temp;
        }

        private void PermuteRecurse(Tile[] list, int k, int m)
        {
            int i;
            if (k == m)
            {
                CheckPermutation(list);
            }
            else
                for (i = k; i <= m; i++)
                {
                    swap(ref list[k], ref list[i]);
                    PermuteRecurse(list, k + 1, m);
                    if (Solved)
                        return;

                    swap(ref list[k], ref list[i]);
                }
        }

        private void DoRotations(int[] rot_list)
        {
            for (int i = 0; i < 9; i++)
            {
                for (int r = 0; r < rot_list[i]; r++)
                {
                    Board[i % 3, i / 3].RotateClockwise();
                }
            }
        }

        private void UndoRotations(int[] rot_list)
        {
            for (int i = 0; i < 9; i++)
            {
                for (int r = 0; r < rot_list[i]; r++)
                {
                    Board[i % 3, i / 3].RotateCounterClockwise();
                }
            }
        }

        private void RotationList()
        {
            int i;
            int[] rot_list = new int[9]; 

            for (; ; )
            {
                DoRotations(rot_list);
                Solved = BoardIsValid();
                if (Solved)
                {
                    RotationSolution = rot_list;
                    return;
                }
                UndoRotations(rot_list);

//                for (i = 0; i < 9; i++)
//                    Console.Write(rot_list[i].ToString() + " ");
//                Console.WriteLine();

                rot_list[8]++;

                i = 8;
                for (; ; )
                {
                    if (rot_list[i] == 4)
                    {
                        rot_list[i] = 0;
                        i--;
                        if (i == -1)
                            return;
                        rot_list[i]++;
                    }
                    else
                        break;
                }
            }
        }

        private void CheckPermutation(Tile[] list)
        {
            for (int i = 0; i < 9; i++)
                Board[i % 3, i / 3] = list[i];

            RotationList();
        }

        public Game()
        {
            Board = new Tile[3, 3];

            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    Board[i, j] = null;
                }
            }
        }

        public bool BoardIsValid()
        {
            total_count++;

            if (total_count % 10000 == 0)
                Console.WriteLine(total_count.ToString());

            int i;

            for (i = 0; i < 3; i++)
            {
                if (TilesMatch(Board[0,i], Board[1,i], 2) == false)
                    return false;
            }

            for (i = 0; i < 3; i++)
            {
                if (TilesMatch(Board[1,i], Board[2,i], 2) == false)
                    return false;
            }

            for (i = 0; i < 3; i++)
            {
                if (TilesMatch(Board[i,0], Board[i,1], 1) == false)
                    return false;
            }

            for (i = 0; i < 3; i++)
            {
                if (TilesMatch(Board[i,1], Board[i,2], 1) == false)
                    return false;
            }

            return true;
        }

        public bool TilesMatch(Tile t1, Tile t2, int compare)
        {
            int first;
            int second;

            if ((t1 == null) || (t2 == null))
                return false;

            switch (compare)
            {
                case 1:
                    // bottom-to-top
                    first = 2;
                    second = 0;
                    break;
                default: // 2
                    // right-to-left
                    first = 1;
                    second = 3;
                    break;
            }
            if (((int)(t1.Sides[first]) + 10 == (int)(t2.Sides[second])) ||
                (((int)(t1.Sides[first]) - 10 == (int)(t2.Sides[second]))))
                return true;
            else
                return false;
        }
    }
}