Backtracking

Four Queens Backtrack

Follow an ordered 4-queens backtracking trace. This is a small deterministic example, not solver engineering.

Example

Follow an ordered 4-queens backtracking trace.

highlighted = computed this step

Step 1 — Branch

Compute the highlighted combinatorics value.

cell, verdict((0, 0), place)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((0, 0), place)}}\end{array}

Step 2 — Branch

Compute the highlighted combinatorics value.

cell, verdict((1, 1), reject diagonal)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((1, 1), reject diagonal)}}\end{array}

Step 3 — Branch

Compute the highlighted combinatorics value.

cell, verdict((1, 2), place)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((1, 2), place)}}\end{array}

Step 4 — Branch

Compute the highlighted combinatorics value.

cell, verdict((2, 1), reject diagonal)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((2, 1), reject diagonal)}}\end{array}

Step 5 — Branch

Compute the highlighted combinatorics value.

cell, verdict((2, 3), reject diagonal)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((2, 3), reject diagonal)}}\end{array}

Step 6 — Branch

Compute the highlighted combinatorics value.

cell, verdict((1, 3), place)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((1, 3), place)}}\end{array}

Step 7 — Branch

Compute the highlighted combinatorics value.

cell, verdict((2, 1), place)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((2, 1), place)}}\end{array}

Step 8 — Branch

Compute the highlighted combinatorics value.

cell, verdict((3, 2), reject diagonal)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((3, 2), reject diagonal)}}\end{array}

Step 9 — Branch

Compute the highlighted combinatorics value.

cell, verdict((0, 1), place)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((0, 1), place)}}\end{array}

Step 10 — Branch

Compute the highlighted combinatorics value.

cell, verdict((1, 3), place)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((1, 3), place)}}\end{array}

Step 11 — Branch

Compute the highlighted combinatorics value.

cell, verdict((2, 0), place)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((2, 0), place)}}\end{array}

Step 12 — Branch

Compute the highlighted combinatorics value.

cell, verdict((3, 2), solution)\begin{array}{c|c}\text{cell, verdict}&\hlmath{\text{((3, 2), solution)}}\end{array}
combinatorics-search Every row is intentionally ordered and pinned to the lesson specification.