JavaScript: constraint satisfaction by backtracking

Color a map so that neighbouring regions differ, counting every valid coloring.

JavaScript

const regions = ["WA", "NT", "SA", "Q", "NSW", "V", "T"];
const borders = [
  ["WA", "NT"], ["WA", "SA"], ["NT", "SA"], ["NT", "Q"], ["SA", "Q"],
  ["SA", "NSW"], ["SA", "V"], ["Q", "NSW"], ["NSW", "V"],
];
const colors = ["red", "green", "blue"];

function ok(assignment, region, color) {
  return borders.every(([a, b]) => {
    if (a === region && assignment[b] === color) return false;
    if (b === region && assignment[a] === color) return false;
    return true;
  });
}

let count = 0;
let first = null;
function solve(index, assignment) {
  if (index === regions.length) {
    count++;
    if (first === null) first = { ...assignment };
    return;
  }
  const region = regions[index];
  for (const color of colors) {
    if (ok(assignment, region, color)) {
      assignment[region] = color;
      solve(index + 1, assignment);
      delete assignment[region];
    }
  }
}

solve(0, {});
console.log("solutions: " + count);
console.log(regions.map((r) => r + "=" + first[r]).join(" "));

Output

solutions: 18
WA=red NT=green SA=blue Q=red NSW=green V=red T=red

Explanation

A constraint satisfaction problem has variables, domains of possible values, and constraints between variables. Map coloring assigns one of three colors to each Australian region so that no two neighbouring regions share a color.

Backtracking assigns the variables one at a time and checks each new assignment against the constraints. As soon as a choice conflicts with a neighbour, the search abandons that branch, which prunes whole subtrees of hopeless assignments. The program counts all solutions: the mainland has 6, and Tasmania, which has no neighbours, can take any of 3 colors, so there are 18.

Explore the dry run

Guided walkthroughReady

1const regions = ["WA", "NT", "SA", "Q", "NSW", "V", "T"];

2const borders = [

3 ["WA", "NT"], ["WA", "SA"], ["NT", "SA"], ["NT", "Q"], ["SA", "Q"],

4 ["SA", "NSW"], ["SA", "V"], ["Q", "NSW"], ["NSW", "V"],

5];

6const colors = ["red", "green", "blue"];

8function ok(assignment, region, color) {

9 return borders.every(([a, b]) => {

10 if (a === region && assignment[b] === color) return false;

11 if (b === region && assignment[a] === color) return false;

12 return true;

13 });

14}

16let count = 0;

17let first = null;

18function solve(index, assignment) {

19 if (index === regions.length) {

20 count++;

21 if (first === null) first = { ...assignment };

22 return;

23 }

24 const region = regions[index];

25 for (const color of colors) {

26 if (ok(assignment, region, color)) {

27 assignment[region] = color;

28 solve(index + 1, assignment);

29 delete assignment[region];

30 }

31 }

32}

34solve(0, {});

35console.log("solutions: " + count);

36console.log(regions.map((r) => r + "=" + first[r]).join(" "));

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A color is allowed if no neighbour already has it.	`—`	—
Only consistent choices are explored; conflicting ones are pruned.	`—`	—
Backtrack: undo the choice before trying the next color.	`—`	—
6 colorings of the mainland times 3 colors for Tasmania.	`count = 18`	solutions: 18
The first solution found, in the search order.	`count = 18`	solutions: 18 WA=red NT=green SA=blue Q=red NSW=green V=red T=red

Cost and common mistakes

Exponential in the worst case, but pruning reduces it greatly in practice.

Checking constraints only after all variables are assigned would test 3^7 = 2187 combinations. Early checking avoids most of them.
Choosing the most constrained variable first, such as SA, usually prunes even sooner.

Try it yourself

How many solutions are there with only 2 colors?

Reveal answer and reasoning

None, because the three mutually neighbouring regions WA, NT, and SA need three different colors.

JavaScript: constraint satisfaction by backtracking

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading