GODNIS20 - God Number is 20 (Rubik)

The Rubik's cube is the most popular toy in the world. Some even consider it as sport, since it requires dedication and training to master it. Also, there are competitions all over the world. There are many ways to compete: 3x3x3 (Rubik's cube), 2x2x2, 3x3x3 blindfolded, 4x4x4, etc. Usually, a speed cuber takes between 50 and 60 move to solve it, using Fridrich method. Fridrich (or CFOP) is a fast method, but requires a big effort for memorization. There are other methods like Roux (~48 moves), Petrus (~45 moves), ZZ (~50 moves) which requires fewer moves, but CFOP is still faster. There are other popular methods like Old Pochmann (~350 moves) ans M2/R2 (~150 moves). They are intended for blindsolving, since you can solve one piece at time.

 

A group of researches showed, by brute force, that any of the 43,252,003,274,489,856,000 positions of the Cube can be solved with at most 20 moves (half turn metric), now, "God Number is 20". The algorithm that always find the optimal solution for the cube is known as God's Algorithm, and it is just theoretical by these days.

 

Note: due to some abuses, in June 10th, 2016, a new judge was added. This one generates random cubes every time, although the n is fixed for every user. You can see the scrambles that generated the cubes you've got by clicking your score.

 

Input

First line, you have n<100, the number of cubes to be solved. You will be given n valid scrambled cube position, as in the sample, with default orientation (white on top, green on front).

 

The cube's faces are represented like:

 U

LFRB

 D

 

Ouput

You have to output the length of your solution, then the solution (at most 1000 face turns). Any valid sequence that solves the cube will be accepted. If you want to skip a particular cube, you have to print "-1" instead of the solution length. The penalty for that is 1000 moves, although if you skip all the cases, you will get WA. Every move must be in HTM, without cube rotations or double rotations, i. e., the only accepted moves are {U, F, R, ...} and {U2, U', F2, F', ...}.

 

Score

Score is the sum of the moves plus penaties.

 

Sample Input

      W W W

      W W W

      O O O
O O Y G G G W R R B B B
O O Y G G G W R R B B B
O O Y G G G W R R B B B
      R R R
      Y Y Y
      Y Y Y
      R W G
      W W W
      W W O
G R R B G W B B W O O W
O O O G G G R R R B B B
O O O G G G R R R B B B
      Y Y Y
      Y Y Y
      Y Y Y
      G R B
      O W G
      O O G
W G Y G Y W O R O W W R
Y O O B G G Y R W O B B
Y G R B Y B R W Y B R R
      Y R W
      W Y B
      G B O

3

      W W W

      W W W

      O O O

O O Y G G G W R R B B B

O O Y G G G W R R B B B

O O Y G G G W R R B B B

      R R R

      Y Y Y

      Y Y Y

      R W G

      W W W

      W W O

G R R B G W B B W O O W

O O O G G G R R R B B B

O O O G G G R R R B B B

      Y Y Y

      Y Y Y

      Y Y Y

      G R B

      O W G

      O O G

W G Y G Y W O R O W W R

Y O O B G G Y R W O B B

Y G R B Y B R W Y B R R

      Y R W

      W Y B 

      G B O

 

Sample Output

1

F'

7

R U R' U R U2 R'

-1

 

Sample Score

1008

 

(1+7+1000)

 

Special thanks to Mitch Schwartz, for helping in the custom judge, and Stefan Pochmann, for helping in some glitches.


Added by:campos20
Date:2016-02-13
Time limit:60s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU

hide comments
2017-01-06 19:30:25 Alexandre Henrique Afonso Campos
@David Miliæeviæ

You can copy the input from here (Input section) and paste it in a file to help you out. In respect to the output, you can output the size of the solution, then the solution. Print -1 to skip a cube. Linebreak is optional.
2016-05-18 00:06:28 Alexandre Henrique Afonso Campos
@Siarhei Kulik since you can't use M, S, E, Uw, Fw, etc., the solution will always give white on top, green on front. U, F, L, R, B, D won't affect center pieces.

Last edit: 2016-05-18 00:07:07
2016-05-17 03:08:53 Siarhei Kulik
Is the result considered correct in case, for example, the upper side is not completely white (but, for example, is yellow)? Is there any standard painting pattern that we should obtain for the cube in final, or the only requirement is "every side painted in one color"?
2016-05-11 22:12:19 Alexandre Henrique Afonso Campos
Every case is formated exactly like the sample. If you are not sure about the piece positions, use sample 2 to test.

Last edit: 2016-06-07 16:17:33
2016-05-07 19:33:09 David Miliæeviæ
Can anyone explain in more details how input and output are formatted, since I'm not sure if I got it correctly?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.