Constraint Solving

Model and solve CSPs using graph coloring, N-Queens, backtracking, MRV, LCV, forward checking, arc consistency, and structural decomposition.

Many AI problems do not ask for a shortest path. They ask for a valid arrangement.

A timetable is successful when every course has a room and time that obeys the rules. A map coloring is successful when every region has a color and neighboring regions differ. An N-Queens board is successful when all queens are placed and no two queens attack each other.

In these problems, the path used to build the answer is usually not important. The final assignment is important.

A constraint satisfaction problem (CSP) is a formal way to describe this kind of problem. Instead of hiding the state inside an arbitrary data structure, a CSP names three things:

the variables we must assign;
the domain of possible values for each variable;
the constraints that say which combinations are legal.

This simple modelling step gives us algorithms that are more specialized than ordinary BFS or DFS.

From Search to CSP

Standard search treats a state as a black box. The successor function may do anything, and the goal test may check any property.

CSP search has more structure:

A state is a partial assignment, such as {A: red, B: green}.
A successor assigns a value to one more unassigned variable.
A goal is a complete assignment that satisfies every constraint.

This matters because CSP assignments are usually commutative. Assigning A = red and then B = green gives the same partial assignment as assigning B = green and then A = red. A CSP solver can avoid exploring both orders.

In plain search, we might describe a state as “whatever the program currently knows.” In a CSP, we describe it with discipline:

variables  -> what needs a value
domains    -> which values are possible
constraints -> which combinations are allowed

That discipline is the whole point of CSPs.

Formal Model

A CSP has:

a set of variables X = {X1, X2, ..., Xn};
a domain D(Xi) for each variable Xi;
a set of constraints over one or more variables.

An assignment maps variables to values.

{WA: red, NT: green, SA: blue}

A partial assignment assigns only some variables.

{WA: red, NT: green}

A complete assignment assigns every variable.

A solution is a complete assignment that satisfies all constraints.

Constraints may be:

unary, involving one variable, such as Room != R101;
binary, involving two variables, such as Color(WA) != Color(NT);
higher-order, involving three or more variables, such as a cryptarithmetic column with carries;
global, such as AllDifferent(row_1, ..., row_9) in Sudoku;
hard, which must never be violated;
soft, whose violation has a penalty.

Hard constraints define validity. Soft constraints define preference. A real timetable may require that no instructor teaches two classes at the same time, while merely preferring that certain sessions are not scheduled late in the evening.

Do not mix those two ideas casually. An “almost valid” timetable that double-books a room is not valid.

Common CSP Applications

Sudoku:

Variables: cells.
Domains: numbers 1 through 9.
Constraints: each row, column, and 3 x 3 box has all different values.

Cryptarithmetic:

Variables: letters and carries.
Domains: digits 0 through 9.
Constraints: letters must have different digits, leading letters cannot be zero, and each arithmetic column must add correctly.

Scheduling:

Variables: classes, jobs, exams, or shifts.
Domains: possible (time, room) or (start, end) values.
Constraints: no room conflicts, no instructor conflicts, capacity limits, equipment requirements, and ordering rules.

Line labeling in computer vision:

Variables: junctions or lines in a drawing.
Domains: possible physical interpretations.
Constraints: neighboring interpretations must agree.

CSPs are common in timetabling, rostering, map coloring, frequency assignment, circuit layout, configuration, resource allocation, type inference, test generation, and fault diagnosis.

Generate and Test

The simplest possible CSP method is generate and test:

Generate every complete assignment.
Test whether each assignment satisfies the constraints.
Return the first valid assignment, or all valid assignments if required.

If there are n variables and each has d possible values, generate-and-test may examine d^n complete assignments.

For three map regions and three colors:

3 variables, 3 colors -> 3^3 = 27 complete assignments

For 20 regions and three colors:

20 variables, 3 colors -> 3^20 = 3,486,784,401 complete assignments

The problem is not only the large number. The deeper problem is that generate-and-test wastes time finishing assignments that were already impossible earlier.

If WA = red and NT = red, and WA touches NT, that partial assignment is already invalid. There is no reason to continue assigning the rest of the map.

Backtracking is the standard fix.

Backtracking

Backtracking builds an assignment one variable at a time.

At each step it follows this pattern:

choose an unassigned variable
try one value from its domain
check whether the partial assignment is still valid
recurse to assign the next variable
undo the value if the recursive call fails

The “undo” step is what makes it backtracking. The algorithm returns to the most recent decision point and tries the next option.

This is depth-first search specialized for CSPs, with two important improvements:

it assigns only one variable per level;
it checks constraints as soon as possible.

The general shape is:

backtrack(assignment):
    if assignment is complete:
        return assignment

    variable = choose an unassigned variable

    for each value in variable's domain:
        if value is consistent with assignment:
            assign value
            result = backtrack(assignment)
            if result exists:
                return result
            undo value

    return failure

The core invariant is:

Every recursive call receives a partial assignment that satisfies all constraints involving assigned variables.

That invariant is the reason the solver can prune large parts of the search tree.

Graph Coloring as a CSP

Graph coloring is the cleanest first CSP example.

Given a graph and a fixed set of colors, assign one color to each vertex so that adjacent vertices have different colors.

This chapter studies vertex coloring, the most common form. In edge coloring, incident edges must differ; in face coloring, neighboring regions must differ. Map coloring can be converted to vertex coloring by making each region a vertex and connecting regions that share a border.

