CODEWITHSUNDEEP
javaalgorithmrecursion
Teroxin
Teroxin

Reputation: 13

Recursive determination of all solutions from a cube tower

I have to solve a task to determine all solutions from a cube tower in Java.

Task:
Four cubes with colored surfaces(red, blue, green, yellow) are piled on each other and are rotated, so that none of the four colors appear twice on each side of the walls. I have to develop a system, that will recursively determine all solutions for the cube tower. (compare to a puzzle called "Instant Insanity" https://en.wikipedia.org/wiki/Instant_Insanity)

Iteratively it's relativly easy to solve this puzzle, but the recursive approach is very difficult in my opinion.

Cube-Class: 

private String[] colour;

public Cube() {
    this.colour = new String[6];
    for(int i = 0; i < colour.length; i++) {
        colour[i] = colourRead();
    }
}

I also got two function to rotate the cube horizontally and vertically, a get-function for the colour and and a function to read in the colour for the cube.

Cube-Tower-Class:

private Cube[] cube;
private ArrayList<String> solutions;
private int solutionCounter = 1;

public CubeTower() {

    this.cube= new Cube[4];
    this.cube[0] = new Cube();
    this.cube[1] = new Cube();
    this.cube[2] = new Cube();
    this.cube[3] = new Cube();
    this.solutions = new ArrayList<>();
}

I also got a get-function for the cube and a function to test, if there are duplications of colours on one side of the cube-tower.

I've got no clue, how to write a function to determine all the solutions recursively. Maybe anyone has suggestions how to solve the puzzle. Thanks for your help!

Upvotes: 0

Views: 441

Answers (1)

btilly
btilly

Reputation: 46435

Here is pseudo-code for the recursive approach.

function findAllSolutions(cubeTower):
    if cubeTower is None:
        cubeTower = []
    solutions = []
    if length(cubeTower) < 4:
        for each cube in possible cube rotations:
            cubeTower.push(cube)
            solutions.appendAll(findAllSolutions(cubeTower))      
            cubeTower.pop(cube)
    else:
        if (isValidSolution(cubeTower)):
            solutions.push(copy of cubeTower)
    return solutions

Upvotes: 1

Related Questions