A Sudoku puzzle has empty cells everywhere.
Each empty cell might contain:
1, 2, 3, 4, 5, 6, 7, 8 or 9.
So should an AI simply try every possible combination?
It could.
In the same way that you could search for your car keys by examining every single object in your house one at a time.
Technically possible.
Slightly concerning.
Fortunately, there is a much smarter idea:
Eliminate what cannot be true.
And that idea leads us to one of the most useful families of problems in Artificial Intelligence:
Constraint Satisfaction Problems.
Sudoku is a perfect place to see the idea because the puzzle looks simple.
Nine rows.
Nine columns.
Nine 3 x 3 boxes.
But underneath those little squares lies a beautiful combination of logic, search, constraints, heuristics, backtracking and mathematics.
The interesting question is not simply:
“Can AI solve a Sudoku?”
It is:
“How can AI avoid trying millions or billions of bad possibilities in the first place?”
First, Can You Solve This?
Before we let the AI near the puzzle, take a look yourself.
Suppose one cell is empty.
What numbers could go there?
At first you might say:
Any digit from 1 to 9.
But then you inspect the row.
Some numbers disappear.
You inspect the column.
More disappear.
You inspect the 3 x 3 box.
More disappear again.
Eventually there may be only one possibility left.
You did not guess.
You used:
Constraints.
That is exactly where our AI story begins.
Sudoku as a Constraint Satisfaction Problem
A Constraint Satisfaction Problem, usually shortened to CSP, has three basic ingredients.
Variables
These are the things we need to decide.
In Sudoku, every empty cell can be treated as a variable.
For example:
The variable represents something whose value is not yet known.
Domains
Every variable has a set of possible values.
This set is called its domain.
For a Sudoku cell, we may initially write:
At the beginning, all nine digits may appear possible.
But not for long.
Constraints
Constraints are the rules that the values must satisfy.
In Sudoku:
- No digit can repeat in the same row.
- No digit can repeat in the same column.
- No digit can repeat in the same 3 x 3 box.
So the AI is not merely asking:
“Which number should I try?”
It is asking:
“Which numbers are still legally possible?”
That is a much more useful question.
The Domain Starts Shrinking
Consider one empty Sudoku cell.
At first:
Nine possibilities.
Now suppose the row already contains:
1, 3, 6 and 8
Those values cannot appear again in that row.
Remove them.
The domain becomes:
Five possibilities remain.
Now examine the column.
Suppose the column already contains:
2, 4 and 9
Those can also be removed.
Now:
Only two possibilities remain.
Finally, suppose the same 3 x 3 box already contains:
5
Then 5 must disappear too.
We are left with:
Only one possibility remains.
The answer is forced.
No guessing.
No dramatic AI revelation.
Just logical elimination.
This gives us one of the most important ideas in constraint solving:
Reduce the domain before you search.
The more possibilities we can eliminate logically, the less searching the algorithm needs to do later.
Constraint Propagation: One Decision Changes Many Others
Now suppose we place:
7
into that cell.
What happens next?
The effect does not remain inside one square.
The number 7 can now be removed as a candidate from other empty cells in the same row.
It can also be removed from cells in the same column.
And from cells in the same 3 x 3 box.
One decision changes many other possibilities.
This process is called:
Constraint Propagation.
Think of it as information spreading through the puzzle.
Place one number.
Then:
Remove impossible candidates elsewhere.
Then:
Another cell may now have only one possible value.
Then:
Place that value.
Then:
More candidates disappear.
Then:
Repeat.
The puzzle begins to change through a chain reaction of deductions.
Well…
not literally by itself.
The algorithm would like some credit.
When a Cell Has Only One Choice
Suppose a cell has:
There is no decision to make.
The value must be:
4
For a constraint solver, this simply means the domain contains one element.
Mathematically:
The vertical bars mean:
the number of elements in the set.
So:
A single remaining candidate is powerful because uncertainty has disappeared.
Once 4 is placed, constraint propagation begins again.
That new value may eliminate 4 from several other cells.
Those eliminations may create another single.
That new single may create another.
A small piece of information can therefore produce a surprisingly large chain of deductions.
But What If Two Possibilities Remain?
Now the puzzle becomes more interesting.
Suppose:
Both values are currently legal.
The AI cannot yet determine which one is correct.
So it may have to make a temporary choice.
Suppose it chooses:
and continues solving.
Several decisions later, something unpleasant happens.
Another cell ends up with:
An empty domain.
There is no legal number that can be placed in that cell.
That means:
A contradiction has occurred.
The earlier choice must have led us down an impossible path.
So what should the AI do?
Panic?
Delete the Sudoku app?
Question every decision it has ever made?
Fortunately:
No.
It backtracks.
Backtracking: “Well, That Did Not Work”
Backtracking is one of the simplest and most useful ideas in intelligent search.
The pattern is:
Choose -> Continue -> Contradiction -> Go Back -> Try Something Else
Suppose:
The AI first tries:
That branch eventually produces a contradiction.
So the solver returns to the earlier decision.
It removes 4 as a possibility.
Then it tries:
and continues solving.
In a search tree, each branch represents a possible decision.
Some branches continue.
Some branches eventually produce contradictions.
When a contradiction appears, the algorithm abandons that branch and returns to an earlier decision point.
This is not failure.
It is information.
The failed branch has taught us:
“This choice cannot lead to a valid solution.”
Sometimes the smartest thing an algorithm can do is admit:
“That was a bad idea.”
and undo it.
Useful advice for algorithms.
Occasionally useful advice for humans too.
Why Not Just Guess Randomly?
Because every uncertain choice can create even more uncertain choices.
Suppose ten cells each have two possibilities.
A naive search could potentially involve:
Twenty such choices:
Thirty:
More than a billion possibilities.
And that is with only two choices per decision.
So even after constraints eliminate many options, the AI still benefits from deciding:
Which uncertain cell should I investigate first?
That brings us to another clever idea.
Fail First? That Sounds Like Terrible Advice.
Imagine two empty cells.
Cell A has:
Only two possibilities.
Cell B has:
Seven possibilities.
Which should the solver investigate first?
A common strategy is:
Choose Cell A.
Why?
Because it is more constrained.
This strategy is called:
Minimum Remaining Values - MRV
The rule is simple:
Choose the variable with the smallest remaining domain.
At first, this may seem backwards.
Why deliberately choose the difficult cell?
Because if a contradiction is going to occur, we would rather discover it early.
This principle is sometimes described as:
Fail first.
That sounds pessimistic.
Computationally, however, it is extremely sensible.
Discovering a contradiction after two decisions is much cheaper than discovering it after twenty.
MRV therefore helps reduce wasted search.
How Large Is the Search Space?
A standard Sudoku grid contains:
81 cells.
Imagine, very naively, that every cell independently had nine choices.
The number of possible assignments would be:
which is approximately:
That is an extraordinarily large number.
To be clear:
This is not the number of valid completed Sudoku grids.
It is simply the size of the completely unconstrained assignment space if we imagined nine possibilities for every one of the 81 positions.
The point is not the exact number.
The point is the scale.
Trying everything blindly would be absurd.
Fortunately, Sudoku gives us structure.
Rows remove possibilities.
Columns remove possibilities.
Boxes remove possibilities.
Given clues remove possibilities.
Constraint propagation removes even more.
MRV helps us decide where to branch.
Backtracking destroys impossible branches.
The enormous search space begins to collapse.
This leads to a beautiful idea:
Constraints do not merely make the puzzle harder.
They are also what make intelligent solving possible.
Without structure, the search space is enormous.
With structure, most possibilities never need to be examined at all.
Brute Force vs Intelligent Search
Imagine two Sudoku solvers.
Solver A tries values almost blindly.
Wrong?
Try something else.
Wrong again?
Try something else.
Repeat.
Solver B starts differently.
It asks:
- Which values are impossible?
- Which cells are already forced?
- Which uncertain cell has the fewest possibilities?
- What information can be propagated before another guess is necessary?
Only when logic can no longer continue does it create a branch.
Which solver would you rather be?
Hopefully Solver B.
Solver A may need coffee.
A lot of coffee.
The important lesson is that intelligence is not simply:
Search faster.
It is often:
Search less.
A Sudoku Solver Workflow
A constraint-based Sudoku solver can be imagined as a cycle.
First:
Read the puzzle.
Then:
Assign a domain to every empty cell.
Next:
Apply the row, column and box constraints.
Then:
Propagate everything that can be deduced.
If the puzzle is solved:
Stop.
If not:
Choose a highly constrained cell - perhaps using MRV.
Try one candidate.
Continue propagating constraints.
If a contradiction appears:
Backtrack.
Try another candidate.
Repeat until every variable has a legal value and all constraints are satisfied.
Notice how little of this process is simply:
“Guess.”
Most of the intelligence comes from:
Avoiding unnecessary guesses.
The Mathematics Behind Constraint Satisfaction
Now let us write the idea more generally.
Suppose a problem contains variables:
Each variable has a domain:
We want to choose values:
such that all required constraints are satisfied.
For example, if two variables must contain different values:
For the nine cells in one Sudoku row:
we require all nine values to be different.
The same condition applies to every column and every 3 x 3 box.
In words:
Every variable must receive a legal value, and all constraints must hold simultaneously.
That is the essence of a Constraint Satisfaction Problem.
Sudoku Is Only the Beginning
Sudoku is useful because the rules are easy to see.
But constraint satisfaction appears in much more serious real-world problems.
Consider school timetabling.
We need to assign classes to rooms and time slots.
But teachers cannot teach two classes simultaneously.
Rooms have limited capacity.
Some subjects need special rooms.
Students may have overlapping course requirements.
That is a constraint problem.
Consider employee scheduling.
Workers have different skills.
They have different availability.
Some shifts require minimum staffing levels.
Working-hour limits must be respected.
Again:
A constraint problem.
Consider manufacturing.
Some jobs must be completed before others.
Machines have limited capacity.
Deadlines exist.
Different products require different equipment.
Constraint satisfaction appears again.
The same ideas also appear in logistics, configuration systems, map colouring, resource allocation and planning.
The Sudoku board has disappeared.
But the mathematical structure remains.
Search and Constraint Satisfaction
This article connects naturally to our previous maze problem.
In the maze, the central question was:
Which path should I explore?
In Sudoku, the question becomes:
Which possibilities can I eliminate before exploring at all?
That is an important progression.
Search says:
Explore possible states intelligently.
Constraint satisfaction adds:
First shrink the set of states worth exploring.
Together, these ideas create a much more efficient problem-solving strategy.
Constraints Can Be More Valuable Than More Search
Suppose an AI system faces one million possible solutions.
One strategy is:
Search faster.
Another strategy is:
Use knowledge to eliminate 990,000 impossible solutions first.
The second may be dramatically better.
That distinction appears repeatedly throughout Artificial Intelligence.
Good problem solving is not always about:
More computation.
Sometimes it is about:
Better structure.
A powerful constraint may save far more computation than simply using a faster machine.
Why This Matters for AI Agents
Imagine an AI agent planning a trip.
There may be thousands of possible combinations of flights, hotels, dates and transportation.
Now introduce constraints.
No overnight layover.
Suddenly many possibilities can be discarded immediately.
The agent does not need to evaluate every hotel.
It does not need to compare every flight.
It does not need to explore every itinerary.
Choices that violate the constraints can disappear from consideration.
That is constraint reasoning.
The same principle can help AI agents with course planning, scheduling, resource allocation, project planning, tool selection and multi-step workflows.
Sudoku therefore becomes more than a puzzle.
It becomes a tiny laboratory for intelligent decision-making.
The Bigger Idea
At first, Sudoku appears to ask:
“Which number belongs here?”
But the deeper AI question is:
“Which numbers cannot possibly belong here?”
That difference is enormous.
It changes the problem from:
Guessing answers
to:
Eliminating impossible states.
From:
Trying everything
to:
Searching only what remains plausible.
From:
Brute force
to:
Reasoned search.
The Takeaway
A smart Sudoku solver does not begin by trying every possible completed board.
It uses:
- Variables
- Domains
- Constraints
- Constraint propagation
- Heuristics
- Backtracking
Each one removes unnecessary work.
The overall pattern becomes:
Start with possibilities
Apply constraints
Shrink the domains
Propagate information
Branch only when necessary
Backtrack when a contradiction appears
Continue until all constraints are satisfied
That is not merely a method for solving Sudoku.
It is a general strategy for solving difficult problems:
Eliminate the impossible before searching the possible.
Learning with Purpose
At The Learning Studio, this is exactly the kind of connection I want learners to see.
A Sudoku puzzle begins as something familiar.
Then suddenly it opens the door to:
- Sets
- Logic
- Search trees
- Combinatorics
- Algorithms
- Heuristics
- Artificial Intelligence
A learner may begin with:
“Which number goes in this square?”
and end up asking:
“How can constraints reduce an exponential search space?”
That journey is:
Puzzle -> Pattern -> Logic -> Mathematics -> Algorithm -> AI
And that is when mathematics stops feeling like a collection of formulas.
It becomes a way to understand how intelligent systems solve problems.
Coming Next
Can AI Make a Schedule That Pleases Everyone?
Timetabling, Constraints, Trade-offs and Why Some Problems Become Surprisingly Difficult
A school wants to create a timetable.
Teachers have limited availability.
Rooms have different capacities.
Students need different subjects.
Two classes cannot use the same room at the same time.
And naturally:
Everyone wants Friday afternoon free.
Can AI create a schedule that satisfies every rule?
What happens when some preferences conflict?
What happens when there is no perfect solution?
And how should an AI decide which constraints are mandatory and which preferences can be compromised?
In the next article, we move from Sudoku to one of the most practical constraint problems:
Scheduling.
Because sometimes the hardest puzzle is not a 9 x 9 grid.
It is getting everyone into the right room at the right time.