The chromatic number of a graph, written χ(G), is the smallest number of colors that can produce a valid coloring. Finding one coloring with three colors proves χ(G) <= 3; it does not prove that three colors are necessary. To prove χ(G) = 3, we must also show that two colors cannot work.

Model:

Variables: vertices of the graph.
Domains: available colors.
Constraints: for every edge (u, v), color(u) != color(v).

Example graph:

A is adjacent to B and C
B is adjacent to A, C, and D
C is adjacent to A, B, and D
D is adjacent to B and C

As an adjacency list:

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"],
}

With colors:

colors = ["red", "green", "blue"]

One valid solution is:

A = red
B = green
C = blue
D = red

D can reuse red because D is not adjacent to A.

The vertices A, B, and C form a triangle, so they must all have different colors. Therefore this graph cannot use only two colors. Since the displayed assignment uses three colors, its chromatic number is exactly 3.

Graph Coloring Trace

Use vertex order A, B, C, D and color order red, green, blue. The complete trace belongs in one block because it represents one continuous run of the algorithm:

Start: {}

A: try red
   accept -> {A: red}

B: try red   -> reject; B touches red A
   try green -> accept
   assignment = {A: red, B: green}

C: try red   -> reject; C touches red A
   try green -> reject; C touches green B
   try blue  -> accept
   assignment = {A: red, B: green, C: blue}

D: try red -> accept; D touches B and C, but not A
   assignment = {A: red, B: green, C: blue, D: red}

The assignment is complete, so it is a solution.

The important idea is not this particular answer. The important idea is that invalid partial assignments are rejected immediately.

Graph Coloring Code: Follow the Execution

The blocks below follow the program at runtime, just as we trace main, push, and pop in a stack program. Python first loads the function and class definitions; their bodies do not run yet. The graph-coloring work begins when the entry guard calls main.

main -> GraphColoring() -> graphColor -> solve -> isPossible
                                      -> deeper solve or undo
                                      -> display

1. Enter `main`

def main():
    graph = [
        [0, 1, 1, 0],
        [1, 0, 1, 1],
        [1, 1, 0, 1],
        [0, 1, 1, 0],
    ]

    gc = GraphColoring()
    gc.graphColor(graph, 3)


if __name__ == "__main__":
    main()

When this file is run directly, __name__ equals "__main__", so the final line calls main().

Inside main, the matrix is created first. Row 0, [0, 1, 1, 0], says that vertex 0 is not connected to itself, is connected to vertices 1 and 2, and is not connected to vertex 3. Because the graph is undirected, the matrix is symmetric: if graph[0][1] is 1, then graph[1][0] is also 1.

Next, gc = GraphColoring() asks Python to create a solver object. Python pauses main, enters __init__, and stores the returned object in gc. Only then can the following line call gc.graphColor(graph, 3).

2. Initialize the Solver Object

class GraphColoring:
    def __init__(self):
        self.V = 0
        self.numOfColors = 0
        self.color = []
        self.graph = []

self is the new object that will become gc. The constructor creates four fields on that object:

self.V = 0: no graph has been loaded, so the vertex count is not known yet;
self.numOfColors = 0: no color limit has been supplied yet;
self.color = []: there are no vertex assignments yet;
self.graph = []: there is no adjacency matrix yet.

These are safe initial values, not a graph-coloring problem. When __init__ finishes, execution returns to the waiting line in main. At that point gc refers to the initialized object, and the next statement enters graphColor(graph, 3).

3. Load the Problem and Start the Search

def graphColor(self, g, noc):
    self.V = len(g)
    self.numOfColors = noc
    self.color = [0] * self.V
    self.graph = g

    if self.solve(0):
        print("Solution exists")
        self.display()
    else:
        print("No solution")

g receives the four-row matrix and noc receives 3. The assignments execute from top to bottom:

self.V = len(g) stores 4;
self.numOfColors = noc stores 3;
self.color = [0] * self.V creates [0, 0, 0, 0];
self.graph = g stores the matrix on the object.

Color 0 means uncolored. Actual colors begin at 1, so the solver can distinguish an unused vertex from a vertex assigned the first color.

Before Python can decide which if branch to execute, it must evaluate self.solve(0). Execution therefore leaves graphColor and enters solve with v = 0. The graphColor call remains waiting at the if statement.

If solve(0) eventually returns True, the successful assignments are still present in self.color, so display() can print them. If it returns False, the else branch prints No solution and display() is never called.

4. Try a Color for the Current Vertex

def solve(self, v):
    if v == self.V:
        return True

    for c in range(1, self.numOfColors + 1):
        if self.isPossible(v, c):
            self.color[v] = c

            if self.solve(v + 1):
                return True

            self.color[v] = 0

    return False

The parameter v identifies the vertex handled by this call. In the first call, v = 0 and self.color is [0, 0, 0, 0].

The base case checks v == self.V. It is false for vertices 0 through 3. It becomes true at v = 4, which means all four real vertices were colored safely before that call began.

range(1, self.numOfColors + 1) produces 1, 2, 3. It deliberately skips 0 because 0 means uncolored.

Before storing that color, self.isPossible(0, 1) is called. Execution pauses inside solve and moves into isPossible.

