Colored Cube 8-Puzzle

Eight cubic dice sit on a 3×3 board; exactly one of the nine cells is empty.

Every die is colored so that each pair of opposite faces shares one color, and the three pairs of faces use the three distinct colors blue, white, and red. All eight dice start in the same orientation: white is on the top (and bottom) face, red is on the two faces pointing toward the top and bottom edges of the board (north and south), and blue is on the two faces pointing toward the left and right edges (east and west).

A die may be rolled into an orthogonally adjacent cell only when that cell is empty. Rolling the die 90° tips it over one edge into the empty cell, and the cell it came from becomes the new empty cell. Rolling toward the north or south edge swaps the die's top color with its north/south face color; rolling toward the east or west edge swaps its top color with its east/west face color.

The puzzle is solved when the top face of every die matches its given target color and the empty cell is at its target position.

Given the initial empty cell and the target colors, output the minimum number of rolls needed to solve the puzzle.

The input contains several test cases. The first line of each test case gives the coordinates of the initially empty cell: the column (1 to 3, counted from the left) followed by the row (1 to 3, counted from the top). The next three lines describe the target board, one row from top to bottom, three space-separated symbols per line. Each symbol is one of B (blue), W (white), R (red), or E. The single E marks the cell that must be empty in the solved board, and exactly one E appears.

The input ends with a line containing "0 0". There are fewer than 16 test cases.

For each test case, print on its own line the minimum number of rolls required to solve the puzzle. If that minimum exceeds 30, or the puzzle cannot be solved, print -1.