BFS search using queue resulting in shallow copy

Question

The goal
I'm trying to use BFS to make a Rubik's cube solver. I know that it'll probably be slow with all of the ways that it can be permuted. =P It's not for school in case anyone is wondering.

The probably-easy-to-fix problem
Whenever I'm putting another state of the scrambled Rubik's cube into the queue<array> it is just a shallow copy, so once other states of the Rubik's cube are added in, the previous states inside of the queue actually change and match up with the newer states. In other words, how do I make sure that all of the elements inside of the queue<array> remain the same?

Attempts that I have made to fix this
https://stackoverflow.com/a/129395/984680
I basically use this code to create a new copy of the cube when it comes out of the queue, and then I create another new copy before I put it into the queue again (in a different state). The code below shows how a new copy is made before it's inserted into the queue.

    //make deep copy of ccube (char array)
    char[][][] newcube = DeepClone(ccube);
    buffer.Enqueue(new State(newcube, calg + face + " ")); //even though newcube gets put into array, it ends up changed after ccube changes

And this is the deepcopy that's made when the array is pulled out from the front of the queue.

    ccube = DeepClone(buffer.Peek().cube);

Even though I cloned the array so many times (something tells me that I don't need to make so many copies) the newer states that I add in are still the same as the older states. I know this because there are only 2 distinct elements inside of the queue, even though I made all of the faces of the cube turn in every way each time.

Thanks in advance to anyone who is able to help.

score 0 · Answer 1 · answered Jun 09 '13 at 21:26

The problem is that arrays are mutable in C#, i.e. when you change an element at a position you are modifying an existing array instead of generating a new array.

Strings are immutable in C#, and since you are already representing that cube as a char[][][] you can leverage that fact. A bounded orthogonal 3D space is bijectively mappable (1:1) to a bounded 1D space, that is your char[][][] is mappable to a String (as long as the cube's dimensions don't change during the cube's lifetime), so combine that with immutability of strings and you can easily deep-clone your cubes.

public class Cube
{
    public int Width { get; private set; }
    public int Height { get; private set; }
    public int Depth { get; private set; } 

    private string _data;

    public Cube(int width, int height, int depth)
    {
        Width = width;
        Height = height;
        Depth = depth;
        _data = "".PadRight(Width*Height*Depth);
    }

    public char Get(int x, int y, int z)
    {
        return _data[(Width*Height*z) + (Width*y) + x];
    }

    public void Set(int x, int y, int z, char c)
    {
        var sb = new StringBuilder(_data);
        sb[(Width*Height*z) + (Width*y) + x] = c;
        _data = sb.ToString();
    }

    public Cube Clone()
    {
        return new Cube(Width, Height, Depth) { _data = this._data };
    }
}

Whenever you call aCube.Clone() you will get a new cube which is completely unrelated to a previous one, so you can enqueue it in a buffer, etc.

BFS search using queue resulting in shallow copy

1 Answers1