If the check succeeds, self.color[v] = c makes the choice. The recursive call then handles the next vertex while the current solve call waits. The reset to 0 runs only when that deeper call returns False; it removes the failed choice before another color is tried.

If all colors fail, the final return False sends control to the previous recursive call. This is exactly where backtracking occurs.

5. Check the Proposed Color

def isPossible(self, v, c):
    for i in range(self.V):
        if self.graph[v][i] == 1 and c == self.color[i]:
            return False
    return True

The loop checks every vertex index i. The left side of and asks whether v and i are adjacent. Only when an edge exists does the right side compare the proposed color c with self.color[i].

The first two calls show the purpose clearly:

isPossible(0, 1), color = [0, 0, 0, 0]
    no neighbor already has color 1
    return True

solve stores color[0] = 1

isPossible(1, 1), color = [1, 0, 0, 0]
    graph[1][0] == 1 and color[0] == 1
    return False

isPossible(1, 2), color = [1, 0, 0, 0]
    no adjacent vertex has color 2
    return True

Uncolored vertices contain 0, so they cannot conflict with candidate colors 1, 2, or 3. The function is therefore checking the candidate only against choices already made earlier in the search.

If no conflict is found, it returns True. Execution then resumes exactly where solve called isPossible:

isPossible returns False -> try the next color

isPossible returns True  -> store self.color[v] = c
                         -> call solve(v + 1)

deeper solve returns True  -> keep the choices and return True
deeper solve returns False -> reset self.color[v] = 0 and try again

This make–recurse–undo sequence is the heart of backtracking. When v == self.V, every vertex has a safe color and True travels back through all waiting calls to graphColor.

6. Display the Completed Coloring

def display(self):
    textColor = [
        "",
        "RED",
        "GREEN",
        "BLUE",
        "YELLOW",
        "ORANGE",
        "PINK",
        "BLACK",
        "BROWN",
        "WHITE",
        "PURPLE",
        "VIOLET",
    ]

    print("Colors:", end=" ")
    for i in range(self.V):
        print(textColor[self.color[i]], end=" ")
    print()

After solve(0) returns True, execution resumes inside graphColor, which prints Solution exists and calls display.

For this graph, the stored solution is [1, 2, 3, 1]. During the loop:

vertex 0 uses textColor[1], which is RED;
vertex 1 uses textColor[2], which is GREEN;
vertex 2 uses textColor[3], which is BLUE;
vertex 3 uses textColor[1], which is RED.

The empty string at index 0 keeps list indexes aligned with color numbers. It should never be printed in a successful solution because every vertex is colored before display is called.

The output is Colors: RED GREEN BLUE RED. When display returns, graphColor returns to main, main returns to the entry guard, and the program ends.

Graph Coloring: Final Full Code

class GraphColoring:
    def __init__(self):
        self.V = 0
        self.numOfColors = 0
        self.color = []
        self.graph = []

    def graphColor(self, g, noc):
        self.V = len(g)
        self.numOfColors = noc
        self.color = [0] * self.V
        self.graph = g

        if self.solve(0):
            print("Solution exists")
            self.display()
        else:
            print("No solution")

    def solve(self, v):
        if v == self.V:
            return True

        for c in range(1, self.numOfColors + 1):
            if self.isPossible(v, c):
                self.color[v] = c

                if self.solve(v + 1):
                    return True

                self.color[v] = 0

        return False

    def isPossible(self, v, c):
        for i in range(self.V):
            if self.graph[v][i] == 1 and c == self.color[i]:
                return False
        return True

    def display(self):
        textColor = [
            "",
            "RED",
            "GREEN",
            "BLUE",
            "YELLOW",
            "ORANGE",
            "PINK",
            "BLACK",
            "BROWN",
            "WHITE",
            "PURPLE",
            "VIOLET",
        ]

        print("Colors:", end=" ")
        for i in range(self.V):
            print(textColor[self.color[i]], end=" ")
        print()


def main():
    graph = [
        [0, 1, 1, 0],
        [1, 0, 1, 1],
        [1, 1, 0, 1],
        [0, 1, 1, 0],
    ]

    gc = GraphColoring()
    gc.graphColor(graph, 3)


if __name__ == "__main__":
    main()

#include <stdio.h>
#include <stdbool.h>

#define V 4
#define NUM_COLORS 3

int graph[V][V] = {
    {0, 1, 1, 0},
    {1, 0, 1, 1},
    {1, 1, 0, 1},
    {0, 1, 1, 0}
};

int color[V] = {0};

bool isPossible(int v, int c) {
    for (int i = 0; i < V; i++) {
        if (graph[v][i] == 1 && color[i] == c) {
            return false;
        }
    }
    return true;
}

bool solve(int v) {
    if (v == V) {
        return true;
    }

    for (int c = 1; c <= NUM_COLORS; c++) {
        if (isPossible(v, c)) {
            color[v] = c;

            if (solve(v + 1)) {
                return true;
            }

            color[v] = 0;
        }
    }

    return false;
}

void display(void) {
    const char *textColor[] = {
        "", "RED", "GREEN", "BLUE", "YELLOW", "ORANGE"
    };

    printf("Colors: ");
    for (int i = 0; i < V; i++) {
        printf("%s ", textColor[color[i]]);
    }
    printf("\n");
}

