Hexagonal Puzzle

Interview

Time limit1sMemory limit128 MB

Summary
Find the shortest sequence of coin moves on a 7-cell hexagonal puzzle graph to restore each labeled coin to its matching outer cell, or report impossibility.
Level

Medium6 of 10

Topics
BFS, Graph, Implementation
Solved
No attempts yet

Problem

A hexagonal board has six outer cells and one center cell. The outer cells are named A, B, C, D, E, and F in the same order used by the input. Initially the center cell is empty, and the six coins labeled A through F occupy the outer cells.

In one move, choose a coin in a cell connected to the empty cell and move that coin into the empty cell. The cell connections are:

  • outer cycle: A-B, B-C, C-D, D-E, E-F, F-A
  • center cell: connected to B and E

The goal state has coins A, B, C, D, E, and F in outer cells A through F respectively, with the center cell empty.

Given an initial state, find the minimum number of moves needed to reach the goal and one sequence of coins moved in such an optimal solution. If the goal cannot be reached, report that it is impossible.

Input

The first line contains the number of test cases T (1 <= T <= 1000). Each of the next T lines contains one initial state: a length-6 permutation of A through F, listed from outer cell A through outer cell F. The center cell is initially empty.

Output

For each test case, print one line. If the puzzle can be solved, print the minimum move count, one space, and the sequence of moved coin labels. The sequence may be empty when the move count is 0. If the puzzle cannot be solved, print -1.

Examples1

  1. Example 1

    Input
    12
FACDBE
ABCDEF
ADCEFB
ADCEBF
FEDCBA
FEDCAB
ECBFAD
ECBFDA
DCEBFA
DCEBAF
CBEADF
BDEAFC
    Expected output
    5 BEFAB
0 
19 DABFECABFEDBACDEFAB
-1
29 EDCBEDFAEDFAEDBCAFBDEFACDEFAB
-1
19 CBFACBFACDEFACDEFAB
-1
13 CDAFBEDCBEDCB
-1
21 DAEBDAEBDCFEBDCABEFAB
16 FAEDBCAFBCAFEDCB