蠻力青蛙跳躍遊戲

Question

---

青蛙跳躍的最後一個變化顯示在the video的末尾。

總之，你有Ñ的在一條線上百合片數目和每 一一青蛙。

在最後一個變種（我想暴力的那個）中，第二個 第一個和第二個睡蓮葉沒有青蛙。你的目標是讓 讓所有的青蛙到同一個睡蓮池。每隻青蛙可以根據其百合花上的青蛙數量向右或向左跳 ，但不能跳上 空的百合花墊。
（墊1個蛙移動1點，墊用正青蛙移動僅Ñ點）對於n = 12的溶液中的

實施例：（有低於12沒有解決方案）

[1,2 0,1,1,1,1,1,1,1,1,0,1] - 開始形成青蛙。 （計數 青蛙從0.到11.）
[1,0,1,0,2,1,1,1,1,1,0,1] - 青蛙3.跳躍 對
[1,0， 1,0,2,1,2,0,1,1,0,1] - 青蛙7.向左跳
[1,0,1,0,4,1,0,0,1,1,0 ，1] - 青蛙6.向左跳
[5,0,1,0,0,1,0,0,1,1,0,1] - 青蛙4.向左跳
[0,0,1 ，0,0,6,0,0,1,1,0,1] - 青蛙0.向右跳
[0,0,1,0,0,0,0,0,1,1,0， 7] - 青蛙5.向右跳
[0,0,1,0,0,0,0,0,0,2,0,7] - 青蛙8.向右跳
[0,0,1， 0,0,0,0,0,0,0,0,9] - 青蛙9.右跳
[0,0,10,0,0,0,0,0,0,0,0， 0] - 青蛙跳了11左手解決

我想找到解決方案對於n青蛙，如果解決方案存在。我知道手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> 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是另一種選擇）現在在你的代碼，它說：log the jump做

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

在log the rollback做

    solution.pop(); 

使用簡單的輔助類Jump可能例如看上去像個e此：

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（）來停止搜索。現在您的遞歸調用變爲：

您以與以前相反的順序獲得解決方案堆棧中的元素，我希望您能夠弄清楚。而不是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(); 
}