What if solving Sudoku wasn't about telling the computer where to put each number?
Imagine telling it the rules of the game instead, and then asking: “Which board satisfies all of them?”
Today, we're going to do exactly that. With a real Prolog program in your browser!
Hang on... where's the algorithm?!
You've probably played Sudoku. Nine rows. Nine columns. Nine little 3×3 boxes. Your job? Fill in the missing numbers without repeating 1 through 9 in any row, column or box.
Now imagine a programmer arriving with an enormous suitcase of for loops, arrays, indexes and carefully arranged backtracking code.
“Excellent!” you say. “What's your plan?”
“I'll try a number, check everything, try another number, undo it, try again...”
Wait! What if we don't explain HOW to solve Sudoku?
What if we simply describe what a valid Sudoku is?
That's the remarkable idea behind Markus Triska's concise Sudoku formulation. It describes the rules as constraints. Scryer Prolog's constraint solver helps find values that satisfy them.
Nine lists. That's our entire board.
Each row is a list of nine entries. Each empty cell is a Prolog variable. Put nine rows together, and voilà: our Sudoku board is a list of lists.
Rows = [[1,_,_,8,_,4,_,_,_],
[_,2,_,_,_,_,4,5,6],
...].That underscore? It represents an anonymous variable—a value we don't know yet. No need to invent a name for every missing number.
Our goal isn't to give each cell a sequence of commands. It's to describe the conditions that the entire board must satisfy.
First rule: nothing weird in the cells!
length(Rows, 9),
maplist(same_length(Rows), Rows),
append(Rows, Cells),
Cells ins 1..9.The first two goals ensure there are nine rows of nine cells. Next, append/2 collects the cells into one list.
And then the fun begins: Cells ins 1..9 constrains each cell to an integer from 1 to 9.
We're not assigning a number to each cell. We're narrowing its possible values. That's constraint logic programming!
library(clpfd). Scryer Prolog uses library(clpz), for constraints over integers. We adapt the library import while preserving the underlying model.No repeats. No exceptions!
maplist(all_distinct, Rows),
transpose(Rows, Columns),
maplist(all_distinct, Columns).all_distinct/1 says the values in a list must all be different. Apply it to every row. Done!
But columns? We didn't store them as separate lists. No problem: transpose/2 turns rows into columns. Then we apply the same constraint.
Notice what is missing: no “move right”, no “check each neighbour”, no manual loop. We reuse relationships instead.
And what about the nine 3×3 boxes? They're next.
Three rows enter. Three boxes come out!
This is my favourite part. We take three consecutive rows and consume them three elements at a time.
blocks([], [], []).
blocks([A,B,C|As], [D,E,F|Bs], [G,H,I|Cs]) :-
all_distinct([A,B,C,D,E,F,G,H,I]),
blocks(As, Bs, Cs).Take the first three elements from each row: that gives you one complete 3×3 box! Constrain its nine values, then recursively continue with the remaining row elements.
When all three lists are empty, we're done. That's the base case.
“Wait... recursion is actually doing something elegant here!” Exactly! And unlike our old friends for and while, the relationship describes what makes the blocks valid.
Your Scryer Sudoku lab
Edit the program and ask Scryer to solve Markus Triska's sample puzzle. The interpreter runs locally in your browser through WebAssembly. For this prototype, its module is downloaded from a version-pinned CDN.
The reference answer is supplied for learning and is not computed by your browser's Prolog engine. Run the lab to calculate it independently.
Try changing a constraint and observe what happens. The original code is restored with Reset.
Ready to experiment.
Run a query to see the answer.
Your turn! No cheating... well, maybe a little.
Can you make Sudoku solve itself?
Run the default query. Compare the nine computed rows to the reference answer. Did Prolog satisfy all the conditions?
What if we forget the columns?
Comment out the line maplist(all_distinct, Columns) and run the program. Does that still describe Sudoku correctly? Why not?
Hint
The program may accept boards with repeated values in columns. A constraint model is only as good as the rules you include.
The impossible puzzle
Change one given value so that a row contains two identical fixed digits. Can the model solve it?
Hint
Replace the first row's second cell (_) with 1. The first row already starts with 1, so its values cannot be all distinct.
You described a solution without writing the search!
Of course Scryer has an execution strategy, and the search can be expensive. Constraint propagation and labeling/2 do real computational work behind the scenes.
But the program you wrote describes the valid boards, rather than every procedural move to solve one.
That's a different way to think about programming. And it is extraordinarily powerful.
Now, where did we put that steering wheel? Oh, that's right. We don't need it!
Further reading: Markus Triska's original public-domain solver · Scryer CLP(Z) documentation · scryer-js