int main(void) {
    if (solve(0)) {
        printf("Solution exists\n");
        display();
    } else {
        printf("No solution\n");
    }

    return 0;
}

#include <iostream>

using namespace std;

#define V 4
#define NUM_COLORS 3

class GraphColoring {
private:
    int color[V];
    int graph[V][V];

public:
    void graphColor(int g[V][V]) {
        for (int i = 0; i < V; i++) {
            color[i] = 0;

            for (int j = 0; j < V; j++) {
                graph[i][j] = g[i][j];
            }
        }

        if (solve(0)) {
            cout << "Solution exists\n";
            display();
        } else {
            cout << "No solution\n";
        }
    }

    bool solve(int v) {
        if (v == V) {
            return true;
        }

        for (int c = 1; c <= NUM_COLORS; c++) {
            if (isPossible(v, c)) {
                color[v] = c;

                if (solve(v + 1)) {
                    return true;
                }

                color[v] = 0;
            }
        }

        return false;
    }

    bool isPossible(int v, int c) {
        for (int i = 0; i < V; i++) {
            if (graph[v][i] == 1 && color[i] == c) {
                return false;
            }
        }
        return true;
    }

    void display() {
        const char *textColor[] = {
            "", "RED", "GREEN", "BLUE", "YELLOW", "ORANGE"
        };

        cout << "Colors: ";
        for (int i = 0; i < V; i++) {
            cout << textColor[color[i]] << " ";
        }
        cout << "\n";
    }
};

int main() {
    int graph[V][V] = {
        {0, 1, 1, 0},
        {1, 0, 1, 1},
        {1, 1, 0, 1},
        {0, 1, 1, 0}
    };

    GraphColoring gc;
    gc.graphColor(graph);

    return 0;
}

public class GraphColoring {
    private int V;
    private int numOfColors;
    private int[] color;
    private int[][] graph;

    public void graphColor(int[][] g, int noc) {
        V = g.length;
        numOfColors = noc;
        color = new int[V];
        graph = g;

        if (solve(0)) {
            System.out.println("Solution exists");
            display();
        } else {
            System.out.println("No solution");
        }
    }

    private boolean solve(int v) {
        if (v == V) {
            return true;
        }

        for (int c = 1; c <= numOfColors; c++) {
            if (isPossible(v, c)) {
                color[v] = c;

                if (solve(v + 1)) {
                    return true;
                }

                color[v] = 0;
            }
        }

        return false;
    }

    private boolean isPossible(int v, int c) {
        for (int i = 0; i < V; i++) {
            if (graph[v][i] == 1 && color[i] == c) {
                return false;
            }
        }
        return true;
    }

    private void display() {
        String[] textColor = {
            "", "RED", "GREEN", "BLUE", "YELLOW", "ORANGE"
        };

        System.out.print("Colors: ");
        for (int i = 0; i < V; i++) {
            System.out.print(textColor[color[i]] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 1, 1, 0},
            {1, 0, 1, 1},
            {1, 1, 0, 1},
            {0, 1, 1, 0}
        };

        GraphColoring gc = new GraphColoring();
        gc.graphColor(graph, 3);
    }
}

These versions follow the reference implementation’s structure: an adjacency matrix, a color array, a recursive solve function, an isPossible check, and a display function.

The supplied Java version stops by throwing an exception after a solution is found. These versions use a Boolean return instead because it is easier to trace: true means “solution found,” and false means “this branch failed.”

If an exercise requires file or keyboard input, keep the same solver and replace only the graph = [...] part with input-reading code.

N-Queens as a CSP

The N-Queens problem asks us to place N queens on an N x N chessboard so that no two queens attack each other.

Two queens attack each other if they share:

a row;
a column;
a diagonal.

A weak CSP formulation uses one Boolean variable per square:

Square(row, column) is either occupied or empty

That creates N^2 variables and many constraints.

A better formulation uses one variable per column:

Q[column] = row where the queen in this column is placed

Model:

Variables: columns 0 through N - 1.
Domain of each variable: rows 0 through N - 1.
Constraints:
- no two variables have the same row;
- no two queens share a diagonal.

Column conflicts disappear by construction because the representation stores exactly one queen per column.

This is not just an implementation trick. It is a modelling improvement. Good CSP modelling removes impossible states before search begins.

N-Queens Diagonal Rule

Suppose one queen is at (row1, col1) and another is at (row2, col2).

They are on the same diagonal when:

abs(row1 - row2) == abs(col1 - col2)

Example:

(0, 1) and (2, 3)

abs(0 - 2) = 2
abs(1 - 3) = 2

They are on the same diagonal, so that placement is invalid.

There are also two useful diagonal identifiers:

descending diagonal: row - column
ascending diagonal:  row + column

If two queens have the same row - column, they share one diagonal direction. If they have the same row + column, they share the other.

We can store occupied rows and diagonals in sets for fast conflict checks.

N-Queens Trace for N = 4

Try columns from left to right. In this compact trace, placement[column] = row, and -1 means that a column has no queen yet.

Start: [-1, -1, -1, -1]

column 0:
  row 0 -> safe; place queen
  state = [0, -1, -1, -1]

column 1:
  row 0 -> reject; same row
  row 1 -> reject; same diagonal
  row 2 -> safe; place queen
  state = [0, 2, -1, -1]

column 2:
  rows 0, 1, 2, and 3 all conflict
  no choice works -> backtrack
  state = [0, -1, -1, -1]

