ブルートフォースジャンプゲームを強制する

Question

---

the videoの最後には、カエルジャンプの最後のバリエーションが表示されます。要するに

は、あなたが持っている N行のユリパッドの数と それぞれ一対一カエル。

最後のバリエーション（私は強引にしたいもの）で、第2の 最後のリリーパッドにはカエルがありません。あなたの目標は 同じリリーパッドにすべてのカエルを得ることです。各カエルは、その白いパッドのカエルの数に基づいて右または左に移動することができますが、 空のリリーパッドでジャンプすることはできません。
（1つのカエル移動する1つのスポットとパッド、n個のカエルとパッドがのみ Nスポット移動）は、n = 12のための溶液の

例：

[1（12以下は解が存在しない）を、 0,1,1,1,1,1,1,1,1,1,0,1] - カエルの形成を開始する。 （0~11の卵を と数える）
[1,0,1,0,2,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,0,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つの解決策があり、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について解くた（13以外の全てのn> 11は、一般的な方法によって到達可能な溶液を、持っています）。このコードはJavaで再帰を試みているところです。

Answer 1

うまくいけばうれしいです。私は今あなたが私のコードを必要とは思わないが、私はこの答えの一番下にある場合に与えるだろう。

まず、どのように解決策を記録しますか？私はあなたが最終結果が[0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0]だったことを知っていることは興味深いものではないと思っていると思います。私たちはそれがどのように得られたのか知りたいです。私は2つの方法を提示します。

簡単な方法は、各ステップを試して保存し、バックトラッキングするときに削除するという簡単な方法です。次に、ソリューションに到達すると、それにつながる手順も保存されています。スタックまたは類似を使用します。

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; 
    } 
} 

私のソリューションで試したところ、1回の検索で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(); 
}