Solving Sudoku in Pure SQL

We ran a chess engine in pure SQL, then built Conway's Game of Life the same way. You seemed to like watching a query language do things it was never meant to do, so here is another one.

This time SQL solves Sudoku. Not stores puzzles. Solves them. You give it a grid with holes, and one query fills in every blank, obeying every rule, using nothing but a recursive CTE and some string arithmetic.

Here is a real puzzle, solved live in your browser by a single SQLite statement. No solver library. No backtracking code in JavaScript. Just SQL.

That one query does the whole job. By the end of this post you will have built it piece by piece, and you will be able to drop in your own puzzle and watch it solve.

Let's take it apart.

A puzzle is just a string

A Sudoku grid has 81 cells. We could model that as a table with a row per cell, but there is a simpler representation that makes the solver much easier to write: one string, 81 characters long, read left to right and top to bottom. A filled cell holds its digit. A blank cell holds a dot.

So this string:

53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79

is this grid. We can prove it by slicing the string back into a 9 by 9 layout. The trick is the same conditional aggregation pivot from the chess post: number every character, work out its row and column, then GROUP BY the row and pull each column out with a CASE inside MAX.

pos is a small recursive CTE that counts from 1 to 81. For each position p, integer division gives the row ((p-1)/9) and the remainder gives the column ((p-1)%9). Blanks show up as a dot so you can read the shape. Nothing clever yet, but now we have a way to see what we are doing.

Nine digits to try

The solver needs to try the digits 1 through 9 in each blank. Rather than hardcode them, we generate them with another tiny recursive CTE.

z is the digit as text, and lp is the same value as a number that we will reuse as a loop counter when checking the rules. Small piece, but it does double duty.

Backtracking, expressed as a query

Here is the heart of it. A Sudoku solver works by backtracking: find the first empty cell, try a digit that does not break any rule, then move on to the next empty cell and do the same. If you reach a point where no digit fits, you back up and try a different one earlier.

That sounds like loops and a stack. In SQL we express the exact same search as a recursive CTE that grows a set of partial boards.

Read the x CTE this way:

• The starting row is the puzzle itself, together with instr(sud, '.'), the position of its first blank.
• Each recursive step takes a partial board, joins it against all nine digits, and for every digit that is legal in that first blank, produces a new board with the blank filled and the position of the next blank computed.
• A board where ind equals 0 has no blanks left. That is a finished solution.

Every legal move spawns a new row. Illegal moves are filtered out before they ever appear. So the CTE explores the whole search tree, one filled cell at a time, and the rows where ind=0 are the leaves that made it all the way.

The filling itself is pure string surgery. To place digit z at position ind, we take everything before it, add the digit, and add everything after:

substr(s, 1, ind-1) || z || substr(s, ind+1)

Checking the rules

The only thing standing between a legal move and an illegal one is the NOT EXISTS block, and it is where the real work happens. A digit is legal in a cell if it does not already appear in that cell's row, its column, or its 3 by 3 box. We check all three by walking lp from 1 to 9 and reading one neighbouring cell each time:

NOT EXISTS (
  SELECT 1 FROM digits AS lp
  WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)                    -- same row
     OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)           -- same column
     OR z.z = substr(s, (((ind-1)/3)%3)*3
                      + ((ind-1)/27)*27 + lp + ((lp-1)/3)*6, 1)   -- same box
)

The first line reads the nine cells of the row. The second steps down the column nine cells at a time. The third, the ugly one, walks the nine cells of the surrounding 3 by 3 box. If the candidate digit z matches any of those 27 neighbours, the move is rejected and that branch of the search dies quietly. This pruning is what keeps the whole thing from exploring an astronomical number of dead ends.

The whole solver

Put the pieces together and you get a query that turns a puzzle string into a solved one. This version returns the raw 81-character answer, so you can see exactly what the recursion produces before we make it pretty.

One row comes back, and it is the answer. Now feed that string through the same pivot from earlier and it becomes a board. This is the query from the top of the post, and you have now built every line of it.

DB Pro

Work With Your Databases Like A Pro

Query, explore, and manage your databases with a beautiful desktop app and built-in AI.

Download Now

It is also a validity checker

Because the recursion finds every complete board, not just the first one, a small change turns the solver into a proof of correctness. A proper Sudoku has exactly one solution. Count the finished boards and you can check that.

One solution, found after exploring a few thousand partial boards. If that number came back as 2 or more, the puzzle would be ambiguous, and if it came back as 0, the puzzle would be impossible. The same query solves, validates, and grades difficulty, all at once.

Your turn

Here is the solver with a puzzle you can replace. Swap the 81-character string on the VALUES line for any Sudoku you like, keeping dots for the blanks and reading left to right, top to bottom. Run it and watch the grid fill in.

One honest caveat: this is plain backtracking with no clever move ordering. It always fills the first blank it finds, rather than the most constrained one. For most puzzles that is fine and the answer comes back in a blink. Feed it a deliberately fiendish grid, the kind designed to defeat naive solvers, and it can churn for a while as it wanders down long dead-end branches. A human solver uses strategy; this query uses persistence.

Why this works

Strip away the Sudoku and what you have is a general shape. A recursive CTE where each step extends a partial answer, an EXISTS check that prunes illegal extensions, and a terminal condition that marks a complete answer. That is backtracking search, and it is the same pattern behind solving mazes, placing N queens, generating permutations, and walking any tree of possibilities.

SQL is usually pitched as a language for asking questions about data that already exists. But a recursive CTE can generate and explore new states just as happily as it can traverse stored rows. Once you see that, a lot of problems that look like they need a "real" programming language turn out to fit in a single query.

The database was solving Sudoku the whole time. It just needed to be asked in the right order.

Jay