java - 蛮力 Frog 跳跃游戏

Question

---

Frog 跳的最后一个变体显示在 the video 的末尾.

In short, you have n number of lily pads in a line and one frog on each one.

In the last variation (the one I want to brute force), the second first and second last lily pads do not have a frog. Your goal is to get all frogs to the same lily pad. Each frog can jump right or left based on the number of frogs on its lily pad, but can't jump on a empty lily pad.
(pad with 1 frog moves 1 spot, pad with n frogs moves only n spots)

Example of a solution for n=12: (there are no solutions below 12)

[1,0,1,1,1,1,1,1,1,1,0,1] - Starting formation of frogs. (counting frogs from 0. to 11.)
[1,0,1,0,2,1,1,1,1,1,0,1] - Frog 3. jumped right
[1,0,1,0,2,1,2,0,1,1,0,1] - Frog 7. jumped left
[1,0,1,0,4,1,0,0,1,1,0,1] - Frogs 6. jumped left
[5,0,1,0,0,1,0,0,1,1,0,1] - Frogs 4. jumped left
[0,0,1,0,0,6,0,0,1,1,0,1] - Frogs 0. jumped right
[0,0,1,0,0,0,0,0,1,1,0,7] - Frogs 5. jumped right
[0,0,1,0,0,0,0,0,0,2,0,7] - Frogs 8. jumped right
[0,0,1,0,0,0,0,0,0,0,0,9] - Frogs 9. jumped right
[0,0,10,0,0,0,0,0,0,0,0,0] - Frogs 11. jumped left- solved

我想为 n 只 Frog 找到解决方案，如果存在的话。我手头知道 12,14,15,16,17,18,19,20 至少有一个解决方案并且1-11 和 13 没有解。

我尝试编写一段代码来遍历所有组合，以找到 n 睡莲叶的解决方案。

编辑:代码现在可以工作了，多亏了OleV.V. , 还添加了日志记录。

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

// # Brute Force # Brute Force # Brute Force # Brute Force # Brute Force # //
public class Frogger {

    /** 
     * PUBLIC STATIC GLOBAL VARIABLES - Modify these as you wish.
     * 
     * Time Data: Levels < 20 ~ around couple seconds
     *            Level = 20 ~ around a minute
     *            Level = 21 ~ around a quarter of an hour
     *            Level = 22 ~ around a sixth of a minute
     *            Level = 23 ~ around half an hour
     *            Level = 24 ~ around a minute
     * 
     * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
        public static int Level = 12;
        public static boolean LogSolution = true;
        public static boolean LogAll = false;
    /** * * * * * * * * * * * * * * * * * * * * * * * * * * * */

    // used for logging
    private static Deque<Jump> solution = new ArrayDeque<>(Level);
    private static double time;

    public static void main(String[] args) {

        // log the time
        time = System.currentTimeMillis();

        // build the world & start jumping
        run(Level);
    }

    public static void run(int n) {

        // create the world
        int[] world = new int[n];
        for (int i = 0; i < n; i++) {
            world[i] = 1;
        }
        world[1] = 0;
        world[n-2] = 0;

        // start jumping
        if (Level > 11 && Level != 13) jump(world);
        else System.out.println("Unsolvable");
    }


    //////////////////////////////////////////////////////

    public static void jump(int[] world) {

    for (int i = 0; i < world.length; i++) {

        if (world[i] != 0) { // pad has a frog

            // check if it is solved at current pad
            if (world[i] == Level - 2) {
                System.out.println("SOLUTION: " + Arrays.toString(world));
                System.out.println(solution);
                System.out.println("\n" + (System.currentTimeMillis() - time) / 1000 + " seconds");
                System.exit(0);
            }   

            // roll-back var
            int temp = 0;

            // attempts to make a RIGHT jump 

                if (world[i] + i < world.length) { // right jump is in bound
                    if (world[i + world[i]]  != 0) { // can't jump on empty pad

                        temp = world[i];

                        // jump RIGHT
                        world[i + world[i]] += world[i];
                        world[i] = 0;

                        solution.push(new Jump(temp, i, i + temp)); // log the solution step 1/2
                        if (LogSolution) if (LogAll) System.out.println( "J: " + Arrays.toString(world)); // log the jump

                        // continue jumping
                        jump(world); 

                        // roll-back right jump
                        world[i] = temp;
                        world[i + world[i]] -= world[i];

                        if (LogAll) System.out.println("R: " + Arrays.toString(world)); // log the rollback
                        if (LogSolution) solution.pop(); // log the solution step 2/2
                    }
                }   

            // attempts to make a LEFT jump 

                if (i - world[i] >= 0) { // left jump is in bound
                    if (world[i - world[i]]  != 0) { // can't jump on empty pad

                        temp = world[i];

                        // jump LEFT
                        world[i - world[i]] += world[i];
                        world[i] = 0;

                        if (LogSolution) solution.push(new Jump(temp, i, i - temp)); // log the solution step 1/2
                        if (LogAll) System.out.println("J:" + Arrays.toString(world)); // log the jump

                        // continue jumping
                        jump(world); 

                        // roll-back left jump
                        world[i] = temp;
                        world[i - world[i]] -= world[i];

                        if (LogAll) System.out.println("R: " + Arrays.toString(world)); // log the rollback
                        if (LogSolution) solution.pop(); // log the solution step 2/2
                    }
                }
        }
    }
    }

}

