Sequence generation/ breadth first searching

Question

Essentially what I'm doing is trying to solve a Rubik's cube with a breadth first search of all possible moves. I know this isn't the best way to solve the cube, but I only need it for very short sequences (so the depth of the search is unlikely to be deeper than 3), and I don't need to store anything other than the current sequence.

I'm trying to find a way of printing out ever increasing strings of number (0,1,2,00,01,02...), so I can just plug each one into a function to check if that particular sequence of moves solves the cube, but I'm having trouble finding a way of continuing the sequence indefinitely.

So far all I've managed is nested for loops, but there needs to be another loop each time the search gets deeper. Does anyone have any idea how I can approach this problem?

Sorry if I've been too vague, I could write an essay on what I'm trying to do but thought I'd try and keep it simple.

Answer 1

I'm not very familiar with what's in the Java libraries, so apologies if this is implementing something that is already there, but if I were writing this from scratch, I'd probably do something like this:

public class Enumerator {
    private int maxDepth;
    private int currentDepth;
    private int currentPerm;
    private String alphabet;

    public Enumerator(String alphabet, int d) {
        this.maxDepth = d;
        this.currentDepth = 1;
        this.currentPerm = 0;
        this.alphabet = alphabet;
    }

    public boolean next() {
        int numPermutations = (int) Math.pow(alphabet.length(), this.currentDepth);
        boolean res=false;

        // finished if
        if ((this.currentDepth == this.maxDepth) && 
            (this.currentPerm == numPermutations - 1)) {
            res = false;
        }
        // next perm at this depth
        else if (this.currentPerm < numPermutations - 1) {
            this.currentPerm++;
            res = true;
        }
        // next depth
        else if (this.currentDepth <= this.maxDepth) {
            this.currentDepth++;
            this.currentPerm = 0;
            res = true;
        }
        return res;
    }

    public String getPermutation() {
        int tmpPerm = this.currentPerm;
        String res = "";
        for (int i=0; i<this.currentDepth; i++) {
          int ind = tmpPerm % this.alphabet.length();
          res = this.alphabet.charAt(ind) + res;
          tmpPerm /= this.alphabet.length();
        }
        return res;
    }

    public static void main(String args[]) {
        int depth = 3;
        String alphabet = "012";
        Enumerator e = new Enumerator(alphabet, depth); 
        do {
            System.out.println(e.getPermutation());
        } while (e.next());
    }
}

That way you can enumerate sequences from alphabets of arbitrary symbols to an arbitrary depth. This also does what you want insofar as it iterates over depth and for each depth generates the full set of possible sequences. It could also be done with recursion, as Gian says, which might be more elegant. In Python I'd use a generator function for this, but I'm not familiar with anything similar in Java.

Answer 2

Sounds like you want a recursive solution, such that your function generates a list of successor moves given a sequence as input, in which case you can just keep calling the function on its own output as many times as is necessary.

Answer 3

Wouldn't a recursive function do this? You can limit the depth of recursion and gradually deepen it.

[Update] Pass the function an int specifying the depth; each time you recurse, decrement the value - check if it is zero, and return if so.

For the values, pass a collection of strings or stringbuilders into the recursive function. Each level reads (and removes) the values from the previous level, appends all possible next moves and places the results back in the collection (in fact, you could do this iteratively rather than recursively if you wanted).

Level 1 generates 0,1,2,...

Level 2 removes 0 and replaces it with 00,01,02,...
Level 2 removes 1 and replaces it with 10,11,12,...
etc

Answer 4

A FIFO queue might be a better approach than recursion, as suggested by the Wikipedia article on breadth-first search: http://en.wikipedia.org/wiki/Breadth_first_search.

My solution in C#:

string SolveRubiks()
{
    string[] singleMoves = {"0","1","2"};
    Queue<string> queue = new Queue<string>(singleMoves);
    while (true)
    {
        string moveSequence = queue.Dequeue();
        if (isSolution(moveSequence))
        {
            return moveSequence;
        }
        foreach (string singleMove in singleMoves)
        {
            queue.Enqueue(moveSequence + singleMove);
        }
    }
}

If you need an iterator, you can swap the if block with a yield return and change the method signature, in Java I guess you'll have to implement an iterator interface (similar to Philip Uren's class).