I wonder home much efficient solution will be if written in the logic programming language like Prolog.

PS. Find this one, but did not run any analysis yet: https://github.com/nablaa/rushhour-solver-prolog