"непонятно как это имплементироваить иначе как полным перебором вариантов."

Ты быстро нащупал слабое место Prolog :)

Это backtracking с перебором. А чтобы перебор не вылиывался в экспоненту - в реализацию добавляются хаки / прагматы / форсирование порядка перебора.