I read somewhere that Pattern Matching like that supported by the match/case feature in Scala was actually borrowed from Logic languages like Prolog.
Can you use Scala to elegantly solve problems like the Connected Graph problem? e.g. https://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_15.html
No, you can't do it, unless you actually create a logic engine, which kind of defeats the whole purpose.
Furthermore, pattern matching itself is wholly unsuited for this, for many reasons. Consider, for instance, the basic query itself: path(1, 5, P). In Scala's pattern matching, 1, 5 and P are outputs. You can't provide an input that could be used to produce the output.
With Prolog, this is like, assuming that 1 and 5 are fixed, what possible values could P take on? That's just now how pattern matching works.
Unfortunately, no. Logic programming is another paradigm. However, Scala borrows a lot of concepts from functional programming - it can and should be used in a functional style. Functional and logic programming are both declarative, but differ significantly. You can read more here.
See http://kanren.sourceforge.net/ for details on how functional and logic programming aren't really all that far apart. Stream structures are the key to understanding how the two paradigms can come together. By "lifting" standard functions into a stream/logic format, they can exhibit problem solving behavior that looks a lot like Prolog.
You should also look at parser combinators. With the right combinators in place, efficient Prolog-like solving capabilities are possible.
I know I am late but searching re: kanren I found this http://scala.sygneca.com/code/mini-kanren There is also this: http://code.google.com/p/scalalogic/
I am just researching the topic and only have a very dim understanding of it but the links may be of some interest anyway.
Haskell and Functional Programming Languages have been the direct source of inspiration for Scala. One of the applications inherited from those languages is the development of Domain Specific Languages (DSLs). There are quite a few DSLs for Logic Programming (Prolog) in Haskell. It should be quite possible to port such a DSL library to Scala, if that has not happened yet.