蛮力迫使青蛙跳跃游戏

Question

---

青蛙跳跃的最后一个变化显示在视频的末尾。

简而 每一个。

在最后一个变化中（我想暴力的一种），第二个 第一个和第二个莉莉垫没有青蛙。您的目标是 将所有青蛙放在同一个百合垫上。每只青蛙可以向右或向左跳 基于其百合垫上的青蛙数量，但无法跳上 空的百合垫。
（带有1个青蛙的垫子1个斑点，带有N青蛙移动的垫仅 n点）

n = 12的解决方案的示例：（12以下没有解决方案）

[1,0,1,1,1,1,1,1,1,1,1,0,1] - 青蛙的起始形成。（数数 青蛙从0。至11。）
[1,0,1,0,2,1,1,1,1,1,1,0,1] - 青蛙3.跳跃 右
[1,0,1,0,2,1,2,2,0,1,1,0,1] - 青蛙7.跳跃左
[1,0,1,0,4,4,1,0,0,1,1,0,1] - 青蛙6.跳跃左
[5,0,1,0,0,0,1,0,0,1,1,0,1] - 青蛙4.左跳跃
[0,0,1,1,0,0,6,0,0,1,1,0,1] - 青蛙0 [0,0,1,1,0,0,0,0,0,1,1,0,7] - 青蛙5.右跳
[0,0,1,1,0,0,0,0,0,0,2,0,7] - 青蛙8.右跳跃
[0,0,0,1,0,0,0,0,0,0,0,0,9] - 青蛙9.右跳
[0,0,0,10,0,0,0,0,0,0,0,0,0] - 青蛙11.跳过左求的

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

我尝试编写一件代码，该代码将通过所有组合运行，以找到 n Lily Pads的解决方案。

编辑：借助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 （除13以外的所有n> 11，都有一个解决方案，可通过广义方法达到）。这件代码只是我试图在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是另一个选项。）现在，在您的代码中，它说log the jump do

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

在 log the rollback do

                    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％的时间。我想说这是可以接受的。如果您非常担心性能，则只能从找到解决方案的情况下登录。这将要求您返回布尔值以指示成功，而不是使用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();
}