Пятнашки с IDA* алгоритмом - Gamedev - Ответ 13032589

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _15probe
{
    class Program
    {
        static void Main(string[] args)
        {
            #region переменные
            int[] dx = new int[] { 0, -1, 0, 1 };//смещения пустой клетки
            int[] dy = new int[] { 1, 0, -1, 0 };
            //var moveDescription:Array = new Array("D", "L", "U", "R"); }
            char[] move_desc = new char[] { 'D', 'L', 'U', 'R' };// Возможные ходы
            int[] opposite_move = new int[] { 2, 3, 0, 1 };// Противоположные ходы (2, 3, 0, 1)
            //var oppositeMove:Array = new Array(2, 3, 0, 1); }
            const int infinity = 10000;
            //int x0, // координаты пустой клетки
            //    y0; // координаты пустой клетки
            int[] goalX = new int[16]; //goalX[i] - координата x i-й пятнашки, ...
            int[] goalY = new int[16];
            int[,] board = new int[,] { { 2, 5, 4, 6 }, { 1, 13, 11, 3 },
                                        { 14, 12, 7, 10 }, { 8, 15, 9, 0 } }; // доска
            //int step;
 
            int[,] boardGoal = new int[4, 4]; // доска целевого состояния
 
            int minPrevIteration; //deepness; // глубина
                                  //string resultString; //результат
                                  //минимум стоимости среди нерассмотренных узлов
            #endregion
            //--------------------------------
            //инициализирует целевое состояние
            void initGoalArrays()
            {
                for (int i = 0; i < 15; i++)
                {
                    goalX[i + 1] = i % 4;
                    goalY[i + 1] = i / 4;
                    goalX[0] = 4;
                    goalY[0] = 4;
                }
            }
            //меняет местами две пятнашки
            void swap(int y1, int x1, int y2, int x2)
            {
                int value1, value2;
                value1 = board[y1, x1];
                value2 = board[y2, x2];
                board[y1, x1] = value2;
                board[y2, x2] = value1;
            }
            //определяет "решаемость" пятнашек
            bool isSolvable()
            {
                int count, transpos, value, i, j;
                count = 0;
                transpos = 0;
                value = 0;
                int[] a = new int[16];
 
                for (i = 0; i < 4; i++)
                {
                    if (i % 2 == 0)
                    {
                        for (j = 0; j < 4; j++)
                        {
                            value = board[i, j];
                            if (value > 0)
                            {
                                a[count] = value;
                                count++;
                            }
                        }
                    }
                    else
                    {
                        for (j = 3; j >= 0; j--)
                        {
                            value = board[i, j];
                            if (value > 0)
                            {
                                a[count] = value;
                                count++;
                            }
                        }
                    }
                }
 
                for (i = 0; i <= count - 2; i++)
                    for (j = i + 1; j <= count - 1; j++)
                        if (a[i] > a[j])
                            transpos++;
 
                if (transpos % 2 == 1)
                    return true;
 
                return false;
            }
            //718508644774274130
            //10446283839894545490
            //эвристическая оценочная функция Манхеттеновское расстояние
            void estimate(out int manhattan)
            {
                int i, j, value, m;
                manhattan = 0;
                for (i = 0; i < 4; i++)
                {
                    for (j = 0; j < 4; j++)
                    {
                        value = board[i, j];
                        if (value > 0)
                        {
                            m = Math.Abs(i - goalY[value]) + Math.Abs(j - goalX[value]);
                            manhattan = manhattan + m;
                        }
                    }
                }
            }
            //поиск в глубину с обрезанием f=g+h < deepness
            void recSearch(int g, int previousMove, int x0, int y0, int step, int deepness, out bool tf,
                            out string resultString)
            {
                int h;
                int manhattan;
                estimate(out manhattan);
                h = manhattan;
                tf = false;
                resultString = "";
                step = 0;
                // h = минимум ходов к цели
                if (h == 0)
                {
                    tf = true;
                    return; // если это цель - ура!
                }
                // если то, что мы прошли (g) + то, что нам как минимум осталось (h)
                // больше допустимой глубины - выход.
                int f;
                f = g + h;
                if (f > deepness)
                {
                    //нaходим минимум стоимости среди "обрезаных" узлов
                    if (minPrevIteration > f)
                        minPrevIteration = f;
                    return;
                }
                int newx, newy;
                bool res;
                // делаем всевозможные ходы
                for (int i = 0; i < 4; i++)
                {
                    if (opposite_move[i] != previousMove)
                    {
                        // новые координаты пустой клетки
                        newx = x0 + dx[i];
                        newy = y0 + dy[i];
                        if ((newy <= 3) && (newy >= 0) && (newx <= 3) && (newx >= 0))
                        {
                            swap(y0, x0, newy, newx); // двигаем пустую клетку на новое место
                            recSearch(g + 1, i, newx, newy, step, deepness, out tf, out resultString); // рекурсивный поиск с новой позиции
                            res = tf;
                            swap(y0, x0, newy, newx); // возвращаем пустую клетку назад
                            if (res == true) //если было найдено решение
                            {
                                resultString = move_desc[i] + resultString; //записываем этот ход
                                step++;
                                tf = true;
                                return; // и выходим
                            }
                        }
                    }
                }
                return; //цели не нашли
            }
 
            //итерация глубины и IDA*
            bool idaStar(out string result)
            {
                bool res;
                int x0 = -1;
                int y0 = -1;
                bool tf;
                int step;
                string resultString;
                res = false;
                result = "";
                int manhattan;
                estimate(out manhattan);
                int deepness = manhattan; // начинаем с h для начального состояния
                while (deepness <= 50)
                {
                    minPrevIteration = infinity; // инициализация для поиска минимума
                    // поиск пустой клетки
                    for (int i = 0; i < 4; i++)
                    {
                        for (int j = 0; j < 4; j++)
                        {
                            if (board[i, j] == 0)
                            {
                                x0 = j;
                                y0 = i;
                            }
                        }
                    }
                    step = 0;                    
                    recSearch(0, -1, x0, y0, step, deepness, out tf, out resultString);
                    deepness = minPrevIteration;
                    if (res)
                    {
                        result = resultString;
                        break;
                    }
 
                }
                return res;
            }
 
            // ----------------------------           
            initGoalArrays();
            // Целевая доска
            int zn = 1;
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    boardGoal[i, j] = zn;
                    zn++;
                }
            }
            boardGoal[3, 3] = 0;
            int manhat;
            estimate(out manhat);
 
            if (!isSolvable()) // если задача нерешаема
            {
                Console.WriteLine("Задача неразрешима");
                return;
            }
            if (manhat == 0) //если это уже цель
            {
                Console.WriteLine("Это уже цель");
                return;
            }
            //делаем IDA* поиск
            string finalresult;
            idaStar(out finalresult);
            //recSearch(0, -1, 0, 0, out tf, out step, out resultString);
            //Console.WriteLine("Количество ходов:", step);
            Console.WriteLine("Путь:", finalresult); //выводим результат
            
            if (finalresult == null) 
                Console.WriteLine("IDA* failed");
 
        }
    }
}