Simple NP-complete analyzer of game passability

import Data.Map
import Control.Monad

type Item = String
type Inventory = [Item]
addToInv src dst = dst ++ [i | i <- src, i `notElem` dst]

type Location = (String, Inventory)
locInv (_, inv) = inv
makeLocation name inv = (name, inv)
isFinal (name, _) = name == "End"

type Requirement = Maybe Item
data GameState = GS {gsInv :: Inventory, gsLocation :: Location}

--type GameMap = M.Map (Location, Location) Requirement
type GameMap = Map Location [(Location, Requirement)]

torch = "Torch"
key = "Key"

start = makeLocation "Start" []
end = makeLocation "End" []
room = makeLocation "Dark room" [key]
chest = makeLocation "A huge chest" [torch]

testMap = Data.Map.fromList
     [(start, [(chest, Nothing), (room, Just torch)]),
      (chest, [(start, Nothing)]),
      (room, [(start, Nothing), (end, Just key)])]

passable :: [GameState] -> Bool
passable states | any (isFinal . gsLocation) states = True
                | otherwise = passable $ do
                    GS inv loc <- states
                    let newInv = addToInv (locInv loc) inv
                    (newLoc, req) <- testMap ! loc
                    guard $ canPass req newInv
                    return $ GS newInv newLoc
    where canPass Nothing _ = True
          canPass (Just item) inv = item `elem` inv

main = print $ passable [GS [] start]