column 1:
  row 3 -> safe; place queen
  state = [0, 3, -1, -1]

This branch eventually fails too, so backtrack to column 0.
Try row 1 there and continue searching.

Solution: [1, 3, 0, 2]

column 0 -> row 1
column 1 -> row 3
column 2 -> row 0
column 3 -> row 2

In 1-based notation, this is (2, 4, 1, 3).

N-Queens Implementation

This implementation solves N-Queens with a 0/1 board matrix and recursive backtracking. The Python version is explained function by function first. Complete Python, C, C++, and Java programs follow afterward.

The Python program follows this structure:

input -> printSolution -> solveNQUtil -> isSafe
                                         |
                                         -> accept or reject a square
                       -> place, recurse, and backtrack
      -> print the completed board after success

Python: Block-by-Block in Runtime Order

Python first executes the three def statements. This creates the functions but does not run their bodies. The algorithm actually starts at the two statements below the function definitions.

Read the Board Size and Start

n = int(input("Number of queen to place - \n"))
printSolution(n)

input(...) displays the prompt and returns the typed value as a string. The escape sequence \n moves the cursor to the next line. int(...) converts the string to an integer and stores it in n.

printSolution(n) then calls printSolution. The value in n is passed into its parameter N.

Create the Board

Execution now enters printSolution:

def printSolution(N):
    board = [[0] * N for _ in range(N)]

[0] * N creates one row containing N zeros. The list comprehension performs that operation N times, producing an N x N matrix. The variable _ means that the loop value is intentionally unused.

Each repetition creates a separate row. Writing [[0] * N] * N instead would repeat references to the same inner list, so changing one row could unexpectedly change every row.

A 0 represents an empty square. A 1 will represent a queen.

Start the Recursive Search

The next executed block calls the solver for column 0, the leftmost column:

if not solveNQUtil(board, 0, N):
    print("Solution does not exist")
    return False

Execution of printSolution pauses while solveNQUtil searches. The not is evaluated after the solver returns. If the solver returns False, not False becomes True, so the program prints the failure message and stops this function.

Enter a Column

Execution enters solveNQUtil with the current column number:

def solveNQUtil(board, col, N):
    if col >= N:
        return True

The base case is checked first. Valid column indexes end at N - 1, so reaching col == N means all N queens have been placed safely. return True reports a completed solution to the previous recursive call.

Try a Row

If the base case is not reached, the solver tries every row in the current column:

for i in range(N):
    if isSafe(board, i, col, N):

range(N) produces row indexes 0, 1, ..., N - 1. For each row i, the solver calls isSafe before changing the board. The current solveNQUtil call pauses until that safety check returns True or False.

Check the Same Row

Execution enters isSafe(board, row, col, N). Here, row receives the value passed as i, col identifies the current column, and N is the board size.

def isSafe(board, row, col, N):
    for i in range(col):
        if board[row][i] == 1:
            return False

Only the left side needs checking because columns are filled from left to right. Columns 0 through col - 1 may contain queens, while columns to the right are still empty.

range(col) produces 0, 1, ..., col - 1. Therefore, board[row][i] visits each square to the left in the proposed queen’s row. If any cell contains 1, another queen already occupies that row and the function immediately returns False.

Check the Upper-Left Diagonal

If the row is clear, execution continues to the next loop:

for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
    if board[i][j] == 1:
        return False

range(row, -1, -1) counts upward: row, row - 1, ..., 0. The ending value -1 is excluded. range(col, -1, -1) similarly counts leftward from col to 0.

zip(...) takes one value from each range at the same time and creates coordinate pairs. Tuple unpacking places the two values into i and j:

(row, col), (row - 1, col - 1), (row - 2, col - 2), ...

Decreasing both coordinates by one traces the upper-left diagonal. Finding a 1 means that a queen attacks the proposed square, so the function returns False.

Check the Lower-Left Diagonal

If the upper-left diagonal is clear, execution reaches the final safety loop:

for i, j in zip(range(row, N, 1), range(col, -1, -1)):
    if board[i][j] == 1:
        return False

range(row, N, 1) counts downward from row to N - 1; the explicit step is 1. Pairing it with the decreasing column range produces (row, col), (row + 1, col - 1), ..., which traces the lower-left diagonal.

zip stops automatically when the shorter range ends, so it does not produce coordinates beyond a board edge. Both diagonal loops include (row, col), but this cell is still 0 because safety is checked before placement.

If all three checks finish without finding a queen, execution reaches:

return True

That value returns to the paused if isSafe(...) inside solveNQUtil.

For example, if a queen occupies (0, 0):

isSafe(board, 0, 1, 4) -> False: same row
isSafe(board, 1, 1, 4) -> False: upper-left diagonal
isSafe(board, 2, 1, 4) -> True: no conflict

Place, Recurse, or Backtrack

When isSafe returns True, execution enters the placement block:

board[i][col] = 1

if solveNQUtil(board, col + 1, N):
    return True

board[i][col] = 0

The three important operations occur in runtime order:

board[i][col] = 1                -> choose this square
solveNQUtil(board, col + 1, N)   -> search the next column
board[i][col] = 0                -> undo the choice if it fails

The recursive call creates another solveNQUtil call for the next column. That call repeats the same base-case, row-selection, and safety-check process.

