OJ Board

I wonder how to do it in less than 2 secs. It takes me at least 7 secs to generate all possible states. There are exactly 3674160 states not considering the 24 rotations of the cube.

3674160 is indeed the number of states, but don't try to generate all of them. The key observation is that the distance between two most distant states is 14.
To get it within 2 secs you also have to think of the best way to represent the cube in your program so that rotations are performed easily. It's also useful to be able to transform state in an unique integer and to do it fast.
Good luck!

I have devised a way of represent each state using an integer less than 3674160, and I have precomputed the set of state transitions.

There are only 6 quarter turns, so for each state in the bfs, I only need to consider the 6 possible next states.

But still, the bfs runs for more than 6 secs. My bfs has 3674160 iterations through the loop, how come 6*3674160 takes 6 secs to run? My program runs for more than 8 secs.

but don't try to generate all of them

Why do you say don't try to generate all of them, then how can I know what is the distance between 2 states? Is it possible to just bfs starting from the final state to the initial state?

It won't be feasible if the number of required quarter turn is 14, since I would have to visit more than 99% of the states anyway. (there are only 276 states which requires 14 quarter turns to reach)

Perhaps it will run faster if I just assume all states to be distance 14 initially, and quit the bfs once I process states of distance 13. I guess i'll have to try that optimazation. (I've reduced the number of operations in my main loop, but my time is still more than 5 secs, maybe that's because there are more than 2000000 states that are at least distance 11 away)

It's interesting to note that there are 28 AC but only 5 people that solved it.

Try searching from both initial and final state. The technique is called meet-in-the-middle.
Let A[X] be distance from initial state to state X and B[X] be distance from final state to state X. If you can find some state X that is reachable from both initial and final state then you can get from initial state to final in A[X] + B[X] moves.
Since the maximum distance is 14 then there must be some state X such that A[X] + B[X] is minimal and A[X] <= 7 and B[X] <= 7. So you'll only have to search to the depth 7 in your BFS. The number of states within 7 moves from any state is about 45000.

I get TLE for this problem.
How to make the whole state in ONE integer? I am using 4 integers. And I do not think that I will pass even if I do this. I made meet in the middle attack as described, but it takes a long time also for number of steps = 6 or 7.
I am making BFS and I do not generate anything twice. However, I generate everything reached by BFS. I think I should use some heuristic. Can you help me please?

kalinov wrote:Try searching from both initial and final state. The technique is called meet-in-the-middle.
Let A[X] be distance from initial state to state X and B[X] be distance from final state to state X. If you can find some state X that is reachable from both initial and final state then you can get from initial state to final in A[X] + B[X] moves.
Since the maximum distance is 14 then there must be some state X such that A[X] + B[X] is minimal and A[X] <= 7 and B[X] <= 7. So you'll only have to search to the depth 7 in your BFS. The number of states within 7 moves from any state is about 45000.

Thanks for the help. I'm too lazy to modify my bfs to do it. I've optimized the code to just below 4 secs.

I'll give some hint to my approach for making state into 1 integer.
We'll number the blocks from 0 to 8 for further reference (doesn't matter what the numbering scheme is) The blocks are all different, and you can tell them apart from the set of 3 colors on them.

Let's also label the corners of the cube from 0 to 8. Then we get 8 numbers a such that a represents the block that lies in corner i. Now observe that we can fix a[0]=0, since we can define it to line up corner 0 and block 0 (since we defined the corner numbering only using a unspecified reference point, and we're given that the position are all valid) Thus, there are only 7! values for the a. It is easy to encode them in an integer less than 7!.

Now, for each corner, pick one of the face to be a reference direction. For each block, we also pick a reference face. We define b to be the number of clockwise rotation of the block at position i (about the corner) needed to line up the reference face with reference direction. There are 3 possible values for each b. (they take values 0,1 or 2)

Again, we can assume b[0]=0 by choosing a suitable definition of the reference direction and reference faces. We can show that each quarter term preserves the sum of the b mod 3, therefore we only need to store 6 of the values of b, then b[7] could be computed from the rest.
The b can be encoded in an integer less than 3^6.

Summary: a -> integer less than 7!, b -> integer less than 3^6
we can combine them into single integer. (although i didn't do it, since it is slightly slower than using 2 integers.)

If you precomputed all the 6 transitions of the a[i] part, and b[i] part (these are independent of each other), then the bfs should run in less than 5 secs even with the max number of steps = 14. If we restrict to 7 steps, it will run much faster.

I think this problem is clearly way harder than all other problems in this set.

Thank you very much.

can this problem solved with A* searching?

if it can,how?

I don't think A*/IDA* is convenient to this problem.
At least, I didn't use.

Normally, the minicube is solved using either BFS or IDS (iterative deepening depth first search)

I don't know of a good heuristic to solve minicube with A* or IDA*. Anyway, the total number of configurations is not very large, so generating all states should be fast enough. Bidirectional search can speed it up too.

For solving the 3x3x3 normal version of rubik's cube, A* or IDA* needs to be used. The number of states is too large even for bidirectional search. Notice that the 8 corner pieces of the 3x3x3 is equivalent to the 2x2x2 minicube. So the optimal number of move to solve them as a minicube is a good heuristic. There are also heuristic that also considers the edge pieces only. And taking the maximum of any admissible heuristic is also admissible.

It's from the paper "Finding Optimal solutions to Rubik's cube Using Pattern Database" by Richard Korf.

My code was AC in 1.16 sec. I chose to encode both the a and b arrays as described by sclo into a single integer. I rotated the cube as a whole so I could fix a[0] and b[0] to 0. Then the permutation order of a[1-7] is computed as an int less than 7!. Maybe due to my choice of references for a and b, I had to store b[7] into the encoding in addition to b[1-6]. So my integer is less than 7!*(3^7)=11,022,480

I use the BFS meet in the middle approach. I don't precompute anything. The goal is encoded to state 0. After computing the next 6 states for each state in the start array, I qsort, remove duplicates, and look for a match with the end array. Then I do the same thing for the end array and iterate keeping track of the number of steps until you find a match.