You have a graph colouring problem.

The graph is a pair <V, E> where V is the set of vertices and E is the

set of edges; that is, E subset V x V. You have a set of colours C.

The problem is to find a set of assignments A: V -> C satisfying the

constraint

forall v1, v2 in V.

<v1, v2> in E => A(v1) \= A(v2)

The most naive approach to finding a solution is to enumerate all

possible assignment sets A, testing each one against the constraint,

until you find one that works. This basic generate-and-test strategy is

prohibitively costly, taking time O(|V^C|).

Prolog pseudo-code for G+T is

solve(Vs, Es, Cs, As) :-

construct_assignment_set(Vs, Cs, As),

test_assignment_set(As, Es).

where construct_assignment_set/3 and test_assignment_set/2 are left as

exercises for the student.

The first optimization to consider is that if a partial set of

assignments A' is inconsistent then so is any completion of A'.

Therefore you can prune your search space early by testing the

constraint against each partial assignment set, backtracking on failure

and going on to extend it on success. This is called Depth First

Search.

Prolog pseudo-code for DFS is

solve(Vs, Es, Cs, As) :-

solve_2(Vs, Es, Cs, [], As).

solve_2([], _, _, As, As).

solve_2([V | Vs], Es, Cs, As0, As) :-

choose_colour(Cs, C),

test_assignment_set([V - C | As0], Es),

solve_2(Vs, Es, Cs, [V - C | As0], As).

You can speed up DFS considerably by using Forward Checking. FC works

by keeping track of the possible assignments to the vertices V' *not*

assigned to by the partial assignment set under consideration, A'. If

at any point we find that some v in V' has no remaining possible

assignments (i.e. all options have been pruned away by the existing

assignments in A') then we know that A' cannot be extended to a

complete, consistent set of assignments.

The pseudo-code for DFS+FC is

solve(Vs, Es, Cs, As) :-

possible_assignments(Vs, Cs, VCss),

solve_2(VCss, Es, [], As).

solve_2([], _, As, As).

solve_2([V - Cs | VCss0], Es, As0, As) :-

choose_colour(Cs, C),

prune_incompatible_possible_assignments(VCss0, VCss, V - C, Es),

solve_2(VCss, Es, [V - C | As0], As).

where prune_incompatible_possible_assignments/5 should fail if all the

options for any vertex are pruned away.

FC typically makes an *enormous* difference to the speed of DFS.

- Ralph

Quote:

> Hello all

> is anyone familiar with the coloured tiles problem?

> there are 8 tiles each with a different colour

> but no tile can be next to a tile with the same colour

> does anyone know where i can find a prolog

> program that will solve this problem???

> ive hit a bit of a brick wall at the mo coz im knew

> to this language.

> any help would be GREAT!!!!