---

旁注:这个问题在数学上已经解决了所有可解决的 n(所有 n > 11，除了 13，都有一个解决方案，可以通过通用方法达到)。这段代码只是我试图在 java 中做一些递归。

Answer 1

很高兴你让它工作了。我不认为你现在需要我的代码，但我会在这个答案的底部给出以防万一。

首先，如何记录解决方案？我猜你在想知道最终结果是 [0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0] 并不是那么有趣；我们想知道它是如何获得的。我将介绍两种方法。

更简单的方法是在尝试时存储每个步骤，然后在回溯时将其删除。然后当你得到解决方案时，你也已经存储了导致它的步骤。使用堆栈或类似的:

private static Deque<Jump> solution = new ArrayDeque<>(Level);

(java.util.ArrayDeque 是堆栈和队列的推荐类；对于堆栈 ArrayList 是另一种选择。)现在在您的代码中，它说记录跳转做

                    solution.push(new Jump(temp, i, i + temp));

在记录回滚时做

                    solution.pop();

使用一个简单的辅助类Jump，例如看起来像这样:

public class Jump {
    int count;
    int from;
    int to;

    public Jump(int count, int from, int to) {
        this.count = count;
        this.from = from;
        this.to = to;
    }

    @Override
    public String toString() {
        return "" + count + " frog/s jump from " + from + " to " + to;
    }
}

当我在我的解决方案中尝试时，一次搜索花费了 20% 的时间。我会说这是可以接受的。如果您非常关心性能，只有在找到解决方案后才能登录。这将要求您返回一个 boolean 值以指示成功，而不是使用 System.exit() 来停止搜索。现在你的递归调用变成了:

                    if (jump(world)) {
                        solution.push(new Jump(temp, i, i + temp));
                        return true;
                    }

您以与以前相反的顺序获取解决方案堆栈中的元素，我希望您能弄明白。也不要 System.exit(0); 做 return true;。在方法的底部，返回 false。我没有测量性能影响，但我希望与不记录任何内容相比它是微小的。现在您可以获得如下输出:

1 frog/s jump from 3 to 4
1 frog/s jump from 7 to 6
2 frog/s jump from 6 to 4
4 frog/s jump from 4 to 0
5 frog/s jump from 0 to 5
6 frog/s jump from 5 to 11
1 frog/s jump from 8 to 9
2 frog/s jump from 9 to 11
9 frog/s jump from 11 to 2

为了完整起见，最后我是这样做的。我没有从您的代码中发现任何有趣的差异。

public static void jump(int[] world) {
    for (int fromIndex = 0; fromIndex < world.length; fromIndex++) { // index of pad to jump from
        // any frog/s here?
        int frogsJumping = world[fromIndex];
        if (frogsJumping > 0) {
            // try to jump left; frogsJumping frogs jump frogsJumping places
            int targetIndex = fromIndex - frogsJumping;
            if (targetIndex >= 0 && world[targetIndex] > 0) { // must not jump to empty pad
                performJump(fromIndex, targetIndex, world, frogsJumping);
            }
            // try a right jump
            targetIndex = fromIndex + frogsJumping;
            if (targetIndex < world.length && world[targetIndex] > 0) {
                performJump(fromIndex, targetIndex, world, frogsJumping);
            }
        }
    }
}

private static void performJump(int fromIndex, int toIndex, int[] world, int frogsJumping) {
    solution.push(new Jump(frogsJumping, fromIndex, toIndex));
    world[fromIndex] = 0;
    world[toIndex] += frogsJumping;
    if (world[toIndex] == noOfFrogs) {
        System.out.println("Solved: " + Arrays.toString(world));
        System.exit(0);
    }
    jump(world);
    // backtrack
    world[toIndex] -= frogsJumping;
    world[fromIndex] = frogsJumping;
    solution.pop();
}