Be careful how you call your predicates.
colour_countries/1 example in Section 13.4
the order in which countries are coloured makes a big difference to
the speed of solution. You can test this by changing the order
of clauses for
ngb/2, which gives the neighbouring countries.
The general principle is to select the (potentially) most
difficult countries and colour them first. The ones likely to be
most difficult are the ones with most neighbours.
(See Bratko, ``Prolog Programming for AI'' for a detailed discussion of
efficiency for the map colouring problem).