A mechanical solution for this kind of puzzle can employ backtracking -- one tries every combination of property values and rejects any that violate the constraints. Hopefully, exactly one combination will remain.
Prolog is a programming language which facilitates backtracking. It is based on the work of Kowalski and Colmerauer in the early 1970s and became very popular through the book Programming in Prolog by Clocksin and Mellish.
Prolog tries to establish facts by consulting a knowledge base and proving conclusions. A knowledge base consists of facts and rules.
Alphanumeric identifiers starting with a lowercase letter represent atoms. A predicate looks like a function header with a name and one or more arguments, separated by commas and enclosed by parentheses; it establishes a fact if it only contains atoms:
boy(red). boy(green). boy(blue). girl(red). girl(green). girl(blue).
Prolog input is more or less free format. White space is mostly ignored, comments are as in C. Predicates always are terminated with a period.
An interactive session with a Prolog system concerning these facts can look as follows:
$ pl ?- ['boy.pl']. [ consulting boy.pl... ] yes ?- girl(red). yes
The first input is a strange but traditional way to consult a knowledge base. The second input is a query concerning a fact that is in the database — Prolog answers in the affirmative.
?- girl(orange). no
This fact cannot be established.
?- girl(X). X = red ? ; X = green ?
An alphanumeric identifier starting in an uppercase letter denotes an unbound variable. If this is used as a parameter of a predicate in a query, Prolog searches and answers with a binding for the variable which would establish a fact. If a semicolon is input, Prolog tries to find another binding; a newline will terminate the search.
The facts above establish the possible values for each property in the puzzle. The following fact might indicate that the boy in red dances with the girl in green:
a(red, green).
Variables as parameters of a predicate in the knowledge base are used to create a rule:
b(X, Y) :- boy(X), girl(Y), X \= Y.
If the condition on the right of :- is true it implies the fact on the left. Comma denotes a conjunction, i.e., it is similar to && in Java. \= is a binary operator that returns true if it's arguments do not match; the arguments must be bound before they may be compared.
This rule can be used to check if a boy and a girl might dance together:
?- b(red, green). yes ?- b(red, red). no
The rule can also be used to let Prolog search for suitable partners:
?- b(red, X). X = green ? ; X = blue ? ; no ?- b(X, Y). X = red, Y = green ? ; X = red, Y = blue ?
Rules can be powerful problem solvers:
col(1). col(2). col(3). col(4). col(5). col(6). col(7). col(8).
dif(A, B, C, D, E, F, G, H) :-
A =\= B, A =\= C, A =\= D, A =\= E, A =\= F, A =\= G, A =\= H,
B =\= C, B =\= D, B =\= E, B =\= F, B =\= G, B =\= H,
C =\= D, C =\= E, C =\= F, C =\= G, C =\= H,
D =\= E, D =\= F, D =\= G, D =\= H,
E =\= F, E =\= G, E =\= H,
F =\= G, F =\= H,
G =\= H.
queens(C1, C2, C3, C4, C5, C6, C7, C8) :-
col(C1), col(C2), col(C3), col(C4), col(C5), col(C6), col(C7), col(C8),
dif(C1, C2, C3, C4, C5, C6, C7, C8),
dif(1+C1, 2+C2, 3+C3, 4+C4, 5+C5, 6+C6, 7+C7, 8+C8),
dif(1-C1, 2-C2, 3-C3, 4-C4, 5-C5, 6-C6, 7-C7, 8-C8).
col ensures that it's arguments are small numbers. dif ensures that it's arguments are mutually different. Finally, queen succeeds for any solution to the 8 Queens Problem.