蛮力青蛙跳跃游戏
Brute Force the Frog Jumping Game
青蛙跳的最后一个变化显示在 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只青蛙的解，如果有解的话。手写知道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.
中做一些递归
很高兴你成功了。我不认为你现在需要我的代码，但我会在这个答案的底部给出以防万一。
首先，如何记录解决方案？我猜你在想，知道最终结果是 [0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0] 并不是那么有趣；我们想知道它是如何获得的。我将介绍两种方式。
更简单的方法是在尝试时存储每个步骤，然后在回溯时将其删除。然后当你得到解决方案时，你也已经存储了导致它的步骤。使用堆栈或类似的：
private static Deque<Jump> solution = new ArrayDeque<>(Level);
（java.util.ArrayDeque 是堆栈和队列的推荐 class；对于堆栈 ArrayList 是另一种选择。）现在在你的代码中，它说 log the jump做
solution.push(new Jump(temp, i, i + temp));
在log the rollback做
solution.pop();
使用一个简单的辅助 class 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% 的时间。我会说这是可以接受的。如果您非常关心性能，只有在找到解决方案后才能登录。这将要求您 return 一个布尔值来指示成功，而不是使用 System.exit() 来停止搜索。现在你的递归调用变成：
if (jump(world)) {
solution.push(new Jump(temp, i, i + temp));
return true;
}
您以与以前相反的顺序获取解决方案堆栈中的元素，我希望您能弄明白。也可以用 return true; 代替 System.exit(0);。在方法的底部，return 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();
}
青蛙跳的最后一个变化显示在 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只青蛙的解，如果有解的话。手写知道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.
中做一些递归很高兴你成功了。我不认为你现在需要我的代码，但我会在这个答案的底部给出以防万一。
首先，如何记录解决方案？我猜你在想，知道最终结果是 [0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0] 并不是那么有趣；我们想知道它是如何获得的。我将介绍两种方式。
更简单的方法是在尝试时存储每个步骤，然后在回溯时将其删除。然后当你得到解决方案时，你也已经存储了导致它的步骤。使用堆栈或类似的：
private static Deque<Jump> solution = new ArrayDeque<>(Level);
（java.util.ArrayDeque 是堆栈和队列的推荐 class；对于堆栈 ArrayList 是另一种选择。）现在在你的代码中，它说 log the jump做
solution.push(new Jump(temp, i, i + temp));
在log the rollback做
solution.pop();
使用一个简单的辅助 class 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% 的时间。我会说这是可以接受的。如果您非常关心性能，只有在找到解决方案后才能登录。这将要求您 return 一个布尔值来指示成功，而不是使用 System.exit() 来停止搜索。现在你的递归调用变成：
if (jump(world)) {
solution.push(new Jump(temp, i, i + temp));
return true;
}
您以与以前相反的顺序获取解决方案堆栈中的元素，我希望您能弄明白。也可以用 return true; 代替 System.exit(0);。在方法的底部，return 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();
}