== Hex puzzle This problem makes use of a board of hexagonal cells that looks like this: i1 i2 i3 i4 i5 j1 j2 j3 j4 j5 j6 k1 k2 k3 k4 k5 l1 l2 l3 l4 l5 l6 m1 m2 m3 m4 m5 n1 n2 n3 n4 n5 n6 o1 o2 o3 o4 o5 Each cell has up to six neighbors. l3 has neighbors (clockwise) k3, l4, m3, m2, l2, and k2. The board is populated with some number of straight pieces of length 2 and 3. Pieces never overlap, but they can move in the direction of their length, which we will refer to as a "groove". So for example, a piece that starts out on locations l1 and l2 can "slide" over to rest on locations l5 and l6. No valid move can make a piece leave the groove in which it was first found. We write "groove" because "row" doesn't quite capture how the pieces can be situated. Besides the above seven rows of the table, a groove (and thus the pieces in it) can also run along a diagonal direction, like this: e1 d1 c1 b1 a1 f1 e2 d2 c2 b2 a2 f2 e3 d3 c3 b3 g1 f3 e4 d4 c4 b4 g2 f4 e5 d5 c5 h1 g3 f5 e6 d6 c6 h2 g4 f6 e7 d7 Or a groove and its pieces could run along the other diagonal direction: p2 q4 r6 s7 t7 p1 q3 r5 s6 t6 u6 q2 r4 s5 t5 u5 q1 r3 s4 t4 u4 v4 r2 s3 t3 u3 v3 r1 s2 t2 u2 v2 w2 s1 t1 u1 v1 w1 There are a total of 23 grooves on the board, 7 horizontal, and 8 for each diagonal. Grooves vary in length from 2 (out in the corners) to 7 (around the main diagonals). A valid playing move on this board consists of sliding a piece along its groove, either forwards or backwards. There are a few things which are *not* allowed: * Two pieces may never overlap and occupy the same location. (Note that the above three representations of the board actually denote the same board; the three sets of grooves intersect each other.) * A piece may not "push" another piece as it slides; it is simply locked in by that other piece. * A piece may not "jump" over another piece as it slides; it is restricted in its movement by the current positions of the other pieces. * A piece may not rotate, move sideways, or otherwise leave its groove. It's perfectly valid for a groove to contain more than one piece (as long as they don't overlap). For this problem, we will restrict ourselves to initial board configurations with a piece at l1 and l2 (written as "l12"). We call this piece the "bullet". The goal is to slide the bullet to l56, through a valid sequence of moves. Thus, other pieces may have to be moved in order to get the bullet to l56. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. start --> l1 l2 .. .. l5 l6 <-- goal .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. Some initial configurations won't have a solution at all. (For example, the bullet will never get through if there are other pieces in its groove.) Write a program that accepts an initial board configuration on standard input. The format looks as follows: d67 i12 l12 u345 v34 The program should reject any initial board configuration that has illegal piece specifications, contains overlapping pieces, or lacks the bullet at l12. If there is possible solution, the program should output No solution. Otherwise it should output one solution as a sequence of valid moves on this format: u[345 -> 456] d[67 -> 23] u[456 -> 123] v[34 -> 23] l[12 -> 56] A solution doesn't have to be minimal in the number of moves, but it may count in your favor if it is. Even more so if it's minimal in the total distance the pieces were moved. Arriving at a solution quickly is an even more important success metric than minimal solutions.