Solving Sudoku in Pure SQL - DB Pro Blog<br>Limited Time Offer: 50% off

Toggle theme<br>Download

h1]:font-serif [&>h1]:text-3xl [&>h1]:font-semibold [&>h1]:tracking-tight [&>h1]:text-ink [&>h1]:mt-12 [&>h1]:mb-8 [&>h1:first-child]:mt-0 [&>h2]:font-serif [&>h2]:text-2xl [&>h2]:font-semibold [&>h2]:tracking-tight [&>h2]:text-ink [&>h2]:mt-16 [&>h2]:mb-6 [&>h3]:font-serif [&>h3]:text-xl [&>h3]:font-semibold [&>h3]:text-ink [&>h3]:mt-8 [&>h3]:mb-4 [&>p]:text-muted-foreground [&>p]:leading-7 [&>p]:mb-6 [&_p_a]:text-brand [&_p_a]:no-underline [&_p_a:hover]:underline [&>ul]:mb-6 [&>ul]:list-disc [&>ul]:list-inside [&>ul>li]:text-muted-foreground [&>ul>li]:mb-4 [&>ul>li>a]:text-brand hover:[&>ul>li>a]:underline [&>ol]:mb-6 [&>ol]:list-decimal [&>ol]:list-inside [&>ol>li]:text-muted-foreground [&>ol>li]:mb-4 [&>ol>li>a]:text-brand hover:[&>ol>li>a]:underline [&>strong]:text-ink [&>strong]:font-semibold [&>code]:text-ink [&>code]:bg-muted [&>code]:px-1.5 [&>code]:py-0.5 [&>code]:rounded [&>code]:text-sm [&>code]:font-mono [&>pre]:bg-muted [&>pre]:border [&>pre]:border-border [&>pre]:rounded-lg [&>pre]:p-4 [&>pre]:mb-6 [&>pre]:overflow-x-auto [&>pre]:text-sm [&>blockquote]:border-l-4 [&>blockquote]:border-brand [&>blockquote]:bg-surface [&>blockquote]:pl-4 [&>blockquote]:py-2 [&>blockquote]:my-6 [&>blockquote]:italic [&>a]:text-brand [&>a]:no-underline hover:[&>a]:underline [&_table]:w-full [&_table]:mb-6 [&_table]:border-collapse [&_th]:text-left [&_th]:text-ink [&_th]:font-semibold [&_th]:text-sm [&_th]:px-3 [&_th]:py-2 [&_th]:border-b [&_th]:border-border [&_td]:text-muted-foreground [&_td]:text-sm [&_td]:px-3 [&_td]:py-2 [&_td]:border-b [&_td]:border-border ">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.

Loading SQL environment...

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.

Loading SQL environment...

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.

Loading SQL environment...

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...