CODEWITHSUNDEEP
javaalgorithmrecursion
Eric Goto
Eric Goto

Reputation: 63

Optimal solution for Reve's puzzle using recursion

I am trying to figure out how to print out the steps for solving the optimal Reve's puzzle, but I can't seem to figure out the correct reduction step for the recursion.

The reve's puzzle is essentially an extension of the Hanoi problem but with 4 pegs instead of 3. More information here: https://everything2.com/title/Reve%2527s+puzzle

The frame-stewart conjecture says that the k value is k= n+1-sqrt(2*n-1), where n is the total amount of discs we have to move. The step I can't figure out is the recursion for 4 pegs instead of 3. My code for 3 pegs is:

private static void revesStepThree(int n, int topDisc, String from, String temp, String to) {
        if (n == topDisc) return;
        revesStepThree(n - 1, topDisc, from, to, temp);
        System.out.println("Move disc " + n + " from " + from + " to " + to);
        revesStepThree(n - 1, topDisc, temp, from, to);

    }

How can I modify this to work for 4 pegs? Essentially, from the link above, I don't understand steps 1 and 3 (which are pretty much the same step except with different pegs).

Upvotes: 1

Views: 2235

Answers (1)

PhamThanhLongVN
PhamThanhLongVN

Reputation: 31

explain more clearly for your code:

  1. Move the entire (n-1) top plate to the intermediate pile (pile B)
  2. Move the remaining disc from pile A to pile C
  3. Move (n-1) from the intermediate pile B back to pile C.

My answer is for 4 piles:

//by Pham Thanh Long EE2-07 K63 HUST VietNam (ĐHBKHN)
//quick Q, feeling free to contact via gmail: [email protected]
public class Reve {
    private static void hanoi(int n, int k, String from, String temp, String to) {
        if (n == 0) {
             System.out.println();
             return;
        }
        hanoi(n - 1, k, from, to, temp);
        System.out.print("Move disc " + (n + k) + " from " + from + " to " + to);
        hanoi(n - 1, k, temp, from, to);
    }
    private static void rev(int n, String from, String temp, String to, String temp2) {
        int k = (int) (n + 1 - Math.round(Math.sqrt(2 * n + 1)));
        if (k == 0){
            System.out.print("Move disc " + 1  + " from " + from + " to " + to);
            return;
        }
        rev(k, from , to, temp , temp2);
        hanoi(n-k,k, from, temp2, to);
        rev(k,temp,from,to,temp2);
    }
    public static void main(String[] args) {
    int n = 20;
    rev(n, "A", "B", "D", "C");
    }
}

Upvotes: 3

Related Questions