Sudoku solving algorithms facts for kids

A typical Sudoku puzzle

A standard Sudoku puzzle is a grid with 81 small squares, arranged in a 9x9 pattern. This big grid is also divided into nine smaller 3x3 sections, often called "boxes." Your goal in Sudoku is to fill every empty square with a number from 1 to 9. The tricky part is that each number can only appear once in each row, once in each column, and once in each of the nine 3x3 boxes.

When you start a Sudoku, some squares already have numbers. These are called "clues." A well-made Sudoku puzzle has only one correct solution. People who love Sudoku, and even scientists, use special computer programs called "algorithms" to solve these puzzles. They also use them to create new puzzles, sometimes with cool patterns or special features.

Computers can solve most 9x9 Sudoku puzzles super fast, often in less than a second! But if the grid gets much bigger, like 16x16 or more, it becomes incredibly hard for computers to solve. This is because there are so many more possibilities, a problem called "combinatorial explosion."

How Computers Solve Sudoku

Trying One by One: Backtracking

A Sudoku (top) being solved by backtracking. Each square is tested for a valid number, moving "back" when there's a problem, and moving forward again until the puzzle is solved.

A Sudoku designed to be tricky for the simple "brute force" method.

One way computers solve Sudoku is using a method called backtracking. Think of it like a very organized way of guessing and checking. It's a type of "brute force" search, meaning it tries every possible option until it finds the right one.

Here's how backtracking works:

• The computer picks an empty square.
• It tries putting the number "1" in that square.
• Then, it checks if "1" is allowed there (making sure it doesn't break any Sudoku rules for that row, column, or box).
• If "1" is allowed, the computer moves to the next empty square and tries "1" there.
• If "1" is NOT allowed, or if it tries all numbers (1-9) in a square and none work, it "backtracks." This means it goes back to the previous square it filled.
• At that previous square, it changes the number to the next one (e.g., from "1" to "2").
• It keeps doing this, moving forward when things work and backward when they don't, until the whole puzzle is solved!

The animation shows this process. The red numbers are the original clues and don't change. The computer fills in the other squares, sometimes changing its mind and trying new numbers if a path doesn't work out.

This method has some good points:

• It's guaranteed to find a solution if one exists.
• The time it takes usually doesn't depend much on how hard the puzzle is.
• The computer code for it is fairly simple to write.

However, it can sometimes be slow. Imagine a puzzle where the first row should be "987654321." If the computer starts by trying "1" in the first square, it will try many, many combinations before it finally gets to "9." Some puzzles are even designed to make this method take a long time! But with today's fast computers, even these tricky puzzles can be solved in less than a second.

Smart Guessing: Stochastic Search

Another way to solve Sudoku is using "stochastic" methods. This means they use some randomness. Here's a simple idea of how it works:

• First, the computer randomly fills all the empty squares with numbers.
• Then, it counts how many mistakes it made (how many numbers break the rules).
• Next, it "shuffles" or changes some of the numbers around, trying to reduce the number of mistakes.
• It keeps shuffling until there are zero mistakes, and the puzzle is solved!

Methods like "simulated annealing" or "genetic algorithms" are used for this shuffling. These methods are often very fast. They are also good because they can solve puzzles that might not be solvable just by pure logic.

Solving with Rules: Constraint Programming

Sudoku can also be seen as a "constraint satisfaction problem." This means you have a set of rules (constraints) that numbers must follow. Computer programs can be written to understand these rules.

A "constraint solver" can figure out the puzzle by applying these rules. For example, if a square can only be a 5 or a 7, and then another rule shows it can't be a 7, the solver knows it must be a 5. For easier Sudokus, these programs might not even need to backtrack! Combining this rule-based approach with backtracking makes a very fast and powerful solver for all kinds of Sudokus.

Covering the Bases: Exact Cover

Another clever way to think about Sudoku is as an "exact cover" problem. This is a math idea where you need to pick a set of items that perfectly "cover" all the requirements without any overlap.

When Sudoku is set up this way, special algorithms (like "Knuth's Algorithm X") can solve it incredibly fast, often in just a few thousandths of a second! It's a very efficient and elegant way to find the solution.

Creating New Sudokus

Computers are also used to create new Sudoku puzzles. People search for puzzles with special features, like having very few starting clues or having a cool symmetrical pattern.

A Sudoku with 17 clues and a diagonal pattern.

An automorphic Sudoku with 18 clues and two-way diagonal symmetry.

A 17 clue Sudoku with a similar pattern. (Orange circles: removed clues, green circles: added clues, blue underline: different digit).

An 18 clue Sudoku with a horizontal pattern.

For example, people have found over 49,000 different Sudokus that only need 17 starting clues to be solved. Finding new ones is getting harder because most have already been discovered!

One common way to search for new puzzles is called "neighbor searching." Imagine you have a Sudoku you like. You make small changes to it, like moving a clue or swapping a few numbers. Then, the computer checks if this new version is also a valid Sudoku with a single solution. This helps discover new puzzles that are similar to ones already known, but still unique.

See also

In Spanish: Algoritmos para la resolución de sudokus para niños