coloured tiles problem
Author Message
coloured tiles problem

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

Sun, 23 May 2004 18:08:46 GMT
coloured tiles problem

Quote:

> there are 8 tiles each with a different colour
> but no tile can be next to a tile with the same colour

Hey, even I can solve this one!  Just put the tiles down in any order:
since they each have a different colour, they're guaranteed not to be
next to a tile with the same colour!  :)

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
for a complete program often results in "help" of a fairly unhelpful
variety.

Cheers,
Warwick

Sun, 23 May 2004 22:35:11 GMT
coloured tiles problem
yeah forgot to say you can only have 4 colours
each tile cant be next to a tile of the same colour

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.

Sun, 23 May 2004 23:29:31 GMT
coloured tiles problem

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.

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

Sat, 29 May 2004 04:06:07 GMT
coloured tiles problem

Quote:

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

Only under a strict set of conditions. For bonus points, what are they?

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

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

Sat, 29 May 2004 07:59:41 GMT
coloured tiles problem
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!!!!

Sat, 29 May 2004 08:38:16 GMT
coloured tiles problem
WOW!!! thanks to you all...

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

Sun, 30 May 2004 23:59:28 GMT

 Page 1 of 1 [ 7 post ]

Relevant Pages