Twilight Zelda Guardian Puzzle : Shortest Path (UPDATE: ADDED RULES) I'm playing a video game right now and in it is a puzzle (see here). There are solutions to solving it (see here) on the Internet, but I'd like to know if this path is the shortest path (least amount of moves) possible to solve the puzzle.
The rules of the game are clear from the video. There is a grid of nodes. The border nodes are bounded with limited path choices. There are three moving bodies. The main one chooses a path that reflects the path choices of the other two. The aim is to guide the other two to land on certain nodes at the same time.
IMPORTANT RULES:

If the guardians face each other and Link, the player, moves in a way to make them collide they, in effect, stay in the same position and Link keeps his move: youtube.com/watch?v=ZNnSwc0w1oE#t=4m58s
Top-guardian-Link conga allowed: youtube.com/watch?v=oUh88KsZYCc#t=3m53s –  Liz Wesley 21 mins ago
The game ends if the player jumps on a square that a guardian is set to jump on at the same time: youtube.com/watch?v=ZNnSwc0w1oE#t=2m55s

I'm seeking a shortest path proof based on this game's rules. Any help would be appreciated.
It is important to note that the top guardian moves in the opposite direction as link and the bottom guardian mimics Link's direction.

Daniel Wagner's 12-step Haskell Solution:

Guardian Path Overlay:

 A: Under a few assumptions, I compute that the shortest path requires 12 steps; the player should make the moves ESNNNWWSSSEN. (This is one step shorter than the two solutions you linked to.) The assumptions I made are:


*

*Entities which would step out of the game board do not move.

*All three entities step simultaneously.

*The player may not make a move which would cause an entity to change their location to one that is currently occupied. (Remaining in place is okay.)

*The player may not remain in place.

*The player may not make a move which would cause two entities to occupy the same cell.


Below I include a full code listing (in Haskell) which describes the game and performs A* search as implemented by the astar package to find a minimal path. As a heuristic, we consider the two ways of pairing guardians and goal cells; in each pairing, we compute the Manhattan distance of the guardian that has farther to walk, then take the smaller maximum distance from these two pairings. This is certainly admissible, since we must take at least as many steps as the guardians are away from their goal cells. Assumption (1) is encoded in stepValid; (2) in unsafeMove; (3)-(5) in movementIsValid. Shorter solutions may be possible if these assumptions are incorrect.
import Data.List
import Data.Graph.AStar
import Data.Ord
import Data.Set (Set, fromList)

type Position = (Int, Int)
data Direction = N | E | S | W deriving (Eq, Ord, Read, Show, Bounded, Enum)

allDirections :: [Direction]
allDirections = [N, E, S, W]

mirror :: Direction -> Direction
mirror N = S
mirror E = W
mirror S = N
mirror W = E

dx, dy :: Direction -> Int
dx E =  1
dx W = -1
dx _ =  0
dy N =  1
dy S = -1
dy _ =  0

step :: Direction -> Position -> Position
step d (x, y) = (x + dx d, y + dy d)

data Configuration = Configuration
    { valid :: [Position]
    , goalA :: Position
    , goalB :: Position
    } deriving (Eq, Ord, Read, Show)

data State = State
    { player         :: Position
    , guardianSame   :: Position
    , guardianMirror :: Position
    } deriving (Eq, Ord, Read, Show)

stepValid :: Configuration -> Direction -> Position -> Position
stepValid c d p
    | p' `elem` valid c = p'
    | otherwise = p
    where p' = step d p

unsafeMove :: Configuration -> Direction -> State -> State
unsafeMove c d State { player = p, guardianSame = gs, guardianMirror = gm } = State
    { player         = stepValid c d p
    , guardianSame   = stepValid c d gs
    , guardianMirror = stepValid c (mirror d) gm
    }

movementIsValid :: State -> State -> Bool
movementIsValid old new
    =  player         new `notElem`                             oldPositions
    && guardianSame   new `notElem` delete (guardianSame   old) oldPositions
    && guardianMirror new `notElem` delete (guardianMirror old) oldPositions
    && nub newPositions == newPositions
    where
    newPositions = [player new, guardianSame new, guardianMirror new]
    oldPositions = [player old, guardianSame old, guardianMirror old]

movements :: Configuration -> State -> Set State
movements c old = fromList
    [ new
    | d <- allDirections
    , let new = unsafeMove c d old
    , movementIsValid old new
    ]

manhattan :: Position -> Position -> Int
manhattan (x, y) (x', y') = abs (x-x') + abs (y-y')

heuristic :: Configuration -> State -> Int
heuristic c s = min
    (max (manhattan (guardianSame s) (goalA c)) (manhattan (guardianMirror s) (goalB c)))
    (max (manhattan (guardianSame s) (goalB c)) (manhattan (guardianMirror s) (goalA c)))

cost :: State -> State -> Int
cost _ _ = 1

finished :: Configuration -> State -> Bool
finished c s = heuristic c s == 0

data Cell = Player | Goal | GuardianSame | GuardianMirror | Valid
    deriving (Eq, Ord, Read, Show, Bounded, Enum)

label :: String -> [(Position, Cell)]
label board = do
    (y, row)  <- zip [0..] (reverse (lines board))
    (x, char) <- zip [0..] row
    let cell c = [((x, y), c)]
    case char of
        'x' -> cell Valid
        'g' -> cell Goal
        's' -> cell GuardianSame
        'm' -> cell GuardianMirror
        'p' -> cell Player
        _   -> []

parse :: String -> (Configuration, State)
parse board = (Configuration
    { valid = map fst labels
    , goalA = gA
    , goalB = gB
    }, State
    { player         = p
    , guardianSame   = gs
    , guardianMirror = gm
    })
    where
    labels = label board
    (p, Player):(gA, Goal):(gB, Goal):(gs, GuardianSame):(gm, GuardianMirror):_
        = sortBy (comparing snd) labels

(testConfiguration, testState) = parse
    "xx xx\n\
    \xgmgx\n\
    \xxxxx\n\
    \ xpx \n\
    \ xxx \n\
    \  s  \n"

main = case aStar (movements testConfiguration) cost (heuristic testConfiguration) (finished testConfiguration) testState of
    Nothing       -> putStrLn "no solution exists for the test board"
    Just solution -> mapM_ print solution

