Sudoku solver in pure SQL

WITH RECURSIVE
  input(sud) AS (
    VALUES('53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79')
  ),
  digits(z, lp) AS (
    VALUES('1', 1)
    UNION ALL SELECT
    CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
  ),
  x(s, ind) AS (
    SELECT sud, instr(sud, '.') FROM input
    UNION ALL
    SELECT
      substr(s, 1, ind-1) || z || substr(s, ind+1),
      instr( substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
     FROM x, digits AS z
    WHERE ind>0
      AND NOT EXISTS (
            SELECT 1
              FROM digits AS lp
             WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
                OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
                OR z.z = substr(s, (((ind-1)/3) % 3) * 3
                        + ((ind-1)/27) * 27 + lp
                        + ((lp-1) / 3) * 6, 1)
         )
  )
SELECT s FROM x WHERE ind=0;

It is one of the examples of Recursive CTE from SQLite docs

The WITH Clause

Let's step in step by step and see how it is working

WITH RECURSIVE Clause

The query begins with the `WITH RECURSIVE` clause, which allows us to define common table expressions (CTEs) that can refer to themselves. This is crucial for handling recursive operations, like the backtracking needed to solve a Sudoku puzzle.

Input CTE

sql
input(sud) AS (
 VALUES('53..7….6..195….98….6.8…6…34..8.3..17…2…6.6….28….419..5….8..79')
)

The `input` CTE defines the starting Sudoku grid. The grid is represented as a string of 81 characters (9x9 grid), where each digit represents a filled cell, and dots (`.`) represent empty cells that need to be filled.
- **Structure**: In this example, the string `’53..7….6..195….98….6.8…6…34..8.3..17…2…6.6….28….419..5….8..79'` is the puzzle input.

Digits CTE

digits(z, lp) AS (
 VALUES('1', 1)
 UNION ALL SELECT
 CAST(lp+1 AS TEXT), lp+1 FROM digits WHERE lp<9
)

The `digits` CTE generates a list of digits (`1` to `9`) along with their positions.
— `VALUES(‘1’, 1)` initializes the sequence with the first digit `1`.
— `UNION ALL` recursively adds the next digit by incrementing the position until it reaches `9`.

X CTE

x (s, ind) AS (
 SELECT sud, instr(sud, '.') FROM input
 UNION ALL
 SELECT
 substr(s, 1, ind-1) || z || substr(s, ind+1),
 instr(substr(s, 1, ind-1) || z || substr(s, ind+1), '.' )
 FROM x, digits AS z
 WHERE ind>0
 AND NOT EXISTS (
 SELECT 1
 FROM digits AS lp
 WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
 OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
 OR z.z = substr(s, (((ind-1)/3) % 3) * 3
 + ((ind-1)/27) * 27 + lp
 + ((lp-1) / 3) * 6, 1)
 )
)

The `x` CTE is the core of the recursive logic, responsible for filling the Sudoku grid.
Initial Step
— `SELECT sud, instr(sud, ‘.’) FROM input` finds the position of the first empty cell (`.`) in the input string.
Recursive Step
— `substr(s, 1, ind-1) || z || substr(s, ind+1)` creates a new string by replacing the `.` at position `ind` with a digit `z`.
— `instr(substr(s, 1, ind-1) || z || substr(s, ind+1), ‘.’)` finds the position of the next empty cell after filling the current one.
— The `WHERE` clause checks two conditions:
1. `ind > 0` ensures that there are still empty cells to fill.
2. `NOT EXISTS` ensures that the digit `z` being placed does not violate the Sudoku rules (i.e., it does not appear in the same row, column, or 3x3 subgrid).

Final SELECT Statement

SELECT s FROM x WHERE ind=0;

The final `SELECT` statement retrieves the solved Sudoku grid.
The query selects the string `s` from the `x` CTE where `ind=0`, meaning all cells have been filled (no more `.` in the string), indicating that the puzzle is solved.

How the Query Works as a Whole

1. The puzzle is input as a string with digits and dots.
2. Digit Generation: A list of digits from `1` to `9` is generated for substitution.
3. Recursive Filling: The grid is filled recursively:
— The query attempts to place each digit in the first empty position.
— If the digit placement is valid (i.e., it doesn’t violate Sudoku rules), it proceeds to the next empty position.
— This process continues until the entire grid is filled.
4. Result: The solved puzzle is returned once the grid is filled without any violations.

Conclusion

This SQL query showcases a creative use of recursive common table expressions to solve a classic problem. While SQL is typically used for data retrieval and manipulation, this query demonstrates its power and flexibility, even in solving puzzles like Sudoku. The recursive approach allows the query to try different possibilities, backtrack when necessary, and ultimately find the solution.