Die gängigen Prolog-Solver sollten bedeutend besser sein als alles, was man mal eben so zusammen schustert.
NP-Komplett bleibt NP-Komplett, egal in welcher Sprache. Sofern Du in Prolog keine Optimierungen (pruning) formulierst, wirst Du genauso lange warten.
Da Rekursion einer der zentralen Deklarationsmetapher von Prolog ist, dürfte die Implementierung auch alles andere als Obersuperoptimal sein, obwohl ein Prolog-Interpreter
tail recursion iterativ auflösen sollte.
Prolog wird teilweise bei Expertensystemen eingesetzt, sodass man hier prüfen müsste, inwieweit der TE ein derartiges System benötigt.