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!!!!

Perhaps if you told us the real problem, somebody might be willing and
able to help.  But please bear in mind that many readers of this news
group don't take kindly to people asking for help with their homework
unless a reasonable attempt has already been made (e.g. post what you've
done and ask for help or advice overcoming specific problems).  Asking
for a complete program often results in "help" of a fairly unhelpful
variety.

Cheers,
Warwick

the tile locations are represented as follows

map(region1,[region2,region3]).
map(region2,[region1,region3,region4,region5,region6,region7]).
map(region3,[region1,region2,region4,region5]).
map(region4,[region2,region3,region5]).
map(region5,[region2,region3,region4,region7,region8]).
map(region6,[region2,region7]).
map(region7,[region2,region5,region6,region8]).
map(region8,[region5,region7]).

colour_map(X,Solution):-

x begin the number of tiles.

if anyone has done this before i would like to look at the code to compare
to my own
mine is rather long and dosent work.

Advice:

1. Choose a random starting tile (A). Chose a color for it.

2. Fill the tiles that surround tile A with the rest of the colors. Go
clockwise. On every step check if the surrounding tiles has the same color
as the current - If so take next color from the list and check again.

3. Go to the next tile in a list.

The colored tile problem could be solved by recursion (Prolog is very good
for this purpose)

It is proven that there is always a solution when minimum 4 colors are used.

--
(`'`'`'`)       Geoffrey Summerhayes
 |     |   ------------------------------
 |    ``   (defun mail-to()
(c---()()   (apply #'concatenate 'string
 |    __)    (mapcar #'reverse

/_____/#\       "liamtoh" "." "moc" ))))

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

i looks like i have two options then
either develop a non recursive or recursive version

the recursive version being more difficult to code
but it will let me generate alternative colour arrangements
using backtracking.

my main problem is that i cant get my head around
the basic prolog coding technigues.

anyway thanks again!!!