== 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.