import java.util.*; /** * Use heuristics to guide the solution towards states that are closer to being solved. * Use rotations of one ring followed by either a rotation of a different ring or a "swap 3" sequence of moves * that swaps 3 beads in one outer ring for 3 beads in another outer ring. * * This can sometimes get stuck in local minima, so perform a random additional move if we get stuck and repeat * until we arrive at the solved state. If the total number of moves exceeded the bound, then just try the * whole thing again. * * @author Finn Lidbetter */ public class magicbeancube_finn { static int MOVES_MAX = 240; static int TOP = 0; static int LEFT = 1; static int RIGHT = 2; static int CENTER = 3; static Move[] trSwap3; static Move[] rlSwap3; static Move[] ltSwap3; static Move[][] swap3s; static Move[][] moves; public static void main(String[] args) { Scanner sc = new Scanner(System.in); // state[0] is the Top // state[1] is the Left // state[2] is the Right char[][] state = new char[3][10]; state[TOP] = sc.nextLine().strip().toCharArray(); state[LEFT] = sc.nextLine().strip().toCharArray(); state[RIGHT] = sc.nextLine().strip().toCharArray(); moves = new Move[4][]; moves[TOP] = new Move[9]; moves[LEFT] = new Move[9]; moves[RIGHT] = new Move[9]; moves[CENTER] = new Move[2]; moves[CENTER][0] = new Move(CENTER, 1); moves[CENTER][1] = new Move(CENTER, 2); for (int i=0; i<3; i++) { for (int j=1; j<=9; j++) { moves[i][j-1] = new Move(i, j); } } State curr = new State(state, null, 0); trSwap3 = new Move[]{moves[CENTER][0], moves[RIGHT][6], moves[CENTER][1], moves[RIGHT][2], moves[CENTER][0], moves[RIGHT][6], moves[CENTER][1]}; rlSwap3 = new Move[]{moves[CENTER][0], moves[LEFT][6], moves[CENTER][1], moves[LEFT][2], moves[CENTER][0], moves[LEFT][6], moves[CENTER][1]}; ltSwap3 = new Move[]{moves[CENTER][0], moves[TOP][6], moves[CENTER][1], moves[TOP][2], moves[CENTER][0], moves[TOP][6], moves[CENTER][1]}; swap3s = new Move[3][]; swap3s[0] = trSwap3; swap3s[1] = rlSwap3; swap3s[2] = ltSwap3; State result = search(curr); while (result.depth>MOVES_MAX) { result = search(curr); } System.out.println(result.depth); curr = result; Move[] solutionMoves = new Move[result.depth]; while (curr.prevState!=null) { solutionMoves[curr.depth-1] = curr.prevMove; curr = curr.prevState; } char[] chrs = {'o', 'g', 'r', 'c'}; for (Move move: solutionMoves) { System.out.printf("%s%d\n", chrs[move.ring], move.rotations); } } static State search(State curr) { State best = curr; int bestValue = best.evaluate(); if (bestValue==0) { return best; } for (int j=0; j<4; j++) { for (int i=1; i<=9; i++) { if (j==CENTER && i>2) { break; } State intermediate = curr.applyMove(moves[j][i-1]); int intermediateValue = intermediate.evaluate(); if (intermediateValue2) { break; } State other = intermediate.applyMove(moves[k][l-1]); int otherValue = other.evaluate(); if (otherValue