If a deeper call returns True, return True sends success through every waiting recursive call. If it returns False, execution continues to board[i][col] = 0. Removing the queen restores the board before the loop tries the next row; this undo operation is backtracking.

If every row in the current column fails, execution reaches:

return False

This tells the previous recursive call that its queen choice led to a dead end and must also be removed.

Return and Print the Result

After solveNQUtil returns True, execution resumes inside printSolution. The not True condition is False, so the failure block is skipped and the completed board is printed:

print("Solution found for", N, "queens")

for i in range(N):
    for j in range(N):
        print(board[i][j], end=" ")
    print()

return True

The outer loop selects each row, and the inner loop visits every column in that row. end=" " prints a space instead of starting a new line after each cell. The empty print() runs after one full row and moves output to the next line.

Finally, return True ends printSolution, and the program has no statements left to execute.

N-Queens: Full Code

All four versions use the same board-matrix backtracking structure so that their functions can be compared directly.

def isSafe(board, row, col, N):
    for i in range(col):
        if board[row][i] == 1:
            return False

    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    for i, j in zip(range(row, N, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    return True


def solveNQUtil(board, col, N):
    if col >= N:
        return True

    for i in range(N):
        if isSafe(board, i, col, N):
            board[i][col] = 1

            if solveNQUtil(board, col + 1, N):
                return True

            board[i][col] = 0

    return False


def printSolution(N):
    board = [[0] * N for _ in range(N)]

    if not solveNQUtil(board, 0, N):
        print("Solution does not exist")
        return False

    print("Solution found for", N, "queens")

    for i in range(N):
        for j in range(N):
            print(board[i][j], end=" ")
        print()

    return True


n = int(input("Number of queen to place - \n"))
printSolution(n)

#include <stdio.h>
#include <stdbool.h>

#define MAX_N 20

bool isSafe(int board[MAX_N][MAX_N], int row, int col, int N) {
    for (int i = 0; i < col; i++) {
        if (board[row][i] == 1) {
            return false;
        }
    }

    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }

    for (int i = row, j = col; i < N && j >= 0; i++, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }

    return true;
}

bool solveNQUtil(int board[MAX_N][MAX_N], int col, int N) {
    if (col >= N) {
        return true;
    }

    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col, N)) {
            board[i][col] = 1;

            if (solveNQUtil(board, col + 1, N)) {
                return true;
            }

            board[i][col] = 0;
        }
    }

    return false;
}

bool printSolution(int N) {
    int board[MAX_N][MAX_N] = {0};

    if (N < 1 || N > MAX_N) {
        printf("N must be between 1 and %d\n", MAX_N);
        return false;
    }

    if (!solveNQUtil(board, 0, N)) {
        printf("Solution does not exist\n");
        return false;
    }

    printf("Solution found for %d queens\n", N);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }

    return true;
}

int main(void) {
    int n;

    printf("Number of queen to place - \n");
    scanf("%d", &n);

    printSolution(n);

    return 0;
}

#include <iostream>

using namespace std;

#define MAX_N 20

bool isSafe(int board[MAX_N][MAX_N], int row, int col, int N) {
    for (int i = 0; i < col; i++) {
        if (board[row][i] == 1) {
            return false;
        }
    }

    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }

    for (int i = row, j = col; i < N && j >= 0; i++, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }

    return true;
}

bool solveNQUtil(int board[MAX_N][MAX_N], int col, int N) {
    if (col >= N) {
        return true;
    }

    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col, N)) {
            board[i][col] = 1;

            if (solveNQUtil(board, col + 1, N)) {
                return true;
            }

            board[i][col] = 0;
        }
    }

    return false;
}

bool printSolution(int N) {
    int board[MAX_N][MAX_N] = {0};

    if (N < 1 || N > MAX_N) {
        cout << "N must be between 1 and " << MAX_N << "\n";
        return false;
    }

    if (!solveNQUtil(board, 0, N)) {
        cout << "Solution does not exist\n";
        return false;
    }

    cout << "Solution found for " << N << " queens\n";

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }

    return true;
}

int main() {
    int n;

    cout << "Number of queen to place - \n";
    cin >> n;

    printSolution(n);

    return 0;
}

import java.util.Scanner;

public class N_queen {
    int N;

    N_queen(int a)
    {
        N = a;
    }

    void printSolution(int[][] board) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(" " + board[i][j] + " ");
            }
            System.out.println();
        }
    }

    boolean isSafe(int grid[][], int row, int col) {
        int i, j;

        for (i = 0; i < col; i++) {
            if (grid[row][i] == 1) {
                return false;
            }
        }

        for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (grid[i][j] == 1) {
                return false;
            }
        }

        for (i = row, j = col; j >= 0 && i < N; i++, j--) {
            if (grid[i][j] == 1) {
                return false;
            }
        }

        return true;
    }

    boolean solveNQUtil(int grid[][], int col) {
        if (col >= N) {
            return true;
        }

        for (int i = 0; i < N; i++) {
            if (isSafe(grid, i, col)) {
                grid[i][col] = 1;

                if (solveNQUtil(grid, col + 1) == true) {
                    return true;
                }

                grid[i][col] = 0;
            }
        }

        return false;
    }

    boolean solveNQ() {
        int grid[][] = new int[N][N];

        if (solveNQUtil(grid, 0) == false) {
            System.out.print("Solution does not exist for " + N + " queens");
            return false;
        }

        System.out.println("Solution found for " + N + " queens");
        printSolution(grid);
        return true;
    }

    public static void main(String args[]) {
        int n;
        Scanner sc = new Scanner(System.in);

        System.out.println("Number of queen to place - ");
        n = sc.nextInt();

        N_queen Queen = new N_queen(n);
        Queen.solveNQ();
    }
}

