JavaScript: constraint satisfaction by backtracking

Before you start

JavaScript recursion and objects.

Color a map so that neighbouring regions differ, counting every valid coloring.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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

Behind the scenes

How JavaScript processes this code

A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.

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.