Sudoku Zero-Knowledge Proof

On the graph coloring page you saw how Peggy can prove she has a valid coloring without revealing it: shuffle the labels, lock each cell with a hash, let Victor challenge one piece, open only that piece. Sudoku uses the exact same trick — just with nine digits instead of three colors, and rows/columns/boxes instead of edges.

Sudoku is a harder puzzle, so the proof feels more impressive: Peggy convinces Victor her full $9 \times 9$ grid is correct while Victor never sees the completed board. By the end of this page you will understand the protocol step by step, play through it in the demo, and see how it satisfies the three rules of zero-knowledge.

The Problem

A Sudoku puzzle is a $9 \times 9$ grid. Some cells are filled in (preset clues); the rest are blank. The rules:

• Every row must contain the digits 1 through 9, each exactly once.
• Every column must contain 1 through 9, each exactly once.
• Every $3 \times 3$ box must contain 1 through 9, each exactly once.

Finding a solution from scratch is hard — that is what makes Sudoku puzzles fun. Checking a proposed solution is easy: scan every row, column, and box and confirm there are no duplicates. Zero-knowledge proofs love this pattern: the prover has something hard to find but easy to verify.

Imagine Victor publishes a Sudoku puzzle online and offers a prize for a solution. Peggy claims she solved it but will not post the full grid — someone could copy her answer and steal the prize. She needs to convince Victor "I have a valid solution" without handing over a single cell of the completed puzzle.

The Setup

Two parties, same names as everywhere else on this site:

• Peggy (Prover) — holds a complete, valid solution to Victor's Sudoku puzzle. She wants credit (or payment) without publishing the answer.
• Victor (Verifier) — knows the puzzle (the preset clues) and wants convincing evidence that a valid solution exists. He must not learn the solution itself.

Victor already trusts that Peggy's solution matches the presets — that part is easy to check once you see the full grid. The hard part is proving the rest of the grid is filled in correctly without revealing it. The protocol below does exactly that.

The Protocol

Each round has three steps, just like graph coloring.

Step 1 — Shuffle and Commit

Peggy starts with her secret solution grid. Before Victor sees anything, she picks a random digit permutation — a secret relabeling of 1 through 9. For example she might decide: $1 \to 4$, $2 \to 7$, $3 \to 1$, and so on. She applies this mapping to every cell in her solution. Because she relabels consistently, the grid is still a valid Sudoku — only the symbols changed.

Next she places a cryptographic lock on each of the 81 cells. For cell $i$ she publishes a commitment:

Here $d_i$ is Peggy's digit at that cell, $\sigma(d_i)$ is the permuted digit she sends on the wire, and $r_i$ is a fresh random nonce (a long random string). Victor receives 81 hash values — sealed envelopes. He cannot guess what is inside any of them.

Step 2 — Challenge

Victor picks one of 27 challenge groups at random:

• one of the 9 rows, or
• one of the 9 columns, or
• one of the 9 boxes ($3 \times 3$ subsquares), or
• the preset cells — to check Peggy's permutation is consistent across the board.

Any valid Sudoku row, column, or box must contain the digits 1–9 exactly once. That is the structural fact Victor will test.

Step 3 — Reveal and Verify

Peggy opens the commitments for the challenged cells — she sends Victor the permuted digit and nonce for each. Victor checks:

1. Hashes match — recomputing SHA-256 from what Peggy sent gives the same commitment she published earlier.
2. No duplicates — for a row/column/box challenge, the nine revealed permuted digits are all different (hence some permutation of 1–9).
3. Presets consistent — if Victor challenged preset cells, every cell showing the same original clue digit must map to the same permuted digit under $\sigma$.

Victor has now audited one slice of the board. The other 72 cells stay locked. Peggy and Victor repeat the whole round with a brand-new random permutation $\sigma$.

Why Cheaters Get Caught

If Peggy does not have a valid solution, at least one row, column, or box contains a duplicate digit. No permutation can fix that — duplicates stay duplicates under relabeling. Victor's challenge is uniform over 27 groups, so the chance he misses the broken group in one round is at most $\tfrac{26}{27}$. After $k$ independent rounds:

One round is weak (Victor is only about 3.7% confident). Many rounds drive confidence up — see the table below after the demo.

Try It Yourself

The demo below runs a real instance of the protocol on a classic Sudoku puzzle. You play both Peggy and Victor. Indigo cells are Victor's presets; everything else is Peggy's secret. Each round: Peggy commits all 81 cells with SHA-256, you pick Victor's challenge (row, column, box, or presets), then watch verification run. Hashes are computed in your browser via the Web Crypto API.

• Begin Protocol — Peggy shuffles digits and sends 81 commitments.
• Challenge — pick a row, column, box, or preset check for Victor.
• Reveal — Peggy opens only the challenged cells.
• Verify — hashes, distinct digits, and preset consistency are checked.

Cryptographic Commitments

The locks on each cell are hash commitments, the same primitive used in graph coloring. Publishing $\text{SHA-256}(\sigma(d_i) \| r_i)$ is binding: Peggy cannot change her mind about a cell after committing. It is hiding: Victor cannot brute-force the digit — the nonce makes even a 1-in-9 guess look like random noise.

A single cell might look like this in one round:

-- Peggy's secret (cell 40, row 5 col 5) --
True digit:     5
Permuted digit: 2        (via secret σ)
Nonce:          kR8mQp2nXv4L
Commitment:     a7f3c91e...   (SHA-256 of "2-kR8mQp2nXv4L")

-- Victor challenges row 5 --
Peggy opens all 9 cells in that row.
Victor checks each hash and confirms nine distinct digits.

Why Is This Zero-Knowledge?

Recall the three rules. Here is how Sudoku satisfies each one.

Completeness

If Peggy has a genuinely valid solution, every row, column, and box she is asked to open will show nine distinct digits. Preset checks will line up. An honest Peggy always passes an honest Victor.

Soundness

A cheating Peggy with an invalid grid has at least one broken group (duplicate in some row, column, or box). Victor catches that group whenever he challenges it. With 27 equally likely groups, each round has at most a $\tfrac{26}{27}$ chance of missing the flaw. Repeating rounds compounds Victor's confidence — same logic as the Ali Baba Cave, but with 27 doors instead of 2.

Zero-Knowledge

What does Victor learn from a successful round? He sees nine distinct digits in one row — but he already knew any valid row must be a permutation of 1–9. The specific digits are meaningless because Peggy applied a fresh random relabeling $\sigma$ that Victor cannot reverse.

Victor could have simulated the transcript himself: pick a random row, write down nine random distinct digits, invent matching hashes. The result looks identical to a real interaction. Because he could fake it without Peggy's secret, the real conversation leaks nothing about her actual solution.

How Many Rounds?

With 27 possible challenge groups, the soundness error per round is $\frac{26}{27} \approx 96.3\%$. This decreases exponentially with each round:

Compare with graph coloring, which had $\frac{m-1}{m}$ soundness error per round where $m$ is the number of edges. For the classic 6-edge example that was $\frac{5}{6} \approx 83.3\%$ per round — much better per-round guarantees. Sudoku's 27 groups give weaker per-round reduction but the protocol applies to a richer, more structured problem.