These versions share the same structure: isSafe, solveNQUtil, a 0/1 board matrix, left-side safety checks, and recursive column-by-column placement.

Inside Python’s printSolution, the output uses the parameter N, not the global input variable n. This keeps the function correct when it is called with a value from another part of a program.

For quick Python testing without keyboard input, replace the final two lines with a fixed call:

printSolution(7)

For n = 2 and n = 3, no solution exists. For n = 1, the single queen is already a solution.

The board-matrix version is more verbose than the set-based version, but it makes the chessboard visible in the code and keeps the placement and backtracking steps easy to trace.

Complexity of Backtracking

Backtracking is complete for finite CSPs: if a solution exists, it can find one; if no solution exists, it can prove failure after exploring the finite search tree.

Its worst-case time is still exponential.

For n variables with domain size at most d, the rough upper bound is:

O(d^n)

Backtracking does not magically remove exponential complexity. It reduces the practical search tree by pruning impossible partial assignments early.

For N-Queens, the compact representation already removes column conflicts. The row and diagonal checks prune additional branches before deeper recursion.

The lesson is:

model well first, then search well

Choosing Variables: MRV

So far, graph coloring used a fixed vertex order. That is easy to teach, but not always efficient.

The minimum remaining values heuristic, or MRV, chooses the unassigned variable with the fewest legal values left.

It is also called the most constrained variable heuristic.

MRV follows the fail-fast principle:

If a part of the problem is almost impossible, find out now.

Example:

A has 3 legal colors
B has 1 legal color
C has 2 legal colors

MRV chooses B.

If B fails, we avoid wasting time on assignments for A and C that cannot lead to a full solution.

MRV is dynamic. The best next variable can change after every assignment because domains shrink.

Degree Heuristic

MRV can produce ties.

If two variables have the same number of remaining values, the degree heuristic chooses the variable connected to more unassigned neighbors.

The reason is practical: a high-degree variable constrains more of the remaining problem.

In graph coloring, a vertex with many uncolored neighbors is often a better early choice than a nearly isolated vertex.

MRV asks:

Which variable is hardest to assign?

The degree heuristic asks:

Which tied variable affects the most future variables?

Choosing Values: LCV

After choosing a variable, we still need to choose which value to try first.

The least-constraining value heuristic, or LCV, tries the value that removes the fewest options from neighboring variables.

In graph coloring, suppose assigning A = red would remove red from five neighbors, while A = blue would remove blue from only one neighbor. LCV tries blue first.

This may sound opposite to MRV, but the two heuristics answer different questions:

MRV chooses a variable where failure is likely.
LCV chooses a value that preserves flexibility.

MRV is “fail early.” LCV is “try not to cause failure.”

LCV costs extra computation because the solver must estimate how each value affects the remaining domains. It is useful when that computation is cheaper than exploring the subtrees it avoids.

Forward Checking

Plain backtracking checks a value against already-assigned neighbors.

Forward checking also updates the domains of unassigned neighbors.

If assigning A = red means neighboring B cannot be red, remove red from B’s current domain.

If any unassigned variable loses all values, the solver backtracks immediately.

For graph coloring:

def forward_check(vertex, color, graph, domains, assignment):
    removed = []

    for neighbor in graph[vertex]:
        if neighbor in assignment:
            continue

        if color in domains[neighbor]:
            domains[neighbor].remove(color)
            removed.append((neighbor, color))

            if not domains[neighbor]:
                return False, removed

    return True, removed

domains stores the current remaining values for each variable.

removed records every value removed during this assignment.

The solver needs that list during undo:

def restore(domains, removed):
    for variable, value in removed:
        domains[variable].add(value)

Copying all domains at every recursive call is simpler, but it can be expensive. Recording reversible changes is more efficient, but easier to get wrong.

When debugging forward checking, test restoration directly.

Arc Consistency

Forward checking only propagates from a newly assigned variable to its unassigned neighbors.

It can miss contradictions among unassigned variables.

Arc consistency performs stronger propagation for binary CSPs.

For a directed arc X -> Y, the arc is consistent if:

for every value x in D(X),
there is at least one value y in D(Y)
such that X = x and Y = y satisfy the constraint

For graph coloring, the constraint is X != Y.

If:

D(X) = {red, blue}
D(Y) = {blue}

Then X = blue has no support in Y, because Y would also have to be blue. Remove blue from D(X).

Remember the direction:

revise X -> Y means delete unsupported values from X

Delete from the tail of the arc.

AC-3

AC-3 is a common arc-consistency algorithm.

It keeps a queue of arcs. When revising one arc removes values from a domain, neighboring arcs must be checked again because their previous support may have disappeared.

from collections import deque


def revise(domains, x, y):
    revised = False

    for x_value in set(domains[x]):
        has_support = False

        for y_value in domains[y]:
            if x_value != y_value:
                has_support = True
                break

        if not has_support:
            domains[x].remove(x_value)
            revised = True

    return revised


