Блог

Я пытаюсь рекурсивно решить головоломку со скользящим изображением, чтобы вычислить минимальное количество шагов, необходимых для подсчета очков. Моя текущая попытка может правильно рассчитать минимальные шаги, необходимые, когда это меньше 8, но выше этого он не может вычислить ответ. Это работает путем вычисления общего расстояния на доске, на котором каждый квадрат (кроме пустого квадрата) находится от желаемого места (его оценки). Эта оценка также учитывает, что квадрат может перемещаться по вертикали, уменьшая общую оценку на основе этого. Рекурсивная функция сначала проверяет, является ли оценка == 0 (таким образом, является полной), затем просматривает все индексы, с которыми можно поменять местами пустой квадрат, создавая и оценивая новую головоломку и только продолжая вызывать себя рекурсивно с новой головоломкой, если встречается меньшая оценка.

Это код, который я использую для рекурсивной функции:

         /// Counts smallest number of steps that the sliding puzzle will take.
        /// Sends it to the property for minimum steps.
        /// </summary>
        private void CountRecursiveStepsToSolve()
        {
            //Builds the board to work with
            string[] currentBoard = new string[] { ImageA1, ImageA2, ImageA3, ImageB1, ImageB2, ImageB3, ImageC1, ImageC2, ImageC3 };
            //Tells how wide the board is for vertical movement options
            int width = 3;
            //Indicates the value of the "blank" square that can be moved into
            string blank = "gray.png";
            //Index of the "blank" square
            int currentIndex = Array.FindIndex(currentBoard, s => s == blank);
            //Indices that can be moved
            int[] swappableIndices = GetSwappableIndices(currentIndex, width, currentBoard.Length - 1);
            //Score of the board (how far from completion it is, with 0 == completed)
            int previousScore = ScoreAnswer(currentBoard, answer, width, blank);
            MinimumSteps = "Minimum steps: "   SwapRecursive(0, currentIndex, currentIndex, swappableIndices, width, currentBoard, answer, previousScore, blank);
        }

        /// <summary>
        /// Recursively solves the sliding puzzle for minimum number of moves.
        /// </summary>
        /// <param name="steps">Current steps taken to solve.</param>
        /// <param name="currentIndex">Index of the "blank" square that can be moved into.</param>
        /// <param name="previousIndex">Previous index of the "blank" square. Used to prevent moving back and forth.</param>
        /// <param name="swappableIndices">Indices that the "blank" square can be swapped with. Adjacent to the "blank" square.</param>
        /// <param name="width">Width of the sliding puzzle.</param>
        /// <param name="currentBoard">Current sliding puzzle to work with.</param>
        /// <param name="answer">The sliding puzzle in its finished form.</param>
        /// <param name="previousScore">Score previously earned by the board. Used to abandon paths that don't lead closer to completion.</param>
        /// <param name="blank">Value of the "blank" square that can be moved into.</param>
        /// <returns>Minimum number of steps needed to finish the sliding puzzle.</returns>
        private int SwapRecursive(int steps, int currentIndex, int previousIndex, int[] swappableIndices, int width, string[] currentBoard, string[] answer, int previousScore, string blank)
        {
            if(ScoreAnswer(currentBoard, answer, width, blank) == 0)
            {//Puzzle finished, so return number of steps taken
                return steps;
            }
            foreach(int index in swappableIndices)
            {//Check each square adjecent to the blank square
                if(index == previousIndex)
                {//Ignore the previous blank square space to prevent repeating the same move over and over
                    continue;
                }
                //Create a new board by swapping the blank square
                string[] newBoard = Swap(currentBoard, currentIndex, index);
                //Calculate the new indices that can be swapped with
                int[] newSwappableIndices = GetSwappableIndices(index, width, newBoard.Length - 1);
                //Score the new board for how close to complete it is
                int score = ScoreAnswer(newBoard, answer, width, blank);
                if(score < previousScore)
                {//If closer to completion
                    //Solve recursively
                    int result = SwapRecursive(steps   1, index, currentIndex, newSwappableIndices, width, newBoard, answer, score, blank);
                    if(result != -1)
                    {//If not a dead end
                        //Puzzle finished, so return number of steps
                        return resu<
                    }
                }
            }
            return -1;//Hit if no progress could be made
        }

        /// <summary>
        /// Scores how close to completion the board is. Score == 0 is a completed board.
        /// </summary>
        /// <param name="currentBoard">The board to score.</param>
        /// <param name="answer">The board in its completed form.</param>
        /// <param name="width">The width of the board.</param>
        /// <param name="blank">The value of the blank square.</param>
        /// <returns>How close to completion the board is, with closer to 0 == closer to complete.</returns>
        private int ScoreAnswer(string[] currentBoard, string[] answer, int width, string blank)
        {
            int score = 0;
            for (int i = 0; i < currentBoard.Length; i  )
            {//For every space pm the board
                if(currentBoard[i] == blank)
                {//Ignore the blank space to prevent moving away from the solution by attempting to place it in the right place
                    continue;
                }
                //Take the difference between the square's current position and solved position
                int difference = Math.Abs(Array.FindIndex(answer, s => s == currentBoard[i]) - i);
                //Since the square can be moved vertically, it can be moved width indices at once
                //That means that it is the difference / width   remainder away from desired position
                score  = (difference / width)   (difference % width);
            }
            return score;
        }

        /// <summary>
        /// Swaps indices a and b on the given board and returns a new board with the result.
        /// </summary>
        /// <param name="currentBoard">The board to perform the swap on.</param>
        /// <param name="a">The first index to swap.</param>
        /// <param name="b">The second index to swap.</param>
        /// <returns>A new board with the indices swapped.</returns>
        private string[] Swap(string[] currentBoard, int a, int b)
        {
            string[] newBoard = new string[currentBoard.Length];
            Array.Copy(currentBoard, newBoard, currentBoard.Length);
            newBoard[a] = currentBoard[b];
            newBoard[b] = currentBoard[a];
            return newBoard;
        }
        
        /// <summary>
        /// Returns the indices next to current index from a board with the given width.
        /// </summary>
        /// <param name="currentIndex">The space to return indices next to.</param>
        /// <param name="width">The width of the board. Used to calculate vertical indices.</param>
        /// <param name="maxIndex">The max index of the board.</param>
        /// <returns>An array of indices next to currentIndex.</returns>
        private int[] GetSwappableIndices(int currentIndex, int width, int maxIndex)
        {
            List<int> indices = new List<int>();
            if(currentIndex - 1 >= 0)
            {
                indices.Add(currentIndex - 1);
            }
            if(currentIndex   1 <= maxIndex)
            {
                indices.Add(currentIndex   1);
            }
            if(currentIndex - width >= 0)
            {
                indices.Add(currentIndex - width);
            }
            if (currentIndex   width <= maxIndex)
            {
                indices.Add(currentIndex   width);
            }
            return indices.ToArray();
        }
 

И вот ссылка на github на проект xamarin, который его использует: https://github.com/NickCRowork/SlidingPuzzleApp
Просто нажмите «открыть слайд-головоломку», а затем «найти минимальные шаги»