In my book "Pattern-Based Constraint Satisfaction and Logic Puzzles" (PBCS), I have a chapter on map colouring, but I've never given an example on this forum of how my approach works for this problem.
However, I think map colouring is the simplest illustration of my general approach.
Here is a simple example:
Countries are numbered from 1 to 30, some of the countries are already coloured, and the goal is to colour all the countries (using 4 colours), in such a way that any two adjacent countries have different colours (adjacent means they have a common border - a single point is not a common border).
You can find many similar examples on Tatham's website: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/map.html.
The CSP-Variables of the problem are the countries (noted as Xk), the values they can take are R, G, B, Y (on the Tatham map, B appear as dark brown; R as light brown). A candidate is a pair (country, colour). Two candidates are linked if
- either their two countries are adjacent and they have the same colour
- or they have the same country but different colours.
(that's the standard meaning of a link in my approach: a direct contradiction between two candidates).
Here is the resolution path in W7 for this puzzle. It shows bivalue-chains, t-whips and whips in action.
- Code: Select all
single ==> X2 = R
biv-chain[2]: X23{Y G} - X24{G Y} ==> X27 ≠ Y
single ==> X27 = B
t-whip[3]: X4{G Y} - X15{Y R} - X17{R .} ==> X18 ≠ G
t-whip[6]: X4{G Y} - X15{Y R} - X17{R G} - X23{G Y} - X20{Y B} - X12{B .} ==> X6 ≠ G
whip[6]: X4{Y G} - X12{G B} - X13{B G} - X20{G Y} - X17{Y R} - X18{R .} ==> X6 ≠ Y
whip[6]: X23{Y G} - X17{G R} - X15{R Y} - X4{Y G} - X12{G B} - X18{B .} ==> X20 ≠ Y
t-whip[3]: X20{B G} - X23{G Y} - X25{Y .} ==> X22 ≠ B
t-whip[3]: X20{B G} - X22{G Y} - X13{Y .} ==> X12 ≠ B
biv-chain[2]: X4{Y G} - X12{G Y} ==> X18 ≠ Y
t-whip[7]: X23{Y G} - X20{G B} - X25{B Y} - X22{Y G} - X13{G Y} - X12{Y G} - X4{G .} ==> X17 ≠ Y
biv-chain[3]: X17{G R} - X18{R B} - X20{B G} ==> X23 ≠ G
single ==> X23 = Y
single ==> X24 = G
biv-chain[2]: X25{G B} - X20{B G} ==> X22 ≠ G
single ==> X22 = Y
biv-chain[2]: X13{G B} - X20{B G} ==> X12 ≠ G
stte
(solved in 0.004s)