def ac3(domains, graph):
    queue = deque()

    for x in graph:
        for y in graph[x]:
            queue.append((x, y))

    while queue:
        x, y = queue.popleft()

        if revise(domains, x, y):
            if not domains[x]:
                return False

            for z in graph[x]:
                if z != y:
                    queue.append((z, x))

    return True

This version assumes graph-coloring constraints, where adjacent variables must differ.

After revise(domains, x, y) changes D(x), every neighbor z of x may need to be reconsidered because x might have been supporting a value in z.

Arc consistency detects some failures earlier than forward checking. It is still not a complete solver by itself. A CSP can be arc-consistent and still have no global solution.

In practice, AC-3 is often used:

once before search, as preprocessing;
after each assignment, inside backtracking.

The second option prunes more but costs more per recursive call.

Consistency Levels

CSP propagation can be described by consistency levels:

Node consistency: every value satisfies unary constraints.
Arc consistency: every value has support across each binary constraint.
Path consistency: compatible assignments to two variables can be extended through a third variable.
k-consistency: any consistent assignment to k - 1 variables can be extended to a kth variable.

Stronger consistency prunes more values. It also costs more to enforce.

Strong enough consistency can remove the need for backtracking, but computing that much consistency may be as hard as solving the original problem.

That is the central trade-off:

spend time reasoning now, or spend time searching later

Constraint Graphs and Structure

For a binary CSP, the constraint graph has:

one node per variable;
one edge between variables that share a constraint.

This graph reveals structure.

If the graph has disconnected components, each component can be solved independently.

For example, in the classic Australia map-coloring problem, Tasmania has no border with the mainland. It is an independent subproblem.

If a CSP with n variables splits into components of size at most c, the rough cost changes from:

O(d^n)

to:

O((n / c) * d^c)

That is a major difference when c is much smaller than n.

Tree-Structured CSPs

If the constraint graph is a tree, a binary CSP can be solved in about:

O(n * d^2)

That is much better than O(d^n).

The algorithm:

Choose a root variable.
Order variables so parents come before children.
Sweep from leaves toward the root, removing parent values that have no child support.
Assign the root.
Sweep from root toward leaves, assigning each child a value consistent with its parent.

Why no backtracking?

After the backward pass, every parent value that remains has support in each child subtree. When the forward pass chooses a parent value, each child is guaranteed to have at least one compatible value.

Cycles break this guarantee. Local pairwise consistency around a loop may still fail globally.

Nearly Tree-Structured CSPs

Some graphs are not trees, but become trees after removing a small set of variables.

That set is a cutset.

Cutset conditioning works like this:

Choose a small cutset.
Try each possible assignment to the cutset.
For each cutset assignment, simplify the remaining CSP.
Solve the remaining tree-structured CSP efficiently.

If the cutset has size c, the expensive part is d^c, not d^n.

This is a recurring AI strategy:

isolate the hard core, then exploit structure in the rest

Tree Decomposition

Tree decomposition is a more general structural method.

Instead of solving individual variables directly, we group related variables into clusters, sometimes called bags or mega-variables.

Each cluster stores assignments that satisfy its internal constraints. Neighboring clusters must agree on variables they share.

The cluster graph is arranged as a tree, then solved like a tree-structured CSP.

The cost depends exponentially on the largest cluster size, not directly on the total number of variables.

This helps when a large problem is made of small dense parts connected through narrow interfaces.

Common Mistakes

Using too many variables when a better representation can encode part of the solution by construction.
Checking constraints only after a complete assignment.
Forgetting to undo an assignment during backtracking.
Forgetting to restore domain values removed by forward checking.
Applying MRV to original domains instead of current domains.
Treating arc consistency as proof that a solution exists.
Mixing hard constraints and soft preferences in one vague score.
Recomputing every constraint when only local neighbors were affected.
Ignoring disconnected or tree-like structure in the constraint graph.

Review Checklist

When modelling a CSP, ask:

What are the variables?
What is the domain of each variable?
Which constraints are unary, binary, higher-order, or global?
Which constraints are hard, and which are soft preferences?
Can the representation remove some impossible states by construction?
What is the constraint graph?
Are there disconnected components, trees, or nearly tree-structured parts?
Which variable-ordering and value-ordering heuristics fit the problem?
Is forward checking enough, or is stronger propagation worthwhile?
How will the implementation prove that undo and restoration are correct?

Exercises

Formulate Sudoku as a CSP. Identify variables, domains, and constraints.
Trace the graph-coloring solver by hand on the four-vertex graph from this chapter using only two colors. Where does it fail?
Modify the graph-coloring code to return all valid colorings instead of the first one.
Rewrite the graph-coloring solver using an adjacency list while preserving the same backtracking logic.
Add MRV to the graph-coloring solver. Count recursive calls before and after the change.
Add forward checking to graph coloring. Write a test proving that removed values are restored after a failed branch.
Run AC-3 on a triangle graph with two colors. Show each domain deletion.
Trace the N-Queens solver for n = 4 until it finds [1, 3, 0, 2].
Modify the N-Queens solver to return all distinct solutions.
Model an exam timetable as a CSP. Separate hard constraints from soft preferences.
Find a CSP where all arcs are consistent but no complete solution exists.
Draw a constraint graph with one small cutset. Explain how cutset conditioning would solve it.